赛时没做出来 D，结果似乎比较简单……
赛时进度：ABC Accepted，Penalty：59：56，Rank：291，Rating：1995 -> 2006。
改题进度：ABCDE Accepted。
A 题意：给定字符串 $S$，可以修改其中的 $k$ 个字符，问可以得到的最小循环节。$|S|\leq 2000$。
直接暴力枚举循环节是否合法，这样每一个对应的位置需要变成一个字符，统计众数出现次数即可。计算众数的时候可以做到线性。
由于循环节最多只有 $O(\sqrt n)$ 种，所以得到时间复杂度 $O(n\sqrt n)$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 int solve (int st, int d) int res = 0 ; for (int i = st; i <= n; i += d) chkmax (res, ++ cnt[s[i] - 'a' ]); for (int i = st; i <= n; i += d) -- cnt[s[i] - 'a' ]; return res; } int main () std::cin >> n >> k >> (s + 1 ); for (int i = 1 ; i <= n; ++ i) { if (n % i) continue ; int res = n; for (int j = 1 ; j <= i; ++ j) res -= solve (j, i); if (res <= k) printf ("%d\n" , i), exit (0 ); } return 0 ; }
B 题意：给定只有 A、R、C 的字符串，奇数次操作可以 ARC -> R，偶数次操作可以 ARC -> AC，问最多可以进行的操作次数。$|S|\leq 2\times 10 ^ 5$。
容易发现我们每一段是独立的，因为 ARC -> AC 后两边都不能再合并，只有 AA...ARC...CC 可以通过只有奇数次变换可以得到 ARC，最后一次任选。
这样我们可以将原串的有用部分压缩为 AA...ARC...CC 中 $\min\{len_A, len_C\}$，容易发现这一定是可以的，多出来的部分是无法操作的。
这样奇数操作就是对数列中的一个非零数 -1，偶数操作就是将一个非零数变为 0。问最多多少次操作。
这其实是可以贪心的：我每次将尽量靠近 1 又不是 1 的一个数用奇数操作，直到他变成 1，这样偶数操作删除这个数的时候代价是最小的。我赛时的代码就是这个。
考虑两个上界：
偶数次操作最多只有 ARC出现的次数，因为一个偶数次一定会消耗一个 ARC 而不会再次出现。
总操作最多只有压缩后数列的和，因为操作一次，至少会减 1。
从偶数操作容易推出所有操作的一个上界：$2\times cnt$（不可能最后一次是一个奇数操作，因为这样的话，我们预估的 $cnt$ 就可以 +1
直接取 $\min$ 即可。代码是贪心，时间复杂度 $O(n\log n)$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 int main () scanf ("%d%s" , &n, s + 1 ); for (int i = 1 ; i <= n; ++ i) { if (s[i] ^ 'R' ) continue ; int len = 1 ; while (i > len && i + len <= n && s[i - len] == 'A' && s[i + len] == 'C' ) len ++; if (len > 2 ) al.push_back (len - 1 ); else cnt += len == 2 ; } std::sort (al.begin (), al.end ()); sz = al.size (); int ans = 0 , i = 0 , j = 0 ; while (1 ) { ++ ans; if (ans & 1 ) { while (i < sz && al[i] <= 1 ) ++ i; if (i >= sz) break ; al[i] --; } else { if (cnt) { -- cnt; continue ; } if (j >= sz) { break ; } al[j ++] = 0 ; } } -- ans; int cur = 0 ; for (int &x : al) assert (x >= 0 && x <= 1 ), cur += x; printf ("%d\n" , ans + cur + cnt); return 0 ; }
C 题意：给定 $n, x$，要求构造长度为 $n$ 的排列 $p$ 使得 $p_1 = x$ 且 $a_i = |p_i - p_{i + 1}|$ 序列的最长严格上升子序列最大。
首先，如果不管 $p_1$ 的话，我们有一个最长上升字符列为 $n - 2$ 的答案。如果 $n$ 是偶数，我们构造即为 $\{\dfrac n2, \dfrac n2 + 1, \dfrac n2 - 1, \dfrac n2 + 2\dots\}$ 或 $\{\dfrac n2 + 1, \dfrac n2, \dfrac n2 + 2, \dfrac n2 - 1\dots\}$，相邻两个差是 $\{1, 2, \dots\}$，这达到了上界。如果是奇数，构造即为 $\{\dfrac{n + 1}2, \dfrac{n + 1}2 + 1, \dfrac{n + 1}2 - 1, \dfrac{n + 1}2 + 2\dots \}$ ，容易证明这个也是达到了上界的。
现在考虑加入 $p_1 = x$。第一种方案是我们不管 $p_1$，后面原来 $\geq x$ 的加 1 即可。第二种方案是我们先将 $p_1$ 按照上面的构造尽可能摆放，剩下的随便摆。容易发现如果 $x$ 不是上面最优情况的开头，第二个一定不优。
剩下的随便分类讨论即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 int main () std::cin >> n >> x; if (n & 1 && x == (n + 1 ) / 2 ) { printf ("%d " , x); for (int i = 2 , j = (n + 1 ) / 2 - 1 , k = (n + 1 ) / 2 + 1 ; i <= n; ++ i) if (i & 1 ) printf ("%d " , k ++); else printf ("%d " , j --); return 0 ; } else if (!(n & 1 ) && x == n / 2 ) { printf ("%d " , x); for (int i = 2 , j = n / 2 + 1 , k = n / 2 - 1 ; i <= n; ++ i) if (!(i & 1 )) printf ("%d " , j ++); else printf ("%d " , k --); return 0 ; } else if (!(n & 1 ) && x == n / 2 + 1 ) { printf ("%d " , x); for (int i = 2 , j = n / 2 + 2 , k = n / 2 ; i <= n; ++ i) if (i & 1 ) printf ("%d " , j ++); else printf ("%d " , k --); return 0 ; } if (n & 1 ) { for (int i = 2 , j = n / 2 + 1 , k = n / 2 ; i <= n; ++ i) if (i & 1 ) p[i] = j ++; else p[i] = k --; } else { for (int i = 2 , j = n / 2 + 1 , k = n / 2 ; i <= n; ++ i) if (!(i & 1 )) p[i] = k --; else p[i] = j ++; } printf ("%d " , x); for (int i = 2 ; i <= n; ++ i) printf ("%d " , p[i] + (p[i] >= x)); return 0 ; }
D 题意：给定一个无向图，$i$ 会和 $x_i$ 连边，有些 $x_i$ 未定，问所有可能的 $x_i$ 无向图连通块个数之和。$n\leq 2000$。
观察 1：容易发现确定 $x_i$ 后的图一定是基环树森林，连通块的个数就是环的个数（包括自环）
观察 2：还没有形成基环树的连通块一定是树，每棵树中 $x_i$ 不确定的点有且只有 1 个。
观察 3：一旦形成了环，这个连通块的贡献就固定了，和其他的有没有联通过来没有关系（因为统计的是环的数量）
有了上面的发现，其实就比较好做了。
首先如果我们确定了 $k$ 棵树，总共有 $cnt$ 个点 $x_i$ 未确定，每棵的大小为 $a_i$，互相连接，并形成了环，那么对应的贡献应该是
发现答案和 $k$ 和 $\prod$ 有关，那么直接考虑 DP，即目前个数为 $k$ 的所有树的组合的乘积和。直接 $O(n ^ 2)$ 转移即可。
对于原来就是基环树的，我们已经形成了环，不参加 DP，直接贡献为 $n ^ {cnt}$。加和即可，时间复杂度 $O(n ^ 2)$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 void dfs (int x, int fa = 0 ) vis[x] = 1 , sz ++; for (int v : g[x]) if (v ^ fa) { if (vis[v]) { flag = 1 ; continue ; } dfs (v, x); } } int main () std::cin >> n; fact[0 ] = 1 ; for (int i = 1 ; i <= n; ++ i) fact[i] = (LL) fact[i - 1 ] * i % Mod; for (int i = 1 ; i <= n; ++ i) scanf ("%d" , &a[i]); for (int i = 1 ; i <= n; ++ i) { if (!~a[i]) continue ; g[a[i]].pb (i), g[i].pb (a[i]); } int excnt = 0 , res = 0 , mul; for (int i = 1 ; i <= n; ++ i) excnt += !~a[i]; mul = qpow (n, excnt); std::vector<int > vad; for (int i = 1 ; i <= n; ++ i) { if (vis[i]) continue ; sz = 0 , flag = 0 , dfs (i); if (flag) { adj (res += mul - Mod); continue ; } vad.pb (sz); } int cnt = vad.size (); f[0 ] = 1 ; for (int x : vad) for (int j = cnt - 1 ; ~j; -- j) if (f[j]) f[j + 1 ] = (f[j + 1 ] + (LL) f[j] * x) % Mod; for (int i = 1 ; i <= cnt; ++ i) if (f[i]) res = (res + (LL) f[i] * qpow (n, cnt - i) % Mod * fact[i - 1 ]) % Mod; std::cout << res << std::endl; return 0 ; }
E 题意：构造 $n\times m$ 的网格，每个数在 $[1, 25]$，要求 $\forall x_1, x_2\in [1, n], y_1, y_2\in [1, m]$，$a_{x_1, y_1}, a_{x_1, y_2}, a_{x_2, y_1}, a_{x_2, y_2}$ 不全相等。$n, m\leq 500$。
不是很好构造，虽然代码不超过 20 行：
1 2 3 4 5 6 7 8 9 10 const int B = 23 ;int main () int n, m; std::cin >> n >> m; for (int i = 1 ; i <= n; ++ i, puts ("" )) for (int j = 1 ; j <= m; ++ j) printf ("%d " , ((i / B) * (j / B) + i + j) % B + 1 ); return 0 ; }
看到 $25$ 和 $\sqrt n$ 同级，果断分块。
暂定为 $\sqrt n\times \sqrt n$ 的分块，那么需要考虑块内和块间的不同情况。
块内的话，需要我们每两个相同的数字得不在一行一列，否则同行 / 列的块内可能会出现对应的情况导致不合法。
既然不在一行一列，这要求我们需要每行每列都是排列，这样的话，我们按照如下构造即可：
那么块间像块内一样是否合法呢？、
首先看 $B = 3, n = m = 9$ 的示范样例输出：
1 2 3 4 5 6 7 8 9 3 1 2 1 2 3 2 3 1 1 2 3 2 3 1 3 1 2 2 3 1 3 1 2 1 2 3 1 2 3 2 3 1 3 1 2 2 3 1 3 1 2 1 2 3 3 1 2 1 2 3 2 3 1 2 3 1 3 1 2 1 2 3 3 1 2 1 2 3 2 3 1 1 2 3 2 3 1 3 1 2
容易发现第 4 行和第 2 行是一样的，是怎么回事呢？
我们发现，当第 1 行变为第 4 行的时候，我们将 1 2 3 的排列变成了 2 3 1，变为第 2 行的时候也是这样，导致第 2 行的输出和第 4 行完全相同。
这启示我们需要找到另外的方式，使得不会产生不合法情况。
给出结论：使用块行编号和纵编号的乘积。
手玩一下发现是不会冲突的。于是就是上面的那个代码（别问我是怎么看题解想到的