2023.8.24 SM Round

Una. / 2023-08-24 / 原文

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)$。