COCI 2020.3 基础算法

写了一下 COCI 2020 年 3 月的 T3~T5，这套题主要涉及到的都是基础算法，下面进行一些总结。 ### [Konstrukcija](https://loj.ac/problem/3268) 一道十分毒瘤的构造题，但体现了一些算法思想。 首先要想到一种可以在不大的花费下得到指数级别矛盾值的方案，我构想了一种把“交错”叠起来的方案。 然而这种方案十分昂贵，大概需要 $540$ 条边，不可能建造很多个这样的“塔”。这里就体现了算法思想——重用。一个塔可以通过许多方法重复利用，而重复利用的“插件”也大有讲究——总之要思考的点非常多。 总之，考试时这道题就写个部分分是比较划算的。 ### [Skandi](https://loj.ac/problem/3269) 算是复习图论知识盲点吧。 看到这道题，我一开始想到用 dp，但似乎没有太好的思路。接着我就想到了图论建模，能影响每个点的只有上方和左方的两道题，似乎可以建图。 这里应该抓住一个关键——“两个”。“两个”是十分特殊的条件，因为一条边有“两个”端点！涉及到“两个”的问题，可以考虑把它弄成边。 这里也是这样。一个空白点可以看作与它关联的两道题之间的一条边，并且根据条件，这两道题之中至少要写一题。 这里的特征其实很明显了，这其实就是最小点覆盖问题——选最少的点，使得每一条边都至少有一个端点被选。 条件还没有发掘完毕。题目分为两种——横和竖，而与每个空白点关联的恰好是一道横题和一道竖题，也就是这个图是二分图！ 于是这道题就被破解了，其实就是二分图的最小点覆盖问题。 根据 König 定理，二分图的最小点覆盖等于最大匹配，因此我们就可以轻松输出答案数了。 但这是一道毒瘤题，还要输出方案，怎么办呢？[Matrix 67 的博客](https://www.matrix67.com/blog/archives/116) 给出了方法，这同时也是 König 定理的一个证明。 首先，我们说明最小点覆盖 $\ge$ 最大匹配。假设最大匹配数为 $m$，那么图上就存在 $m$ 条不相交的边，覆盖这 $m$ 条边一定需要至少 $m$ 个点，因此最小点覆盖 $\ge$ 最大匹配。 接下来，我们构造一种方案，用 $m$ 个点完成整个图的点覆盖，这也就证明了上面不等式的等号可以取到，也就完成了定理的证明。 我们先思考一下，这 $m$ 个点应该是什么样的点。根据上面的讨论，最大匹配中的 $m$ 条边都要被覆盖，因此至少要选择 $m$ 个匹配点，才能完成点覆盖，而且同一条匹配边的两个端点还不能同时选中。但是总共我们也就只能用 $m$ 个点了，因此我们知道，最终的这 $m$ 个点一定都是匹配点，而且每条匹配边恰有一个端点被选中。 对最后的结果有了大概的把握，我们开始看算法的过程。在下面这个算法中，有着“循环不变式”，即我们一直保持这个性质 $P$ 成立：当前所选的点一定能完成点覆盖。 初始时，我们选择左半的所有点，（同时不选右半的任何点，）这样肯定能够保证性质 $P$ 成立。 接着我们想通过调整选择的点，达到“只选 $m$ 个点”的目标，当然调整的过程中一直要保持性质 $P$ 成立。 我们枚举左半的点，当遇到一个非匹配点 $x$，且 $x$ 当前被选中时，我们就要警醒了—— $x$ 是非匹配点，到最后一定不能被选中，所以现在不改，更待何时？马上取消点 $x$ 的选中状态！ 但是这会引起问题，性质 $P$ 可能就不成立了。假设有一条边 $x-y$，原先是 $x$ 以一己之力维持的，取消 $x$ 的选择后这条边不就成了孤儿了吗？ 思考一下，上面的 $y$ 可能是非匹配点吗？——怎么会呢？两个非匹配点怎么可能有边直接相连啊（否则不就可以继续匹配了吗）？所以我们知道，$y$ 一定是匹配点。 那么接下来的事情就比较顺理成章——由于最终选的点都是匹配点，那么在取消 $x$ 的选择的同时，改选匹配点 $y$，这当然是向着成功的方向进行的——正所谓“前途是光明的”。 因此，在取消 $x$ 的选中后，要同时找出与 $x$ 相连的所有匹配点 $y$，如果 $y$ 没有选中，就要把 $y$ 选上了。而且，这个 $y$ 是最后**必选**的，也就是今后不管怎样都不会取消掉 $y$ 的选择——因为今后永远都不会再去选 $x$，为了保证边 $x-y$ 的生存，$y$ 一定要坚持住啊！（雾） 选中了 $y$，又会带来另一个问题——浪费问题。由于 $y$ 选上了，那与 $y$ **相配**的匹配点 $z$ 就不能选了——因为最终“每条匹配边恰有一个端点被选中”。 于是我们又需要取消掉 $z$ 的选择。这和取消 $x$ 的选择是类似的，又会带来“性质 $P$ 不成立”的问题，需要找出右边所有与 $x$ 相连且没有被选的点 $y'$，把 $y'$ 选上。 现在问题又来了，你说要选 $y'$，那 $y'$ 万一是非匹配点怎么办？这岂不是让我永久地选择一个非匹配点？ 好消息是，这种情况不会存在。我们一开始是从 $x$（非匹配点）出发，来到与 $x$ 相连的匹配点 $y$，再考虑与 $y$ **相配**的匹配点 $z$，又从 $z$ 来到与 $z$ 相连的 $y'$。如果 $y'$ 是非匹配点，这岂不是意味着 $x\to y\to z\to y'$ 是一条增广路吗？那又可以继续匹配了，就与“最大匹配”矛盾。因此，这样找到的 $y'$ 一定是匹配点，可以放心选中。 选了 $y'$，又要消除与 $y'$ 相配的点的选择……如此下去，直到调整完毕。 对 $x$ 调整完毕后，再找左半的下一个非匹配点，直到遍历完左半的所有非匹配点。 整个过程中，我们就做了两件事——取消左半的某个点（可能是匹配点或非匹配点）的选择、选中右半的某个匹配点。而且在算法的最后，左半的所有非匹配点都被取消了，而且我们从来没有选中过右半的非匹配点，因此最后选中的所有点都是匹配点。 在算法中，只要选中右半的一个匹配点，我们就会取消掉左半与它相配的匹配点的选择，如此反复；因此，算法过程保证了“每条匹配边恰有一个端点被选中”。 根据这两条——选的全是匹配点，且每条匹配边恰有一个端点被选中，我们可以知道最终选择的点数是 $m$——这就构造完成了。 分析上面的算法，每个点的选中与否只会改变一次，因此复杂度为 $\mathrm{O}(n)$ 级（这个复杂度中没有考虑图的边数）。 这个方案构造的代码实现其实很简单，像下面这样就好了（下面代码中 `[0]` 表示左半，`[1]` 表示右半）。 ```cpp // 调用前把所有 labels[x][0] 设为 1，也就是选中左半的所有点 void dfs(int x){ //labels[x][0/1] 表示左/右半的 x 点是否被选中 labels[x][0]=0; for (auto v:g[x]){ if (labels[v][1]) continue; //如果已经被选中了就不需要再调整了（这个判断能防止无限递归） labels[v][1]=1; if (labels[invmat[v]][0]) //只有被选中了才需要调整 dfs(invmat[v]); //invmatch[v] 表示与右半的 v 点相配的匹配点 } } ``` ### [Trener](https://loj.ac/problem/3270) 这道题的题意需要结合样例理解，问的是“想组成一支球队，有多少种不同的方案”，并不是“最多把这些球员分为多少支球队（且一个球员不能同时处在两支球队中）”。前者 dp 即可，后者也许是最大流。 题目中“每个球员的姓氏必须为姓氏比他长一个字符的那个球员的姓氏的连续子串”这个条件告诉我们，这题其实不难。考虑姓氏较长的那个球员，假设他的姓氏长度为 $t$，那么姓氏较短的球员的姓氏一定是这个 $t$ 长字符串的 $t-1$ 长连续子串——这不只有 $2$ 个吗？ 因此我们枚举这两个子串，看有多少个以这个子串为姓氏的球员（可以用哈希或 Trie），dp 即可；或者说在长姓氏和相应的短姓氏之间连有向边，做路径数量计数。 注意，因为是“姓氏”，所以存在姓氏相同的球员很正常（存在姓名相同的球员其实也不奇怪）。