赛时 E 看错题了……
赛时进度：ABCD1D2 Accepted。
赛后进度：All Accepted。
可能会和官方题解做法不同，欢迎 Hack。
A
题意：在一个 01 序列中，至少插入多少个数才能使得任意一段子区间 0 的个数都不超过 1 的个数。
赛时直接降智，还先做的 B 再回来做的 A，实时排名达到了 4000+。
容易发现两个 0 之间至少有 2 个 1，不够的塞满。容易发现这样操作过后，其他区间也是合法的。
B
题意：问有多少个长度为 $n$ 的排列满足：
$T(T\leq 1000)$ 组数据，$n\leq 1000$。
观察样例，发现奇数答案都为 0，考虑从奇偶性入手。
假设 $n$ 是偶数，那么有 $\dfrac n2$ 个奇数，容易发现这些数必须全部放在偶数位置才能保证 $\gcd$ 包含 2。而想要包含更大的质因数，比如 3，只有 $\dfrac n3$ 个位置，却有 $\dfrac {2n}3$ 个数必须放在 3 的倍数的位置，就不可能。
那么 $n$ 是偶数时，所有奇数必须放在偶数位置，那么答案就是 $(\dfrac n2!) ^ 2$。
当 $n$ 是奇数的时候，发现奇数多一个没地方放，所以答案就是 0。
C
题意：给出一个排列，定义一个 $i$ 变换得到一个排列为 $\{p_{n - i + 1} , \cdots, p_n, p_1, \cdots, p_{n - i} \}$，已知 $i$ 变换后的不同的前缀最大值有 $c_i$ 个，问是否存在这样的排列。$\sum n\leq 10 ^ 5$。
我的想法是和题面反过来的，可能略有不适，请谅解。反转后容易转化为 $p$ 开始的循环排列前缀最大值。
首先注意到，假设 $n$ 在位置 $p$，那么 $p$ 这个位置前缀最大值的个数是 1，且没有其他位置前缀最大值个数是 1，因为有一个是自己，有一个是 $n$。
如果 $i$ 的前缀最大值个数是 $c_i$，那么我们可以发现 $i - 1$ 的前缀最大值的个数一定不超过 $c_i + 1$，因为类似于单调栈的，我们会弹出多个元素，但是只会加入一个元素。
那么我们就得到了该排列存在的必要条件了。欲证明其充分性，可以考虑构造一组合法解，像单调栈一样构造，这里不再展开。
注意实现的时候需要反过来（是有点小阴间）
1 | void work() |
D
题意：已知一个区间 $[l, r]$ 和 $a_i\oplus x$，其中 $a_i$ 是一个 $[l, r]$ 的排列，但是 $x$ 未知，要求给出 $x$ 的一组合法解，保证存在。$0\leq l\leq r < 2 ^ {17}$，D1 满足 $l = 0$。
看了一下，似乎和官方题解做法不同。
先考虑 D1 怎么做。都看到异或了，显然是和二进制有关。首先如果 $r + 1$ 是 2 的次幂，那么输出任意一个 $a_i\oplus x$ 都是合法的。否则 $r + 1$ 不是 2 的次幂，那么最高位 $t$ 一定会出现 1 的个数和 0 的个数不同的情况，而且有一边的个数是 $2 ^ t$（因为你把低端的都拿到了），如果是 1 的个数是 $2 ^ t$ 的话，为了把这个数变到 $[0, 2 ^ t - 1]$，我们需要 $\oplus 2 ^ t$。高位的直接递归下去做即可，时间复杂度 $O(r\log r)$。
1 | int solve(std::vector<int> a, int R) |
D2 相对于 D1 来说情况更复杂，主要是存在下界导致不再存在 $2 ^ t$ 这样好的性质了。如果你对刚才的流程比较熟悉的话，你会发现几个问题：
- 还是像刚才一样划分了，如果两边的个数相同怎么办？
- 刚才有一边明摆着不用递归，现在两边都需要递归，如何确保复杂度及正确性？
对于第一个问题，首先我们发现，这样的情况一定出现在类似 $\{2, 3, 4, 5\}$ 这样中间位置恰好是 2 的次幂的时候。可以证明我们现在两边递归都是可以的。因为如果我们翻转过来，其实相当于是在答案上 $\oplus 7$，其实还是正确的。
对于第二个问题，首先由于每一次处理一位，那么每一个数最多遍历 $O(\log r)$ 次，时间复杂度还是 $O(r\log r)$。
对于正确性，我们刚才说到如果 $l\oplus r$（在上一题中是 $r$）是 2 的次幂的话，我们随便返回一个 $a_i \oplus l$ 即可。但是这给实现起来带来了很大挑战。一个比较新奇的做法就是你返回最小的那个 $a_i\oplus l$，他的低位都是 0，然后和其他答案按位或起来，这样两边的答案就可以得到融合。由于题目保证有解，所以肯定不会出现无法合并的解被强行按位或。
这样就可以解决这个问题，时间复杂度 $O(r\log r)$。
1 | int solve(std::vector<int> a, int L, int R) |
E
题意：给定一个 $n\times n$ 的网格，每个网格写了一个 $1\sim n \times n$ 的数字且各不相同。先手选择一个起点，得到该点权值（注意权值并不会消失），然后又后手走。后手选择的点必须满足和前一个点曼哈顿距离 $> k$，可以重复走同一个点。问 $10 ^ {100}$ 步后谁会获胜，或者是平局。输出对于有每一个点，先手选择他开始的最后的结局。$n\leq 2000$。
考虑一个结论：
如果这一步走到的点比出发点权值小，那么走该步的人一定会输。
证明：另外一个人走回去就一定获得正收益。
这启示我们只能往更高点走，谁抢到了最高点谁就获胜。
首先先手如果选择在最高点开始，直接获胜不给后手一点机会。如果选择在距离最高点 $>k$ 的位置，显然后手必胜。但是这么分析后面难度较大，考虑按照权值倒序枚举。
现在我们只能走到已经枚举过的点，如果我们能走到一个先手必败的场面，那么这个点就是先手获胜的，否则就是先手必负的。
如何判断在曼哈顿距离 $> k$ 的位置有没有先手必败的点呢？到这里可以直接二维数点之类的办法，但是 $O(n ^ 2\log ^ 2 n)$ 能不能过有点看人品。
考虑曼哈顿距离的一个有趣结论：$|x_1 - x_2| + |y_1 - y_2| = \max\{x_1 + y_1 - (x_2 + y_2), x_1 - y_1 - (x_2 - y_2)\}$。你可以把坐标系旋转 45 度看看，就可以得到。
剩下的我们只需要找到是否所有先手必败的点和当前点的距离 $\leq k$，那么只需要维护 $\max\{x + y\}, \min\{x + y\}$，$\max\{x - y\}, \min\{x - y\}$ 就可以判断。时间复杂度 $O(n ^ 2\log n)$ 或 $O(n ^ 2)$，注意输入输出效率。
1 | int main() |
F
题意：给定一个长度为 $n$ 的 01 串，选出某些子区间（不能相交），要求长度和为 $m$，且 1 的占比和原串相同。最小化子区间数量并给出方案，或报告无解。
容易发现 1 的个数应该为 $\dfrac{mc_1}{n}$，$c_x$ 表示 $x$ 的出现次数。如果这步时整数，显然无解。
假设我们把这个看作是一个循环的串，那么有 $n$ 个不同的长度为 $m$ 的子串。
结论 1：假设 $n$ 个子串中 1 个数最多有 $mx$ 个，最少有 $mn$ 个，则 $mn\leq \dfrac{mc_1}n \leq mx$。
证明：反证法，如果所有 1 个数都 $<\dfrac{mc_1}{n}$（$>\dfrac{mc_1}n$ 同理），那么把所有的加起来，容易发现所有数被覆盖了 $m$ 次，但是根据这个我们算出一定少于 $mc_1$ 个，矛盾。
这个结论提示我们我们要找的可能只需要一个区间。
结论 2：$[mn, mx]$ 每一个数都有一个对应的子串。
证明：考虑 $mn$ 产生的位置到 $mx$ 产生的位置的这段区间。主义党两个相邻的子串只有一个位置没有重合，也就是说变化量最多只有 1，而最前面是 $mn$，最后是 $mx$，只能一步一步变化，那么每一个位置都能覆盖到。
这说明如果我们可以循环取的话，答案一定为 1。
结论 3：原问题答案不超过 2。
证明：在这 $=\dfrac{mc_1}n$ 的长度为 $m$ 的子串中，每一个最多都只需要原串的 2 段就可以拼起来。
剩下的就很好做了，我们先枚举原串长度为 $m$ 的子串，这些串的答案为 1，需要优先选，然后选择那些循环的串，这些串的答案为 2。容易发现根绝刚才的结论，一定有解。
这样就可以做了，时间复杂度 $O(n)$。实现时可以复制一倍做，很简洁。
1 | void work() |