Codeforces Round 982 (Div. 2)解题报告
A
显然答案不会小于 \(2(\max w+\max h)\)。
构造方案学习样例一，挺明显的。
B
有个小性质（好像没用）：一旦能通过操作变成 non-increasing，再对整个序列操作一次必然变为同一个数字。
我们把一开始 remove 的数字记为A类，通过操作删掉的记为B类，保留的记为C类。
枚举第一个C类的下标，那么它前面的都一定是A类（因为操作不可能删空一个序列），后面的比它大的也一定是A类，其余的是B类最优。预处理每个位置后面比它大的数字个数 \(p_i\)，答案就是 \(\max_{i=1}^n i-1+p_i\)。
C
加进来的零肯定动不了，问题变为每次选一个 \(i\) 使得 \(a_i+i-1=|a|\)，得分和 \(|a|\) 都增加 \(i-1\)，求最大得分。
由于 \(|a|\) 单调不减，能供操作的 \(i\) 一定是按照 \(a_i+i-1\) 升序，而且 \(|a|\) 增加类似转移，这提示我们往 DAG 想。每个点权值为 \(b_i := a_i+i-1\)，连边到所有权值为 \(b_i+i-1\) 的点。用虚拟点辅助连边，bfs即可。\(O(n\log n)\)
D
简单的想法是DP，考虑 \(f_{i,j}\) 表示 \(a[1\cdots i]\) 已被消除，\(b\) 序列到了 \(j\) 的最小代价。则：
\[f_{i,j} \rightarrow f_{i,j+1} \quad s.t. \quad i<n \\ f_{i,j}+m-j \rightarrow f_{k,j} \quad s.t. \quad s_k-s_i \leq b_j \]其中 \(s\) 是 \(a\) 的前缀和。
这样配合使用线段树转移， \(j\) 为第一层循环，每层 \(k\) 枚举的 \(i\) 一定是一段区间，找一个区间最小值。时间复杂度 \(O(nm\log n)\) 可以解决D1。
考虑D2求方案数，维护多一个 \(g_{i,j}\) 以及线段树中维护最小 \(f\) 对应的 \(g\) 之和即可转移，时间复杂度不变。
前四题均不超过蓝题水平，目测cf1900-。
E1
游戏规则就是取石子，但是只能够取当前个数二进制下某子集个，且最多取 \(a\) 个。关键算出 SG 值。
先考虑没有 \(a\) 限制的情况，打表发现 \(SG_i=popcount(i)\) 恒成立。数学归纳法证明如下：
\(SG_0=0,SG_1=1\)
若 \(\forall i<n,SG_i=popcount(i)\)，则：
枚举 \(n\) 的后继 \(i\)，\(n-i\) 的 SG 即为 \(n\) 某个子集的 popcount，且理所当然能够取遍 \(0,1,\cdots,popcount(n)-1\)；至少取走一个，所以取不到 \(popcount(n)\) 以上。得证。
考虑有 \(a\) 限制时，发现 SG 只可能变小。
而且若 \(a\) 最高位为第 \(k\) 位，比 \(k\) 大的位永远取不走，相当于不存在，直接不要了就行。随后看留下的数字 \(x\)(此时 \(x\) 与 \(a\) 位数相同)，如果 \(x\) 小于等于 \(a\)，\(x\) 怎么操作都不受 \(a\) 影响，答案就是 \(popcount(x)\)。
于是只需要处理与 \(a\) 位数相同且 \(>a\) 的 \(x\) 的 SG 值即可。
之后打表猜了几个规律例如： \(a+lowbit(a)\) 以及依次迭代得到的所有 \(a\) SG 值变成0，其它不变；偶数就先加一再开始。但都不是太对。
看题解：发现如果 \(a\) 和 \(x\) 某一位都是 0 那么就可以把这位删掉，\(a\) 是 1 且 \(x\) 是 0 等价于 \(a\) 把这一位变成 0，后面全部变成 1。这样我们就能把 \(x\) 变成 \(2^k-1\) 的形式，只考虑 \(a\) 这一个变量决定 SG 即可。打表容易发现规律(题解有)。
利用此规律求出每堆石子的 SG，E1可通过，时间复杂度 \(O(n\log A)\)
分析为什么我没有做出此题，一方面是对博弈论过于依赖打表，对题目性质分析不够；另一方面是对这里二进制的感觉有些偏颇，看到 \(x\& d=d\) 这种限制就往lowbit这种二进制方向猜结论，就被迷惑了。实际上题解思路更加看重对大小比较的限制，才有了同时删去 0 以及"等价于 \(a\) 把这一位变成 0，后面全部变成 1"这样的关键分析。启发我们要对限制深入研究，总结自己推出来的小结论本质上究竟指向什么。
E2
由于 SG 值有限，数位DP 即可求出每种 SG 的方案数，再异或卷积即可。
DP 大概就是记录当前 \(x\) 到第几位，\(a\) 删了几个 0，是否剩下全为1之类的，用于判断最后的SG。\(O(n\log^2A)\)
标签：log,982,Codeforces,popcount,打表,即可,Div,SG,变成 From： https://www.cnblogs.com/zsj6315/p/18521266