A

在 \(n\) 个数中选尽可能多的数，使得任意两个数之和不是质数

质数只有 \(2\) 是偶数，那么只有 \(1+1\) 和 奇数加偶数 能产生质数

因此首先把 \(1\) 删除到只剩一个。这个 case 在有拍情况下卡掉了 cls（

建最小割的图，源点连奇数容量 \(1\) 的边，偶数连汇点容量 \(1\) 的边，如果两个数相加为质数就将两者连一条奇数向偶数的边、容量无限，跑最小割即可。

用 Miller_Rabin 判断素数，经验证只需 \(2、3、5、7、11\) 五个底数即可查清 \(2\times10^9\) 以内的质数。

B

考虑每个炸弹向它上下左右的第一个炸弹连边，这样就连出了若干个连通块，这样我们可以单独考虑每个连通块，因为它们之间不会引爆。

若一个连通块有环，那么只要引爆环中的一个炸弹，就可以把这个连通块涉及到的所有行列都引爆，获得这些行列上的所有水晶；若没有环，那么当块最优解一定是选择某个左右／上下没有其它炸弹的炸弹，将它竖着／横着引爆，对比上一种情况，这样最多只会损失掉某一行或某一列的水晶，减去这些即可。

时间复杂度 \(O(nm)\)。

C

注意到有很多起点，这迫使我们求出每个位置的 SG 函数异或起来。

这里有一个难的地方，如何规避移动到重复格子。这仅仅在一行内没有任何障碍时可能发生，在朴素情况下这个东西也需要记录到一个局面的状态中，也就是状态要加上当前行已经走过的区间（其中一个端点必然为当前点），变成 \(O(n^3)\) 复杂度。

因为从下一行递推上来时，我们并不关心这个第三维，考虑优化为：\(f_{i,j}\) 表示上一步来自 \(f_{i-1,j}\) 或者此为起点时的 \(sg\) 函数。

若行内有障碍，那么一定只能走单一方向，且这样不会走回重复格子。因此 \(f_{i,j}\) 可以从左到右、从右到左分别直接递推。不能直接递推 SG 函数值，而是把 \(f_{i,j}\) 对应的所有后继状态处理出来。

Trick：一个点 SG 函数的上界等于出度。本题中是小常数 \(2\)。

注意到算 \(f_{i,j}\) 时，\((i,j)\) 可以看作行内的一个额外障碍。遍历 \(j\) 套用上面的做法是 \(O(n^3)\)，考虑加速这一过程，注意到 SG 值不超过 \(2\)，因此可以预处理出这样的一些信息：当 \((i,j)\) 的 SG 值为 \(v\) 时，一路向左边或右边推，位置 $(i,1) 或 \((i,m)\)的SG值为多少； 以及当位置 $(i,1) 或 \((i,m)\) 的SG值为v时，一路向右或向左推，到 \((i,j)\) 时的SG值为多少。即可 \(O(1)\) 计算每个位置的 SG 值。时间复杂度 \(O(nm)\)。

D

\(72pts\)：P6329，直接点分树维护 \(dis\le k\) 邻域和，用总和减去之。

正解：这个需求的距离 \(k\) 其实是有性质的。考虑以特殊点 \(1\) 为根时，指定了某个点 \(x\)，那么其子树内有贡献的点是 \(d_y>2d_x\) 的 \(y\)；子树外有贡献的是 \(d_y>d_x\) 的 \(y\)。

所以我们直接拆成三个询问，长链剖分就可以了？