炼石计划 10 月 05 日 NOIP 模拟赛 #9【补题】 - 比赛 - 梦熊联盟
复盘
既然以前做过，复盘貌似不重要了吧？
T2 很快写完了。
T1 想到堆就做完了。
T3 忘了咋做了，好像是个 DP 但剩下忘了。于是写了暴力分跑路了。
T4 正解显然不可能会的。打满了暴力。
最后 T1 数组开小挂了 \(50\)。其余没有挂分。
总结
- 好的：
- 不足：
- 奇葩挂分。
- 做过的题不会做。
知识点
T1：贪心，堆。
T2：图论。
T3：DP，快速排序。
T4：并查集，组合计数。
A. 序列加法机
求出 \(c_i = |a_i-b_i|\)。如果 \(c\) 中不为 \(0\) 的元素数 \(>m\) 则无解。否则可以证明一定有解。
于是变成了对 \(c\) 做 Carrots for Rabbits。
考虑贪心。
首先令 \(f(i, j)\) 表示将一个元素 \(i\) 分成 \(j\) 部分的最小代价。显然能平均分就平均分。
初始时，显然每个元素都只被分成了一部分。用一个堆，维护每个元素从 \(j\) 部分变成 \(j+1\) 部分后，操作代价会减少多少。每次挑变化最大的变化。这样跌倒 \(m\) 次即可。
B. 字符串构造机
C. 快速排序机
显然 \(a\) 合法等价于 \([l, m-1],[m+1,r]\) 都合法。所以可以 DP。
最暴力的，设 \(f(l, r, h)\) 表示若要对 \(a = (l, l+1,\dots,r)\) 进行排序，且递归深度至多为 \(h\) 的合法 \(a\) 的方案数。
考虑转移。枚举 \(a_r = k\)，即快速排序时选择的基准，则：
\[f(l,r,h) = \sum_{k=l}^r \dbinom{r-l}{k-l} f(l,k-1,h-1) f(k+1,r,h-1) \]即，除 \(k\) 外总共 \(r-l\) 个位置，这些位置中有 \(k-l\) 个位置 \(<k\)，这些位置最终将按照原来的顺序摆放到 \(k\) 之前，剩下的位置也会按照原来的顺序放到 \(k\) 之后，所以会有个组合系数。
注意到 \(f(l, r, h) = f(1, r-l+1,h)\)。于是就能做到 \(\mathcal O(n^3)\)。
\[f(i, j) = \sum_{k=1}^i \dbinom {i-1}{k-1}f(k-1,j-1)f(i-k,j-1) \]D. 格子衫染色机
显然对 \(k\) 分类讨论，
\(k=0\) 显然答案一定在 \(0,1,2\) 内。极易。
\(k=1\)。
注意到 \(x_{i,j} = x_{1,1} \oplus x_{i,1} \oplus x_{1,j} \oplus [i \bmod 2 = 0 \land j \bmod 2 = 0]\)。
不妨枚举 \(x_{1,1}\)。那么 \(x_{i,1} \oplus x_{1,j}\) 可以表示成一个常数（\(0\) 或 \(1\)）。
因此建边。如果存在一个全为 \(1\) 的奇环则无解。否则答案为 \(2\) 的连通块数量次幂乘 \(2\) 的孤立点数量次幂。这里连通块只看 \(0\) 的边。
然后 \(k=2\) 不会了。
标签：10.23,T2,显然,T1,模拟,oplus,排序,DP From： https://www.cnblogs.com/2huk/p/18490242