题解 CF1322C 【Instant Noodles】

QwQcOrZ · 2021-05-26 21:41:00 · 题解

看了好久官方题解才看懂，感觉这个证明方法好牛啊。

我来搬运一下官方题解，顺带说明一下它讲得不是很清楚的地方。

记 H_i 表示与第 i 个右部点有连边的左部点的集合。

考虑将右部图的点分成几组，使每组的店都具有相同的 H_i。

然后，答案等于每个组中 c_i 之和的 \gcd，H_i 为空集的组除外。

让我们证明一下这为什么是对的。

如果某些右部点具有相同的 H_i，则对于每个集合 S 它们都将在 N(S) 中（N(S) 的含义在原题中），或者都不在 N(S) 中。

这意味着我们可以将同组的所有顶点替换为权值等于这些顶点的 c_i 之和的一个顶点。

之后，所有顶点中的数字都可以被答案整除（这里的答案是指由上面的结论得出的答案，即替换后每个顶点权值的 \gcd，所以可以整除），因此选出某些 c_i 后它们的总和也一定可以被答案整除。

所以可以将所有权值除以答案，然后证明答案为 1。显然这和原问题等价。

考虑对于某个整数 k>1，证明一定有方案能找到一个左部点集合 S，使得f(S) 不能被 k 整除（f(S) 的含义依然在原题题面中）。

如果权值的总和不能被 k 整除，显然可以直接选上所有左部点。

因此只需要证明权值的总和能被 k 整除的情况。

考虑找到一个最小度数的右部点 v，使其权值不能被 k 整除（存在该顶点是因为右部点权值的 \gcd 现在为 1，如果找不到显然 \gcd 都为 1）。

于是我们选择 H_v 的补集，可以发现与它有连边的右部点的权值和一定不能被 k 整除。

为什么？考虑哪些右部点与该集合没有连边，首先 v 一定是，还有 H_i\subset H_v 的所有 i（每个 i 的权值都一定可被 k 整除）。但是 v 的权值不能被 k 整除，而 H_v 的补集的答案显然为总权值和减去这些没有连边的点的权值，得证。

至于为什么都可以每个 i 的权值都一定可被 k 整除，首先 H_i=H_v,i\not=v 的情况是不存在的，因为这样他们一定会合并为一个点。考虑如果存在一个 i 使得 H_i\subset H_v 且 i 的权值不能被 k 整除，那么它的度数小于 i。由于我们选的是度数最小的点，所以这种情况不可能出现。

直接按照结论计算，用哈希合并即可。