【题解】XX Open Cup, GP of Moscow

// created on 23.03.26

• A. Alice and Bob
• B. Brackets
• C. Circles
• D. Deja Vu
• E. Easiest Sum
• F. Funny Salesman
• G. Graph Coloring
• H. Hidden Graph
• I. Insects
• J. Joining Points

A. Alice and Bob

对于链上的情况，异色点是一定不会选择走进同色段的（长度不小于 \(2\)），因为一定不优。所以，可以倒着 DP，求助每个点的优势步数（即走多少到同色段的最后，然后接下来是黑白相间的链；链过后如果还是同色，就再 \(+1\)，表示可以消耗一手，否则没法小号）。将这个 DP 放在 DAG 上，每次选择最优的决策即可。剩下的交给背包。

提交记录：Submission #90996 - QOJ.ac 。

B. Brackets

我们考虑如下贪心过程：先假装所有位置都是 )，每次尝试改一对 ( 并检查后缀和，如果后缀和仍然都 \(\leq 0\) 那么合法，否则非法。

我们只需要证明：如果后缀和合法，并且原序列有解，那么改成 ( 仍然有解。假设这两个位置为 \(i,j\)，如果我们可以找到 \(i<i',j<j'\) 满足 \((i',j')\) 选择了 (，那么交换匹配不劣。否则因为后续必有 )，所以只有 \(i<i'<j'<j\) 的 \((i',j')\) 选择了 ( 。此时交换匹配，检查后缀。

然后你发现，此时检查后缀，和插入 \((i,j)\) 时检查后缀并无区别。仍然是合法的，因此交换仍然合法。

提交记录：Submission #91002 - QOJ.ac 。

C. Circles

线性规划对偶。不难发现到一个变量的取值只会是 \(0/1\)（调整可证），所以直接 DP 即可。

提交记录：Submission #91022 - QOJ.ac 。

D. Deja Vu

等下。

算了。

E. Easiest Sum

考虑二分 \(w\) 计算 \(\leq w\) 需要的最小限制次数，设为 \(A(w)\) 。注意到 \(A(w)\) 是 \(O(n)\) 段的函数。将 \(a\) 做前缀和，操作变为后缀减。相当于每次维护 \(L(w)\rightarrow \min(L(w),a_i+w)\)，然后若 \(a_i>L(w)\) 就要操作 \(a_i-L(w)\) 次。将后缀减变成前缀加，遇见 \(a_i>L(w)\) 时，只需要令 \(L(w):=a_i\) 即可。

算好 \(A(w)\) 的转移，再统一转移 \(L(w)\rightarrow \min(L(w),a_i+w)\) 。注意到 \(L(w)\) 也是分段函数，只需要拿栈维护每一段即可。模拟的时候将 \(A(w)\) 的修改处理出来，最后排序统一处理即可。

提交记录：Submission #91024 - QOJ.ac 。

F. Funny Salesman

从高位开始贪心，每次递归到可能仍然存在的最大连通块即可。

提交记录：Submission #91037 - QOJ.ac 。

G. Graph Coloring

\({14\choose 7}\geq 3000\)，所以给点标号，每次只要挑选一位是 \(0\rightarrow 1\) 即可。正确性显然。

提交记录：Submission #91039 - QOJ.ac 。

H. Hidden Graph

考虑一个合法图，每次删度数最小的点，删的时候与剩下部分相连都不超过 \(k\) 条边 —— 这明确指向，我们可以通过这样的方式给图染色，将图分成 \(k+1\) 个独立集。

于是，考虑增量。每次加入 \(i\) 时，将 \([1,i-1]\) 划分独立集，然后每个独立集单独询问即可。因为独立集个数至多为 \(k+1\)，所以代价不超过 \(nk+n(k+1)\) 。

提交记录：Submission #91053 - QOJ.ac 。

I. Insects

将题意转化为求白色点字典序最小最大匹配（黑点是原来点，白点是加入点），称之为最优匹配。显而易见，前缀答案大小不可能比最优匹配大（否则替换）。

接下来给出一种通用做法：如果对于一张二分图，可以花一定代价求出任意一组最小割，那么可以以多一个 \(\log n\) 的代价求出最优匹配。

在此之前对最小割做定义：我们求出任意一组最大匹配，然后从左部，非匹配点出发。将可以到达的点全部加入队列，然后遍历。最后访问过的点称为左集，没访问过的称为右集。而两者在左部和右部的点集，将标注下角标。

设计 \(F(S_1,S_2,S_3)\) 表示 \(S_2<S_1\) 且左部为 \(S_2\cup S_1\)，右部为 \(S_3\)，并且 \(S_2\) 一定在最优匹配中。答案就是 \(F(L,\empty, R)\) 。此时将 \(S_1\) 分成 \(X,Y\) 两部分且 \(X<Y\)，我们求出 \((S_2\cup X,S_3)\) 的最小割，记为 \((A_l,A_r),(B_l,B_r)\) 。注意到以下事实：

• \((B_l\cup Y,B_r)\) 的最优匹配一定包含 \(B_l\)：因为 \((B_l,B_r)\) 的最优匹配已经包含 \(B_l\)，考虑匈牙利增广即可。
• \((S_2\cup X,S_3)\) 的最优匹配由 \((A_l,A_r)\) 和 \((B_l,B_r)\) 的最优匹配构成：因为 \(A_l,B_r\) 之间没有边，而 \(B_l,A_r\) 之间的边一定会让最短路变小（\(B_l,A_r\) 都全在最大匹配中）。所以剩下的边都不是匹配边。
• \((S_1\cup S_2,S_3)\) 的最优匹配由 \((A_l,A_r)\) 和 \((B_l\cup Y,B_r)\) 的最优匹配构成：考虑从 \((S_2\cup X,S_3)\) 增广，因为 \(A_r\) 已经全都在最大匹配，所以增广路不可能进入 \(A\) 。

于是，\(F(S_1,S_2,S_3)\) 由 \(F(A_l\cup S_1,A_l\cup S_2,A_r)\) 和 \(F(Y,B_l,B_r)\) 构成。容易发现一个点恰好递归到一侧，且 \(S_1\) 大小减半，因此递归树深度 \(O(\log n)\) 。

求最小割是容易解决的：从右到左贪心地找一组最大匹配。然后从每个非匹配白点出发，尝试访问剩下的点。这个可以通过对点建线段树，快速处理。

提交记录：Submission #91243 - QOJ.ac 。

J. Joining Points

枚举 \(1\) 的覆盖情况，剩下的部分直接 DP 就行了。