CF1920

SC 真的在认真写喵，关注 Sugar_Cube 喵。（）
A 没价值，略去。

B

给定一个可重集合，A 选择至多 k 个数删除，然后 B 在剩下的数选至多 x 个取相反数。
A 想要和尽量大，B 想要和尽量下，求两者都使用最佳决策的情况下的结果。
\(n\le 10^5\)

假如确定了删除哪些数，B 肯定是尽量取反大数，故答案是剩下的和减去 2 倍的前 x 大之和。
而 A 如果删不是前 x 大的数，对 B 没有影响，只能删是前 x 大的数，那么贪心地删最大的那个数。
注意到，删了可能不优，所以我们枚举 A 删了多少个数，找最大值即可。

C

给定一个长为 n 的数字串，对于 n 的每个正因子 k，把该串分为 \(\frac{n}{k}\) 个等长为 k 的子串。
称当前的这个划分是合法的，当且仅当存在 \(m\ge 2\)，使得 \(a_i\bmod m\) 在该划分下存在长为 k 的循环节。
求合法划分数。
\(n\le 2\times 10^5\)

以为是分析性质，没想到直接暴力做就可以了。

考虑枚举所有 \(k\)，想办法在 \(\mathcal O(n)\) 时间内计算出是否存在 \(m\)。
若 \(a\equiv b\pmod m\)，则有 \(m|(a-b)\)，故只需计算出所有 \((t_{i}-t_{i+k})\) 的最大公因数，判断其是否 \(\neq1\) 即可。
由于辗转相除的性质，直接写 gcd 复杂度就是对的。
代码

D

通过 n 步操作生成一个序列，初始序列为空：
向序列末尾插入 \(x~~(1\le x\le n)\)。
将序列整体复制 \(x~~(1\le x\le 10^9)\) 份插入序列末尾。
之后有若干次对该序列某个位置的值的询问，保证询问位置合法。
\(n,q\le 10^5\)

注意到两种操作都是插入，故一次询问只与一个前缀的操作有关。
我们二分出生成询问位置时的那次操作，如果是单点插入那么已经做完了。
否则我们可以把询问位置对于该操作前的序列长度取模，那么只需解决该子问题。
发现这样询问位置至少减少一半，所以复杂度是对的。

E

称一个 01 串合法当且仅当其恰好包含一个 1。
要求对满足恰好有 n 个合法子串，且最长合法子串 \(\le m\) 的所有 01 串计数。
\(n,m\le 2500\)

下次优化前记得先把转移式写出来。

对于一个 1 来说，设它左右的 0 的个数分别为 \(l,r,~(l+r+1\le m)\)，则包含它的合法子串数为 \((l+1)(r+1)\)。
故我们对 01 串和 0 段序列构造双射，问题变为：
对于非空序列 \(a\)，满足 \(\sum\limits a_{i}a_{i+1}=n,a_{i}+a_{i+1}\leq m+1,a_{i}\geq 1\)，对其计数。
直接考虑背包，朴素的状态设计为 \(f_{i,j,lst}\) 表示当前序列长度，当前 \(\sum\limits a_{i}a_{i+1}\)，与上一个 \(a_{i}\)，转移：
\(f_{i,j,lst}=\sum\limits_{p} f_{i-1,j-lst\times p,p}\)。
注意到转移式与 \(i\) 无关，且原本的转移就是一个 DAG，不需要分层，故可把 \(i\) 这维删去。
再考察转移范围得到：
\(f_{j,lst}=\sum\limits_{p=1}^{\min(m-lst,\lfloor \frac{j}{lst} \rfloor)}f_{j-lst\times p,p}\)。
枚举 \(p\) 的复杂度为一个调和级数，所以直接转移就对了。
代码

F

Luogu
给定一个网格，格子有海水，火山和岛屿。
保证岛屿构成一个四连通块，所有火山和海水构成一个四连通块。
有若干次询问，每次询问对于一个点 \((x,y)\)，走四连通的只走海水或火山的回路，且这个回路必须绕岛一周。
要求最大化路径上任意一个位置到最近的火山曼哈顿距离的最小值。
\(3\le n,m\le 10^5,9\le nm\le 3\times 10^5\)
Easy Version：\(q\le 5\)
Hard Version：\(q\le 3\times 10^5\)

思路解析

使用思维树，抓住关键的地方进行思考。
充要条件转化，大胆猜想。
使用思维上的近似转化为已知问题。
好好读题（）

Easy Version

抛弃曼哈顿距离的性质，通过一次多源 bfs 求出所有非岛格子到最近的火山的距离，作为其权值。
二分，只保留那些权值足够大的格子，考虑怎么判是否存在绕岛一周的路径。

每个岛屿方块的四个方向上都存在一个路径格子？
看起来非常没有前途。
考虑正难则反，考虑什么时候无解，发现此时必然存在路径经过那些不合法点且能从边界连到岛上。
不合法点指要么权值小，要么无法从起点到达，连接显然是八连通。

Hard Version

感觉关键点仍在判环岛上，但是上面的判断方法看起来没有一个非过程化的转化前途。
考虑回退思路到二分前。

考虑原图实际上与一个环拓扑同构，上面的判断方法可以理解为不存在一个环上的点不可选。
那我们考虑 破环成链，在原问题上对应着考虑任意找一条岛屿格子边界到网格边界的简单路径，称其为分割线。

Conclusion：如果任意找一条分割线，则任意简单回路绕岛一周，当且仅当它经过该分割线恰好奇数次。
Prove：
必要性画图显然，充分性注意到环分割后是一条链，那么把经过分割线奇数次的部分拿出来，剩余部分只能是一条链，所以合法。（感觉不如直接画个图发现没有反例）
值得注意的是，所有经过分割线偶数次的路径一定不是简单回路，手玩一下容易证明。

那么我们任选一条分割线，直接考虑拆点，每个点拆为经过奇数次和经过偶数次。
我们的询问就是 \((x,y,0)\to (x,y,1)\) 的瓶颈最大路。
于是直接 Kruskal 重构树即可通过 Hard Version，在线单 \(\log\)。

此外，该问题也可以通过离线整体二分和启发式合并解决。