2023.8.24 LGJ Round
A
有 \(n(n\le 750)\) 个正整数 \((a_i\le 10^9)\)，你需要删除一些数，使得剩下的数两两加起来都不为质数。
若 \(a_i+a_j\in \text{prime}\)（这里使用 Miller-Rabin 即可），将 \(i\) 和 \(j\) 连边。
我们就是要求一个最大独立集。
一般图是求最大独立集是 NP 问题。但是我们发现去掉所有 \(a_i=1\) 到只剩一个后，原图是二分图。
奇数在一边，偶数在一边，我们求二分图最大独立集=点数-最大匹配。
B
一个网格图 \(n,m\le 3000\)，每个点可能是炸弹，水晶，或者空地。
引爆一个炸弹时，你可以选择其所在的行或列其中一个，使得其中的水晶被炸掉，且引爆其中的所有炸弹。
你一开始可以引爆任意一个炸弹，求最多炸掉的水晶。
首先现将一个炸弹的行和列通过并查集合并，代表其中一个被引爆，另一个也会被引爆。
考虑处理联通块。
若这个联通块是树的形式。我们发现炸弹的数量=联通块里行和列的总数-1。
那么有一行或一列不被引爆，枚举叶子节点即可。
不是树的形式呢，那么所有行和列都能被引爆，所以直接计算贡献即可。
C
一个网格图 \(n,m\le 1000\)，每个点可能是棋子，障碍或空地。
Alice 和 Bob 玩游戏，Alice 先手，
每次行动选择一个棋子，可以向左，向右，或向下移动，不能经过障碍物，不能经过当前这个棋子层经过的所有点。
每个点可以容纳多个棋子。
每行的第 \(1\) 和第 \(m\) 个点是可以互相到达。
无法行动的人算负。
SG 函数？
D
一棵树 (\(n\le 2\times 10^6\))，每个点有 \(a_i\) 个人，老板在 \(1\) 号节点。
员工速度为 \(2\)，老板速度为 \(1\)。
询问每个点，要每个人都到达这个点，有多少个人能比老板先到。