有正能量的分图二（题目记录）

\(01.04\) 分图二

偏知识向的总结在这里。

\(\text{Magic}\)

注意到题目中的区间是左闭右开的，考虑一对数 \((i-1,i)\) 要变成不同的颜色，要么进行一次 \(l=i\) 的操作，要么进行一次 \(r=i\) 的操作。

由于所有的 \(l_i,r_i\) 不重复，那么可以使得 \((i-1,i)\) 拥有不同颜色的区间就最多会有一个。

对于任意两个区间 \(D_1=[l_1,r_1),D_2=[l_2,r_2)\)，若 \(D_1 \cap D_2 = \emptyset\)，则他们的相对顺序不影响结果，若 \(D_1 \subseteq D_2\)，则先操作 \(D_2\) 再操作 \(D_1\) 显然不劣。

当 \(D_1\) 和 \(D_2\) 有交且不包含时，设 \(l_1<l_2\)，如果先操作 \(D_1\)，\((r_1-1,r_1)\) 就会被 \(D_2\) 所覆盖；如果先操作 \(D_2\)，\((l_2-1,l_2)\) 就会被 \(D_1\) 所覆盖。

换句话说就是这两处贡献仅能保留一处，在它们之间连边，不难发现会形成一个二分图，用 \(\text{bitset}\) 优化匈牙利跑最大独立集即可。

\(\text{Blackboard Game}\)

• 数据范围特别大的时候要勇于猜结论。

令 \(w(i)\) 表示 \(i\) 的质因子个数，容易发现边只会连接 \(w\) 的奇偶性不同的两个点，故原图是二分图。

根据 \(\text{UVG}\) 游戏的结论，我们需要找到的即为一个点 \(u\) 满足 \(u\) 为偶数，且存在一个最大匹配不包含点 \(u\)。

暴力建图的复杂度为 \(O(n \log_2\log_2 n)\)，考虑如何在 \(O(n^2 \log_2 \log_2 n)\) 的复杂度内判定所有点是否合法。

先求出该图的任意一组最大匹配，对于不在该匹配内的点一定合法，对于在匹配内的点，考虑从它出发，走一条匹配边 \(-\) 未匹配边 \(-\) 匹配边 \(-\) 未匹配边 \(\dots\) 的路径，如果遍历的过程中能找到一个未匹配点，则起点是合法的，因为可以将这条路径上所有边的匹配情况取反，使得最大匹配不变且起点不在匹配内。否则，如果找不到一个未匹配点，则起点不合法。

那么我们就获得了一个暴力算法，但是依旧难以处理 \(n\leq 10^7\) 恐怖范围。

打表发现，当 \(n\) 较大时是一定有解的，且存在解是某个较大质数的 \(2\) 倍或者 \(3\) 倍。

结论：当 \(n>lim\) 时一定有解，且如果令 \(p\) 为 \(\leq \frac n 3\) 的最大质数，则 \(2p\) 一定是一个合法解。

考虑构造一个最大匹配使得 \(2p\) 不在其中即可证明上述结论：

设存在三个质数 \(a<b<c\)，满足 \(3a<3b<3c\leq n <4a<4b<4c\)，那么就有下图是原图的一个子图：

上方的 \(6\) 个点仅能连向下方的 \(5\) 个点，那么就一定会有一个点不在匹配中，很容易就能构造出一个不包含 \(2c\) 的匹配，故得证。

所以如果能找到三个满足条件的质数 \(a,b,c\)，这个结论就成立，通过代码可以得出结论中的 \(lim\) 取 \(200\) 即可保证正确。

对于 \(n \leq 200\) 的情况直接跑暴力即可。

\(\text{Goblins And Gnomes}\)

• 对于任意最大匹配为 \(p\) 的二分图，至少有 \(p\) 个点被包含在所有最大匹配方案中。

• \(\text{Dilworth}\) 定理。

首先利用 \(\text{Dilworth}\) 定理把原图转化成二分图，那么原限制即为在第 \(i\) 轮中，二分图的最大匹配必须 \(\leq n-i\)。

封锁操作即为在二分图上删掉任意一个点。

先不考虑每一轮具体是怎样进行封锁操作的，只看全局的操作顺序，显然，在第几次封锁哪一个点是一个固定的最优排列。

假设我们已经获得了这个排列，那么就可以进行 \(\text{DP}\)，设 \(f_{i,j}\) 表示前 \(i\) 轮删掉了排列中的前 \(j\) 个点时最大代价是多少，且删掉排列中前 \(j\) 个点之后的最大匹配 \(\leq n-i\)。

转移可以考虑枚举当前轮要删掉多少个点：

\[f_{i,j}=\min_{k=0}^j f_{i-1,k}+\max(0,x_i-(j-k) \times y_i) \]

直接实现是 \(O(n^3)\) 的，使用前缀最大值可以简单的优化到 \(O(n^2)\)，但这并不重要。

接下来考虑如何求出删点顺序。

显然，我们希望删掉点之后二分图的最大匹配尽量小，而删掉一个点之后最大匹配最多也只会减少 \(1\)，有结论：最大匹配不为 \(0\) 时，一定可以找到一个点 \(u\) 被包含在所有最大匹配方案中。

只根据结论，每一轮枚举剩余的所有点，尝试删掉它之后跑匈牙利判断最大匹配是否减小，即可做到 \(O(n^5)\) 的时间复杂度，已经可以通过。

结合证明过程，每轮可以删掉最小点覆盖中的一个点，不用枚举每一个点进行判定，复杂度优化到 \(O(n^4)\)，用网络流可以做到更优。