前言
wzy 在这场比赛中打到 rnk66，特此来纪念纪念。
由于细节和代码能力问题，wzy 就讲讲 EX 的思路（考场思路），代码就不放了（也没 AC)。
还有题意的话，大家就自己读了哈。
D - Magical Cookies
发现最对修改 2n 次，且每次修改是更改 n 个顶点，从而可以 bfs 模拟即可，直接上代码。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2010;
char c[N][N];
int cl[N], cu[N];
int vis[N][N], visl[N], visu[N];
int cntl[N][27], cntu[N][27];
int suml[N], sumu[N];
queue<pair<int, int> > q;
int main() {
int n, m; scanf ("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf ("%s", c[i] + 1);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
c[i][j] -= 'a'; int x = c[i][j];
if (!cntl[i][x]) cl[i]++; cntl[i][x]++;
if (!cntu[j][x]) cu[j]++; cntu[j][x]++;
suml[i]++; sumu[j]++;
}
}
for (int i = 1; i <= n; ++i) {
if (!visl[i] && cl[i] == 1 && suml[i] >= 2) q.push (make_pair (i, 0)), visl[i] = 1;
}
for (int i = 1; i <= m; ++i) {
if (!visu[i] && cu[i] == 1 && sumu[i] >= 2) q.push (make_pair (i, 1)), visu[i] = 1;
}
while (!q.empty()) {
pair<int, int> u = q.front(); q.pop();
if (u.second == 0) {
int i = u.first;
for (int j = 1; j <= m; ++j) {
if (vis[i][j]) continue;
int x = c[i][j]; vis[i][j] = 1;
suml[i]--; sumu[j]--;
cntl[i][x]--; if (!cntl[i][x]) cl[i]--;
cntu[j][x]--; if (!cntu[j][x]) cu[j]--;
}
} else {
int j = u.first;
for (int i = 1; i <= n; ++i) {
if (vis[i][j]) continue;
int x = c[i][j]; vis[i][j] = 1;
suml[i]--; sumu[j]--;
cntl[i][x]--; if (!cntl[i][x]) cl[i]--;
cntu[j][x]--; if (!cntu[j][x]) cu[j]--;
}
}
for (int i = 1; i <= n; ++i) {
if (!visl[i] && cl[i] == 1 && suml[i] >= 2) q.push (make_pair (i, 0)), visl[i] = 1;
}
for (int i = 1; i <= m; ++i) {
if (!visu[i] && cu[i] == 1 && sumu[i] >= 2) q.push (make_pair (i, 1)), visu[i] = 1;
}
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (!vis[i][j]) ans++;
}
}
printf ("%d\n", ans);
return 0;
}E - Prerequisites
建反边，看节点 1 的前驱，然后 dfs 直接扫描即可。
#include <queue>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 2e5 + 10;
struct node {
int to, nxt;
} edge[N << 1];
int cnt, head[N], in[N];
int n, ans[N], cc[N], vis[N];
void add (int u, int v) {
cnt ++;
edge[cnt].to = v;
edge[cnt].nxt = head[u];
head[u]= cnt;
}
void dfs1 (int u) {
vis[u] = 1;
for (int i =head[u]; i; i = edge[i].nxt) {
int v = edge[i].to; cc[v]++;
if (!vis[v]) dfs1(v);
}
}
void dfs (int u) {
ans[++cnt] = u;
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].to; in[v]++;
if (in[v] == cc[v]) dfs(v);
}
}
int main() {
scanf ("%d", &n);
for (int i = 1; i <= n; ++i) {
int c; scanf ("%d", &c);
for (int j = 1; j <= c; ++j) {
int p; scanf ("%d", &p); add(i, p);
}
} cnt = 0; dfs1(1); dfs(1);
for (int i = cnt; i >= 1; --i) {
if (ans[i]== 1) break;
printf ("%d ", ans[i]);
}
return 0;
}F - Shortcuts
任意两点间的距离 $\leq 20000$，所以每个站点都去的最大代价是 $10^4 \times 20000 = 2\times 10^8$。
假定最优解 $C + 1$ 个站点不去，会花费 $2^C $ 钱，所以满足 $C \leq log_2(2 \times 10^8) $，即 $C \leq 30$（其实 20 就够了，大家自己可以想一想，不过没啥影响）。
这样就很好做了，直接 dp 即可。设 $f[i][j]$ 表示到第 $i$ 个站点（不能跳过），一共跳过 $j$ 个站点的最小代价。
转移方程考虑上一个不被跳过的站点即可，看代码即可。
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
const int M = 30;
const int N = 1e4 + 10;
double f[N][20];
int x[N], y[N];
double solve (int a, int b) {
return sqrt ((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]));
}
int main() {
int n; scanf ("%d", &n);
for (int i = 1; i <= n; ++i) scanf ("%d%d", &x[i], &y[i]);
double ans = 0;
f[1][0] = 0; f[1][1] = 1e9;
for (int i = 2; i <= n; ++i) {
for (int j = 0; j <= 20; ++j) {
f[i][j] = 1e9;
for (int k = i - 1; k >= max (1, i - j - 1); --k) {
f[i][j] = min (f[i][j], f[k][j - (i - k - 1)] + solve (k, i));
}
}
}
ans = f[n][0];
for (int i = 1; i <= 20; ++i) {
ans = min (ans, (1 << (i - 1)) + f[n][i]);
}
printf ("%.20lf\n", ans);
return 0;
}G - Ai + Bj + Ck = X (1 <= i, j, k <= N)
考虑到这个式子非常像扩欧的式子，于是考虑枚举 i, 那现在的目标就是求 $Bj + Ck = X - Ai(1 \leq j, k \leq n)$，这样就可以直接扩欧了。
具体关于上取整，下取整的细节见代码。
#include <cstdio>
#include <iostream>
using namespace std;
#define int long long
int exgcd (int a, int b, int &x, int &y) {
if (b == 0) {
x = 1, y = 0; return a;
}
int d = exgcd (b, a % b, x, y);
int tmp = x;
x = y; y = tmp - (a / b) * y;
return d;
}
int calfloor (int a, int b) {
if (a % b == 0) return a / b;
if (a > 0) return (a / b);
return (a / b) - 1;
}
int calceil (int a, int b) {
if (a % b == 0) return a / b;
if (a > 0) return (a / b) + 1;
return (a / b);
}
int solve (int a, int b, int d, int l1, int l2, int r1, int r2) {
if (d < 0) return 0;
int x, y; int g = exgcd (a, b, x, y);
if (d % g != 0) return 0;
d /= g; a /= g; b /= g;
x = (x * (d % b) % b + b) % b; y = (d - a * x) / b;
// x0 = x + kb, y0 = y - ka 就是方程的解。
// 要满足：l1 <= x + kb <= r1, 即 (l1 - x) / b <= k <= (r1 - x) / b
// 要满足：l2 <= y - ka <= r2, 即 (y - l2) / a >= k >= (y - r2) / a
int up = min (calfloor (r1 - x, b), calfloor(y - l2, a)); // 注意是上取整
int down = max (calceil (l1 - x, b), calceil(y - r2, a)); // 注意是下取整
if (up < down) return 0;
return up - down + 1;
}
signed main() {
int n, a, b, c, x; scanf ("%lld%lld%lld%lld%lld", &n, &a, &b, &c, &x);
int ans = 0;
for (int i = 1; i <= n; ++i) {
ans += solve (b, c, x - a * i, 1, 1, n, n);
}
printf ("%lld\n", ans);
return 0;
}Ex - Typical Convolution Problem
说实话，这题出得是真的坑。
直接转化式子，$ \frac{f[n]}{a[n]} = \sum{a + b < n} f[a]f[b] = \frac{f[n - 1]}{a[n - 1]} + \sum{a + b = n - 1} f[a]f[b] $
这样分治 fft 即可。
但是，考虑一下细节：
- f[0] 的贡献；
- a 和 b 的顺序不固定，比如当 a = b 时，估计计算时就只计算了 1 次。
啊啊啊，细节真多，我也没切，就不放错误代码了。。。