10.23 模拟赛

炼石计划 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. 字符串构造机

T2 - 洛谷专栏

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\) 不会了。