# 11.6NOIP模拟赛解题报告

## 心路历程

8点开始考，9:40就都拍上了。。可见题目确实水。。然后又去做了做另一套

## Sol

### T1

```#include<cstdio>
#include<algorithm>
#include<iostream>
#define lb(x) (x & (-x))
#define LL long long
using namespace std;
const LL MAXN = 1e6 + 10;
inline LL read() {
char c = getchar(); LL x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
LL N, f[MAXN], g[MAXN], a[MAXN], mod;
LL add(LL x, LL y) {
if(x + y < 0) return x + y + mod;
return x + y >= mod ? x + y - mod : x + y;
}
LL mul(LL x, LL y) {
return 1ll * x * y % mod;
}
LL fp(LL a, LL p) {
LL base = 1;
while(p) {
if(p & 1) base = mul(base, a);
a = mul(a, a); p >>= 1;
}
return base;
}
LL date[MAXN], num;
void Des() {
sort(date + 1, date + num + 1);
num = unique(date + 1, date + num + 1) - date - 1;
for(LL i = 1; i <= N; i++) f[i] = lower_bound(date + 1, date + num + 1, f[i]) - date,
g[i] = lower_bound(date + 1, date + num + 1, g[i]) - date;
}
LL T[MAXN];
void Add(LL x, LL val) {
while(x <= num) T[x] += val, x += lb(x);
}
LL Query(LL x) {
LL ans = 0;
while(x) ans += T[x], x -= lb(x);
return ans;
}
int main() {
freopen("calc.in", "r", stdin);
freopen("calc.out", "w", stdout);
for(LL i = 1; i <= N; i++) a[i] = read(), f[i] = fp(i, a[i]), g[i] = fp(a[i], i),
date[++num] = f[i], date[++num] = g[i];
Des();
LL ans = 0;
for(LL i = N; i >= 1; i--) {
ans += Query(f[i] - 1);
}
cout << ans;
return 0;
}```

### T2

```#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define LL long long
using namespace std;
const LL MAXN = 2e6;
inline LL read() {
char c = getchar(); LL x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
LL N, R;
LL  tag[MAXN], s[MAXN], a[MAXN], b[MAXN], K;
bool check(LL val) {
memset(tag, 0, sizeof(tag));
LL now = 0, res = K, flag = 1;
for(LL i = 1; i <= N; i++) {
now += tag[i];
a[i] += now;
if(a[i] < val) now += val - a[i], tag[i + 2 * R + 1] -= val - a[i], res -= val - a[i];
if(res < 0) {flag = 0; break;}
}
memcpy(a, b, sizeof(a));
return flag;
}
LL Query(LL l, LL r) {
r = min(r, N);
if(l < 0) return s[r];
return s[r] - s[l];
}
int main() {
freopen("game.in", "r", stdin); freopen("game.out", "w", stdout);
for(LL i = 1; i <= N; i++) a[i] = read(), s[i] = s[i - 1] + a[i];
for(LL i = 1; i <= N; i++) a[i] = Query(i - R - 1, i + R);
for(LL i = 1; i <= N; i++) b[i] = a[i];
LL l = 0, r = 3e18, ans = 0;
while(l <= r) {
LL mid = (l + r) >> 1;
if(check(mid)) l = mid + 1, ans = mid;
else r = mid - 1;
}
cout << ans;
return 0;
}```

### T3

```#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define Pair pair<LL, LL>
#define MP make_pair
#define fi first
#define se second
#define LL long long
using namespace std;
const LL MAXN = 1e6 + 10, INF = 1e9 + 10;
inline LL read() {
char c = getchar(); LL x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
LL N, M, Q, cnt, fa[MAXN], w[MAXN], ans, out[MAXN];
struct Edge {
LL u, v, w;
bool operator < (const Edge &rhs) const {
return w < rhs.w;
}
}E[MAXN];
Pair q[MAXN];
LL find(LL x) {
return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}
void AddEdge(LL i) {
LL x = E[i].u, y = E[i].v, v = E[i].w;
LL fx = find(x), fy = find(y);
if(fx == fy) w[fx] += v, ans = max(ans, w[fx]);
else {
fa[fx] = fy; w[fy] += v + w[fx]; w[fx] = 0;
ans = max(ans, w[fy]);
}
}
int main() {
freopen("graph.in", "r", stdin); freopen("graph.out", "w", stdout);
for(LL i = 1; i <= N; i++) fa[i] = i;
for(LL i = 1; i <= M; i++) E[i].u = read(), E[i].v = read(), E[i].w = read();
sort(E + 1, E + M + 1);
for(LL i = 1; i <= Q; i++) q[i] = MP(read(), i);
sort(q + 1, q + Q + 1);
LL j = 1;
for(LL i = 1; i <= Q; i++) {
while(j <= M && E[j].w <= q[i].fi)
out[q[i].se] = ans;
}
for(LL i = 1; i <= Q; i++) printf("%I64d\n", out[i]);
return 0;
}```

0 条评论

• ### POJ 2891 Strange Way to Express Integers

Description Elina is reading a book written by Rujia Liu, which introduces a ...

• ### 洛谷 P1313 计算系数

题目描述 给定一个多项式 ，请求出多项式展开后 项的系数。 输入输出格式 输入格式： 输入文件名为factor.in。 共一行，包含5 个整数，分别为 a...

• ### 洛谷P3799 妖梦拼木棒

题目背景 上道题中，妖梦斩了一地的木棒，现在她想要将木棒拼起来。 题目描述 有n根木棒，现在从中选4根，想要组成一个正三角形，问有几种选法？ 输入输出格式 输入...

• ### 打表法——暴力破解方法之一

特别声明：除特别标注，本站文章均为原创，本站文章原则上禁止转载，如确实要转载，请电联：wangyeuuu@qq.com，尊重他人劳动成果，谢过~

• ### POJ 2773 Happy 2006（容斥原理+二分）

Happy 2006 Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 1...

• ### POJ 2891 Strange Way to Express Integers

Description Elina is reading a book written by Rujia Liu, which introduces a ...

• ### 洛谷 P1313 计算系数

题目描述 给定一个多项式 ，请求出多项式展开后 项的系数。 输入输出格式 输入格式： 输入文件名为factor.in。 共一行，包含5 个整数，分别为 a...

• ### 扩展中国剩余定理详解

前言 阅读本文前，推荐先学一下中国剩余定理。其实不学也无所谓，毕竟两者没啥关系 扩展CRT 我们知道，中国剩余定理是用来解同余方程组 但是有一个非常令...

• ### 洛谷P1516 青蛙的约会

题目描述 两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出...

• ### 洛谷P3799 妖梦拼木棒

题目背景 上道题中，妖梦斩了一地的木棒，现在她想要将木棒拼起来。 题目描述 有n根木棒，现在从中选4根，想要组成一个正三角形，问有几种选法？ 输入输出格式 输入...