CF Pinely Round 5(#2161) 总结
A~D
A：每次都取到尽量小（对 \(0\) 取 max）即最优。
B：特判掉 2*2 的情况，剩下的情况只能是一条不断转弯的「斜线」，此时所有点都在两条相邻的斜线上，只需判断 \(x+y\) 的最值，或 \(x-y\) 的最值即可。
C：猜想上界是能够取到的，然后考虑如何构造，可以排序后前后维护一个指针，每次若使前面的指针移动而不跨越 \(X\) 的倍数，则移动前面，否则移动后面。正确性自证。
D： 若最终序列中有值相邻的数，那么一连串值相邻的数组成的一定是不升子序列。设 \(f_i\) 表示考虑完值大于等于 \(i\) 构成的子序列的答案，依次考虑每个值为 \(i\) 的位置，可以从 \(f_{i+2}\) 转移来，也可以从上一个值大于等于 \(i\) 的位置转移来，后者用树状数组维护即可。
E
考虑 \(d[l,r]\) 表示 \(1\) 的个数减 \(0\) 的个数。不妨设 \(d[1,k]>0\)，则 \(s_1=1\)。
- 若 \(d[1,k]>1\) 则显然有 \(d[2,k+1]>0\)，则 \(s_2=1\)。
- 否则 \(s_2=s_{k+1}\)。
扩展到一般情况：
- 找到第一个 \(d[l,l+k-1]=1\) 的位置，则所有 \(i\le l\) 都有 \(s_i=1\)。而所有 \(i\ge l+k\) 都有 \(s_i=s_{i-k}\)。即后面的 \(s\) 都是 \(s[l,l+k-1]\) 的循环。
对此计数即可，枚举上述 \(l\) 的位置，要注意当 \(l>1\) 时 \(s_{l+k-1}\) 不能为 \(1\)，否则 \(l\) 并不是第一个位置。
F
考虑每条边的贡献。若对于一个子树 \(x\)，\(x\) 没有选，而它下面选了若干儿子，那么找到深度最小的儿子 \(v_0\)，最优方案就是 \(v_0\) 与其他 \(v\) 之间连边。
可以 \(O(n^3)\) DP，然后可以优化成 \(O(n^2)\)。
G
看错数据范围以为 \(a_i<2^{30}\)，所以看了题解、听了讲题、想破脑子还是不会做，因为其本身就是不可做的。
正解是考虑【第一步】先把所有 \(a_i\) 变成第一个使得 \(a_i'\&x=x\) 的 \(a_i'\)，【第二步】然后对于使得 \(x\) 不存在的与和为 \(1\) 的位置，我们可以找到最大的这样的位置 \(p\)，然后要找到一个位置 \(q>p\) 然后把一个 \(q\) 为 \(0\) 的位置改为 \(1\)，这样就可以把其低位不存在的 \(1\) 都改成 \(0\)。
【第一步】可以枚举第一个 \(x\) 中包含而 \(a_i\) 中不包含的位置，然后改后面的位置，可以高维后缀和处理 \(a\) 的和与个数。
【第二步】\(p\) 容易计算，枚举改的位置 \(q\)，然后要找到 \(q\) 为 \(0\) 且 \(a_i'\& 2^q-1\) 最大的 \(a_i'\) 将其改掉。