A
如果满足条件可以注意到一定有 $a_i = a_{i+k} = a_{i+2k} = \ldots$,所以先判断这个,然后只需要判断 $[1 \ldots k]$ 能否被填成平衡的串即可。
B
如果先手一步能抓住后手,那么先手必胜。
如果 $db \leq 2da$,那么一定存在一个时间后手被先手逼到角落里但是后手无法通过向先手的范围跳跃而跳出攻击范围。
那么按照后手的意愿,先后手最后的稳定状态一定是在直径上反复横跳,但是如果直径长度 $\leq 2da$,那么整个数都能被先手覆盖到,也没了。
其他的情况后手可以一步跳出先手的攻击范围,所以先手必败。
C
首先考虑不带修改怎么做:设 $f_i$ 表示考虑了前 $i$ 个元素,最大能删除多少个。
如果 $a_i < i$ 那么 $f_i = f_{i-1}$(永远不能匹配上)
否则如果 $f_{i-1} \geq a_i-i$,我们可以先缩小前面的 $a_i-i$ 个元素,这时候 $a_i$ 正好在 $i$ 上,然后在缩剩下的就行,所以 $f_i = f_{i-1}+1$。
对于区间询问 dp 问题要么考虑矩阵维护转移(这个题显然不行),要么考虑离线+枚举右端点维护左端点答案。
我们枚举右端点,考虑维护所有左端点的答案,遇到一个新的点相当于让所有 $f_{i} \geq a_i-i$ 的点加一,发现 $f$ 单调,所以修改的一定是对应的一个后缀,可以二分出来。树状数组+二分或者线段树二分可以得到 $O(n \log^2 n)/O(n \log n)$ 的复杂度。
D
神仙构造题。
这种让你自由选择先后手的一定是某些情况先手必胜某些情况后手必胜。
如果 $n$ 是偶数那么先手必胜:因为注意到 $\sum_{i=1}^n i = \frac{n(n+1)}{2} \equiv \frac{n}{2} \pmod n$,所以我们如果配对 $(i,i+n)$,每次变化量只能是 $n$,和 $\bmod n$ 的值一定都是 $\frac{n}{2}$,也就永远不能是 $2n$ 的倍数。
如果 $n$ 是奇数那么后手必胜:首先注意到 $\sum_{i=1}^{2n}i = n(2n+1) \equiv 0 \pmod n$,所以 $\bmod 2n$ 的值只有可能是 $0$ 或 $n$。我们在题目的限制上新增限制 $(i,i+n)$,首先观察每个点的度数是 $2$ 所以形成了若干个环并且不存在奇环,所以可以通过染色求出一组方案,因为方案是根据总和减掉若干个 $n$ 得到的,所以现在的方案 $\bmod 2n$ 可能是 $0,n$,如果是后者的话取补集即可(因为两种方案的增量的和是 $\bmod 2n = n$ 的,所以另一个一定 $\bmod 2n = 0 $,所以一定存在一个集合满足条件)。
E
原题。
首先让每个黑格子都单独染一次,现在考虑将一块的贡献在边界算掉。
每个点状态只要上下连和左右连,这提示我们使用最小割。
考虑这个点周围的所有点:如果是白色点相当于选择这个点指向这个白色点的位置贡献会被算上这个方向白色点的方向;黑色点如果相邻不同状态答案也会 $+1$,经典最小割建模。
看完这个题真的后悔没打。。。