2021 Jiangsu Collegiate Programming Contest¶
B¶
题意¶
题解¶
D¶
题意¶
给一个 \(n\times m\) 个手机锁屏格点图，让你构造一个连满所有点的方案，使得相邻两步之间夹角为锐角。连得时候两点间不能有别的点。\(2 \le n, m \le 500\)
题解¶
逆天构造。
考虑其中有一个是偶数的情况，假设 \(n\) 是偶数，可以用下面的连法。
\((1, 1) \to (2, 2) \to (1, 2) \to \dots \to (1, m) \to (2, 1) \to (3, m) \to (4, m - 1) \to (3, m - 1) \to \dots \to (4, 1) \to (3, 1) \to (4, m) \to (5, 1) \to \dots\)
如果全为奇数，根据数据范围可知 \(n, m \ge 3\)。考虑先构造一个 \(3 \times m\) 的东西出来。前 \(3 \times (m - 3)\) 可以用上面的做法先连，最后会剩下一个 \(3 \times 3\) 的格子，手玩一下嗯连就好了。
E¶
题意¶
定义一个字符串 \(s\) 个权值 \(w_s\) 为 \(s\) 的所有排列中为回文串的个数。
给定 \(n\) 个字符串，每个字符串中会等概率选择一个字符，问组成的字符串的权值期望是多少。
\(1 \le n \le 30, \sum|s_i| \le 5 \times 10 ^ 4\)
题解¶
本质上就是求 \(\Pi |s_i|\) 种情况所有排列有多少个回文串。
考虑这 \(n\) 个位置都与哪些位置配对，可以先不考虑配对的先后顺序，因为最后单独乘一个阶乘就可以。设 \(val_{i, j}\) 表示第 \(i, j\) 位配对这两个位置相同有多少种情况。如果 \(n\) 为奇数可以单独增加一个点 \(n + 1\)， \(val_{i, n + 1}\) 就表示这个点作为中心的情况。
考虑暴力的状压，\(dp_s\) 表示 \(s\) 的内部已经都配好对有多少种方案。考虑转移，由于我们不用考虑配对的先后顺序，因此我们可以固定转移的下一个是 \(s\) 中二进制位第一个为 \(0\) 的位置，设为 \(u\)，我们就有如下的转移。
最后答案就是 \((n/2)! \times dp_{(1 << n) - 1}\)
考虑这个东西复杂度的证明：
-
总的状态数仅有不超过 \(2^{n / 2}\) 种，因为 \(popcount(s) \% 2 = 0\)
-
总的转移数不多。设 \(S(n)\) 表示 \(n\) 的转移个数，看起来有 \(S(n) = \sum \binom{n}{k} \times (n - k - 1)[k \% 2 == 0]\) 最大有 \(7.5 \times 10^9\) 个转移，但是这里面有很多状态是不可能出现的。
根据我们的状态转移前 \(k\) 轮前 \(k\) 个位置一定被选择，因此 \(S(n) = \sum\binom{n - k}{k}\)，可以算出在 \(n \le 30\) 下 \(S(n) \le 1346269\)，可以在 \(O(n\times S(n))\) 的复杂度通过此题。
此题状态要用 \(\text{unordered\_map}\) 记录，当做 \(O(1)\) 好了。
F¶
题意¶
题解¶
G¶
题意¶
题解¶
L¶
题意¶
给一棵树，每个点有一个权值，为 \(1 \sim n\) 的排列。一个人进行游戏，每个点可以操作不超过一次，每次操作可以将他和他直接连接的儿子拿出来重新排列。这个人获胜当且仅当至少有一种操作方式使得 \(i = a_i\)。
现在有些点权值未知，问有多少种赋值方式使得这个人能获胜。
\(n \le 2 \times 10 ^ 5\)
题解¶
考虑都赋值什么情况不能获胜。
设现在操作 \(u\)，\(u\) 与直接连接的儿子的序号集合为 \(A\)，权值集合为 \(B\)，分情况讨论：
-
如果 \(A = B\)，操作后 \(u = a_u\)，回溯即可。
-
如果 \(A \not = B\)：
-
如果 \(|A \cap B| <= |A| - 2\) ，显然无解。
-
否则我们有 \(x \in |B - (A \cap B)|, a_u = x\)，回溯判断。
由这个性质就可以计数了，定义与上文相同：
-
如果 \(B \subset A\)， \(a_u = 0\) 或者 \(a_u = u\)
-
如果 \(B \not \subset A\)：
-
如果 \(|B - (A \cap B)| >= 2\)，无解。
-
否则我们有 \(x \in |B - (A \cap B)|, a_u = x\)
-
设 \(cnt\) 为 \(u\) 与 \(u\) 直接相连的儿子中 \(0\) 的个数，\(dp_u = cnt! \times dp_v\)，\(v\) 为 \(u\) 的直连儿子。
最终还需要判断 \(a[1]\) 与 \(1\) 是否想等即可。
注意计数的时候我们本质上只考虑的 \(0\) 的个数，可以考虑从终态反推，略了。