526互联

2021 Jiangsu Collegiate Programming Contest

发布时间 2024-01-11 19:28:18作者: Smallbasic

A. Spring Couplets

简单模拟。

B. Among us

容易想到对于每个内鬼和船员集合 \(S\)，求出它杀掉 \(S\) 中所有人的最短时间，最后 \(O(2^k)\) 合并答案即可。

考虑状压。设 \(f_{S,i}\) 杀完 \(S\) 中的人后站在节点 \(i\) 上所需要的最小时间，用类似最短路的方法转移即可。

C. Magical Rearrangement

从高到低贪心即可。

D. Pattern Lock

存在行数/列数有一个是偶数时，构造是容易的：不妨设列数为偶数，那么方案为： \((1,1)\rightarrow (2,2) \rightarrow (2,1)\rightarrow (3,2)\rightarrow \dots \rightarrow (n,1)\rightarrow (1,2)\rightarrow (3,n)\rightarrow \dots\)

行列均为奇数时，在角上挖一个 \(3\times 3\) 的方块，前 \((n-3)\times m\) 和左边 \(3\times (m-3)\) 的方案都可以用上面的方法构造出来，最后连到剩下的九宫格的中心，九宫格的方案是可以手动构造出的。

E. Stone Ocean

显然期望可以变为所有方案的权值和。

有个显然的状压做法：回文串要求第 \(i\) 个和第 \(n-i+1\) 个字符匹配，我们不妨设 \(f_S\) 表示已经从集合 \(S\) 中的串中选了字符且两两匹配的方案数，转移就是考虑每次枚举两个未加入的串，强行计算出匹配的方案数之后加入集合。统计答案是好做的。

状态数是 \(2^{30}\) 的，但是又很多无用的状态。设有用的状态数为 \(S(n)\)，则:

\[S(n)=\sum_{k=0}^n \binom{n-k}{k}=1+\sum_{k=0}^{n-1} \binom{n-k-1}{k}+\sum_{k=0}^{n-2} \binom{n-k-2}{k}=S(n-1)+S(n-2)+1 \]

\(S(n)\) 实际上只有 \(O(1.618^n)\) 级别的，可以通过。

F. Jumping Monkey II

路径统计问题考虑点分治。

设当前分治中心为 \(x\)，令 \(f(x)\) 表示当前子树从下往上的单调递减子序列最后一位为 \(x\) 是的最长长度，显然可以线段树合并求出来的。线段树合并将每个子树的答案合并到分治中心，并遍历每棵子树，另开一棵线段树统计根到当前节点的 dp 数组即可。

G.Five Phases

暴力列出五元生成函数的式子，因式分解可得到：\([v^ay^bx^cy^dz^e]\left[{(1+vw)(1+wx)(1+xy)(1+yz)(1+zv)\over vwxtz}\right]^k\)。

设 \(vw,wx,xy,yz,zv\) 展开的幂次分别为 \(f,g,h,i,j\)，可以列出一个五元一次方程组，解出来发现解是唯一的，于是一堆组合数乘起来即可。

H. Reverse the String

如果开头的一个字符在之后的字符串中字典序都是最小的那肯定不会翻转到它，于是我们可以快速找出翻转的左端点，问题变为一个翻转一个前缀使得字典序最小。用后缀数组/二分+哈希可以快速比较两个位置翻转后的结果。

I. Fake Walsh Transform

特判 \(n=0\) 的情况和 \(n=1,m=1\) 的情况。

对于剩下的情况，容易发现 \(0\sim 2^{m}-1\) 的异或和为 \(0\)，所以答案一定为 \(2^{m}-1\)

J. Anti-merge

容易发现方格是个二分图，答案不超过 \(2\)，染色即可。

K. Longest Continuous 1

容易发现最长的连续段只会在形如 \(2^{x}-1,2^x\) 的地方出现，枚举 \(x\) 即可。

L. Tree Game

重排树的过程是自底向上的，那么对于每个子树，在向上重排的时候它的根节点的值是确定的。我们可以 dfs 的时候维护出重拍好这个子树之后它根节点上是什么值。

考虑在 dfs 的同时计数，设 \(f_{i}\) 表示子树 \(i\) 的填数方案，\(c\) 表示排到现在 \(i\) 和它儿子上 \(0\) 的个数，则对于这些 \(0\)，他们所代表的数的集合在任何方案里都是可以唯一确定的，它们的顺序则可以任意打乱，因此有：

\[f_i = c! \prod_{j} f_j \]

注意判无解即可。