由于我的codeforces的帐号登不上，所以我错过了这场比赛，只好赛后再抄题解自己做。
A Benches
最大的情况就是所有人都挤在那个人最多的长椅上，最小的情况是所有人尽量平均的坐。
#include#include #include const int N = 110;int a[N], n, m, mx; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); mx = std::max(a[i], mx); } int ansb = mx + m, ansa = 0; for (int i = 1; i <= n; ++i) { m -= mx - a[i]; } if (m < 0) ansa = mx; else ansa = mx + m / n + (m%n != 0); printf("%d %d\n", ansa, ansb); return 0;}
提交次数：\(1\)
B Vitamins
这个题直接DP，把有哪几种维他命状压一下就行。
#include#include #include const int N = 1010;int V[N];int n, c[N], p[N];int f[10];int main() { V['A'] = 1; V['B'] = 2; V['C'] = 4; scanf("%d", &n); char s[5]; for (int i = 1; i <= n; ++i) { scanf("%d%s", &p[i], s); int len = strlen(s); for (int j = 0; j < len; ++j) c[i] |= V[s[j]]; } memset(f, 0x3f, sizeof f); f[0] = 0; for (int i = 1; i <= n; ++i) { for (int S = 7; S >= 0; --S) if (f[S] < 0x3f3f3f3f) { f[S|c[i]] = std::min(f[S|c[i]], f[S] + p[i]); } } if (f[7] == 0x3f3f3f3f) puts("-1"); else printf("%d\n", f[7]); return 0;}
提交次数：\(1\)
C Array Product
这个也是一个简单的构造题，贪心的做就行，不要忘记只能删除一个点。
删正数肯定是不优的。如果有偶数个负数，乘起来就行，如果有奇数个负数，将绝对值最小的负数和0乘起来（如果没有0那就直接删），然后把所有0乘起来删掉（如果就只剩一个0了那就不能删）。 最后把所有数乘起来就行。#include#include #include const int N = 2e5 + 10;int a[N], n, m, mx = 0, del[N], tot, posi, nega, zero;int ls[3][N]; int main() { scanf("%d", &n); a[0] = -0x3f3f3f3f; for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); if (a[i] == 0) { ls[1][++zero] = i; } else if (a[i] < 0 ) { ls[0][++nega] = i; if (a[i] > a[mx]) mx = i; } else { ls[2][++posi] = i; } } if (nega%2 != 0 && zero > 0) { printf("1 %d %d\n", mx, ls[1][1]); del[mx] = 1; tot++; } else if (nega%2 != 0 && zero == 0) { printf("2 %d\n", mx); del[mx] = 1; tot++; } if (zero > 0) { while (zero > 1 && tot < n-2) { printf("1 %d %d\n", ls[1][zero], ls[1][zero-1]); del[ls[1][zero]] = 1; zero--; tot++; } if (tot < n-1) { printf("2 %d\n", ls[1][1]); tot++; del[ls[1][1]] = 1; } } int i = 1, j; while (del[i]) i++; j = i+1; while (tot < n-1) { while (del[j]) j++; printf("1 %d %d\n", i, j); i = j; j = i+1; tot++; } return 0;}
提交次数：\(3\)（没看到只能删一次和少处理了一个情况）。
D Petya and Array
求区间和一定要求前缀和，然后问题就转化成了求\(\displaystyle\sum_{l}\displaystyle\sum_{r}[s_i-s_{l-1}<k]\)，化简一下就成了\(\displaystyle\sum_{l}\displaystyle\sum_{r}[s_i<k+s_{l-1}]\)，直接倒着做然后树状数组查就行。别忘了离散化的时候要把\(S_0 = 0\)也离散进去（并没有想明白为什么）
#include#include const int N = 200000 + 10;typedef long long LL;LL a[N], s[N], b[N], c[N];LL t;int n, mx;LL bt[N];inline void add(int x) { for (; x <= mx; x += x&-x) { bt[x]++; }}inline LL query(int x) { LL ans = 0; for (; x>0; x -= x&-x) { ans += bt[x]; } return ans;}int main() { scanf("%d%I64d", &n, &t); for (int i = 1; i <= n; ++i) { scanf("%I64d", &a[i]); s[i] = s[i-1] + a[i]; b[i+1] = s[i]; } std::sort(b+1, b+n+2); mx = std::unique(b+1, b+n+2) - b - 1; for (int i = 1; i <= n; ++i) { c[i] = std::lower_bound(b+1, b+mx+1, s[i]) - b; } LL ans = 0; for (int i = n; i; --i) { add(c[i]); int tmp = std::lower_bound(b+1, b+mx+1, s[i-1]+t) - b - 1; ans += query(tmp); } printf("%I64d\n", ans); return 0;}
提交次数：\(5\)（离散化没加\(0\)，和lower_bound上界写错）
E Vasya and Magic Matrix
这个题还是能轻松的想到排序后从小到大枚举计算的。只是我一开始没有看到欧式距离的平方，苦思无解，只好去看题解，结果……
有平方的话就有交换律和结合律了，某个点的期望值为\(f_x = \displaystyle\frac{\displaystyle\sum_{1\le i\le k}(f_i + (r_x-r_i)^2 + (c_x-c_i)^2)}{k}\)，其中\(k\)是所有比他小的点的数量。化简之后就能发现这个式子只与比他小的数的个数，横纵坐标的和，横纵坐标的平方和，以及期望和有关。开几个变量记录一下就行（我图方便开了数组）
#include#include typedef long long LL;const int N = 1e3 + 10;const int M = N*N;const LL MOD = 998244353;struct node { LL x, y, h; bool operator< (const node &x) const { return h < x.h; }} p[M];int n, m, tot;LL pos, sf[M], sx[M], sy[M], sx2[M], sy2[M], sk[M];LL dp[N][N];int x, y;inline LL pow_mod(LL x, LL p) { LL ans = 1; while (p) { if (p&1) ans = ans * x % MOD; x = x * x % MOD; p = p >> 1; } return ans;}int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { tot++; scanf("%I64d", &p[tot].h); p[tot].h++; p[tot].x = i; p[tot].y = j; } } scanf("%d%d", &x, &y); std::sort(p+1, p+tot+1); for (int i = 1; i <= tot; ++i) { if (p[i].h != p[i-1].h) { pos++; sf[pos] += sf[pos-1]; sx[pos] += sx[pos-1]; sy[pos] += sy[pos-1]; sx2[pos] += sx2[pos-1]; sy2[pos] += sy2[pos-1]; sk[pos] += sk[pos-1]; } LL f = 0; f = (f + sf[pos-1]) % MOD; f = (f + sx2[pos-1]) % MOD; f = (f + sy2[pos-1]) % MOD; f = (f + p[i].x * p[i].x % MOD * sk[pos-1] % MOD) % MOD; f = (f + p[i].y * p[i].y % MOD * sk[pos-1] % MOD) % MOD; f = (f - 2 * p[i].x % MOD * sx[pos-1] % MOD + MOD) % MOD; f = (f - 2 * p[i].y % MOD * sy[pos-1] % MOD + MOD) % MOD; f = f * pow_mod(sk[pos-1], MOD-2) % MOD; dp[p[i].x][p[i].y] = f; sf[pos] = (sf[pos] + f) % MOD; sx[pos] = (sx[pos] + p[i].x) % MOD; sy[pos] = (sy[pos] + p[i].y) % MOD; sx2[pos] = (sx2[pos] + p[i].x * p[i].x % MOD) % MOD; sy2[pos] = (sy2[pos] + p[i].y * p[i].y % MOD) % MOD; sk[pos] = (sk[pos] + 1) % MOD; if (p[i].x == x && p[i].y == y) break; } printf("%I64d\n", dp[x][y]); return 0;}
提交次数：\(0+1\)
F Leaf Sets
这个题看了一会儿觉得不可做，就直接看了题解。
其实用了树形DP的思想，先dfs下去，再统计儿子们的答案然后上传。不过这个在dfs里开vector的操作惊到我了，我以前从未见过这样的写法（但是这样不会爆栈吗？）。
首先，对于一个叶子节点的集合，我们用这个集合中深度最大的点代表这个集合，因为只有这个点决定了两个集合能否合并。如果两个集合\(A,B\)的代表点\(d_A,d_B\)之间的距离小于\(k\)，那就可以合并，且合并后代表点的深度为\(max\{ d_A, d_B \}\)，如果大于\(k\)呢？不妨设\(d_A\le d_B\)，此时\(d_B\)一定没有用了，因为之后能和\(B\)合并的也一定能和\(A\)合并，那么\(B\)集合就不用再合并了，直接记录答案就行。
#include#include #include const int N = 1e6 + 10;const int M = 2e6 + 10;int n, k;int hd[N], to[M], nxt[M], cnt;int dep[N], deg[N];int ans;inline void adde(int x, int y) { cnt++; to[cnt] = y; nxt[cnt] = hd[x]; hd[x] = cnt;}int dfs(int x, int f) { if (deg[x] == 1) { return 0; // 叶子直接返回0 } std::vector d; for (int i = hd[x]; i; i = nxt[i]) if (to[i] != f) { d.push_back(dfs(to[i], x) + 1); } std::sort(d.begin(), d.end()); while (d.size() >= 2) { if (d[d.size()-1] + d[d.size()-2] <= k) break; d.pop_back(); // 不能合并的就不合并了。 ans++; } return d.back(); // 相当于把d中的所有集合合并了。 }int main() { scanf("%d%d", &n, &k); for (int i = 1, x, y; i < n; ++i) { scanf("%d%d", &x, &y); adde(x, y); adde(y, x); deg[y]++; deg[x]++; } for (int i = 1; i <= n; ++i) if (deg[i] > 1) { dfs(i, 0); break; } printf("%d\n", ans+1); // 最后会剩下一个集合 return 0;}
提交次数：\(0+2\)（没有处理好叶子节点）