Atcoder Regular Contest 134
比赛总结
- D 本来可以切的，只要把两个
second改为first即可。。。
题解
ARC134D Concatenate Subsequences
给出两个序列 \(A,B\)，请选择一个下标的子序列，然后将 \(A,B\) 保留这些位置后拼接起来，使得其字典序最小。
\(n \le 10^5\)
贪心
考场上的做法和官方题解一模一样，只要将两处 second 改成 first 就可以通过了。。。
首先，我们选出最小的 \(A_i = T\)，如果存在 \(A_i = T \wedge B_i \le T\)，那么直接选最小的 \(B_i\)，将两个拼接在一起就行了。
否则，我们要让这些后面的元素尽可能地靠后，于是要将所有 \(A_i = T\) 选出（可以理解为缓兵之计，缓解比较大的 \(B_i\) 的到来）。
之后，我们要尽可能地使用缓兵之计，于是我们可以将最后一个 \(A_i = T\) 后面的所有 \(
最后一个问题就是对于 \(A_i = V\) 的是否要选，我们可以考虑选了之后字典序时候变大，暴力 check 一次即可（如果成功则所有 \(A_i = V\) 都要选择）。
代码
ARC134E Modulo Nim
给出一个序列，长度为 \(n\)，第 \(i\) 个元素的值 \(b_i \le a_i\)，现在 Alice，Bob 轮流进行如下若干轮的游戏：
- 设 \(X = \max\{b_i\}\)，当 \(X\) 为 \(0\) 的时候，当前操作者获胜。
- 选择一个数 \(Y \in [1, X]\)，令 \(b_i \gets b_i \bmod ~ Y\)
问所有可能的情况中先手获胜的方案数。
\(n \le 200, a_i \le 200\)
动态规划 博弈论
考虑对于一个给定的序列，如何计算先手是否失败：
-
首先，相同元素对答案没有影响，于是我们可以将 \(\{b_i\}\) 去重。
-
\(\{1\}, \{2\}\) 一定是必输的。
-
接下来，我们可以枚举一些比较简单的情况，然后可以发现
- 考虑 \(Y = 2\)，如果 \(\{b_i\}\) 中存在奇数，先手必胜，于是 \(\{b_i\}\) 必须全部是偶数。
- 考虑 \(Y = 3\)，如果 \(\{b_i\}\) 中存在 \(\bmod ~ 3 = 1\) 和 \(\bmod ~3 = 2\) 的数，先手必败；如果 \(\{b_i\}\) 全部是 \(3\) 的倍数，那么先手必败；否则先手必胜，于是剩余的必败情况中 。
- 如果 \(Y = 4\)，如果 \(\{b_i\}\) 中存在 \(\bmod ~ 4 = 2\) 的数，那么先手依然必胜，于是 \(\{b_i\}\) 必须全部是 \(4\) 的倍数。
这个时候，我们发现，如果先手必输，除了之前两种特例，还有 \(\{4, 8\}\)，或者 \(\{b_i\}\) 全部是 \(12\) 的倍数，然后这些可能的数已经比较少了，只有 \(16\) 个，可以先暴力计算胜负情况（实测复杂度可以承受），然后状压 DP 求解方案数。
代码
F
要 FFT， 先咕咕咕咕