题解 P6775 【[NOI2020]制作菜品】

> 这篇题解将给出详细的证明。如果我能拿到自己考场代码应该会贴（不过看起来希望渺茫）。 看到题目感觉无从下手。观察数据范围，发现一个奇怪的限制 $n-2\leq m$，而且还专门给出了 $m=n-1$ 和 $m\geq n-1$ 的部分分，我们不妨从此入手思考。 对于 $m=n-1$，枚举 $n=2,3$ 发现都一定有解。我们不妨尝试直接将 $n$ 向 $n-1$ 转化：不失一般性，令 $d_1\leq d_2\leq \cdots\leq d_n$。我们发现应该要尽量先用光少的那些材料，而且少的尽量要配大的。可以证明下面两条引理： **引理一：**$d_1 < k$。 **证明：** 用反证法。假设 $d_1\geq k$，那么 $d_2,...,d_n\geq k$，则 $d_1+\cdots+d_n\geq nk>(n-1)k=d_1+\cdots+d_n$。显然矛盾，故命题得证。 **引理二：**$d_1+d_n\geq k$。 **证明：** 用反证法。假设 $d_1+d_n\leq k-1$，那么 $d_n\leq k-1-d_1$，则 $d_1+d_2+\cdots+d_n\leq d_1+(n-1)(k-1-d_1)=(n-1)k-(n-1)-(n-2)d_1 < (n-1)k$，矛盾，所以 $d_1+d_n\geq k$。 综合上面两条引理，我们可以一次把 $d_1$ 用光，同时用 $d_n$ 填补空缺，显然是可行的。这样就成功将 $n$ 的情况转化成了 $n-1$ 的情况。而 $n=2$ 时直接放一起即可。综上，我们成功对于 $m=n-1$ 的任意情况构造出了一组解。 直接模拟的时间复杂度为 $O(n^2)$；可以简单用数据结构优化到 $O(n\log n)$，虽然本题中没有必要。 ------------- 对于 $m\geq n$ 的情况，考虑向 $m=n-1$ 转化。同上令 $d_1\leq \cdots\leq d_n$，显然可证 **引理三：** $d_n\geq k$。 **证明：** 如果 $d_n < k$，则 $d_1+d_2+\cdots d_n < nk\leq mk=d_1+d_2+\cdots d_n $。矛盾。 所以我们用 $d_n$ 单独做一道菜，就可以令 $m$ 减少 $1$。这样就转化为 $m=n-1$ 的情况了。时间复杂度 $O(mn)$ 或 $O(m\log n)$。 ------------- 接下来是最后的部分：$m=n-2$。 先手推一下 $n$ 较小的情况，发现 $n=3$ 必定无解，$n=4$ 是有解当且仅当存在两个 $d$ 加起来等于 $k$。也就是说，我们似乎要将这个问题向 $m=n-1$ 转化；把 $n$ 个物品分为两个集合，如果两个集合都能找到 $m=n-1$ 的方法，那么加起来就有一个 $m=n-2$ 的方法了。也就是说 **引理四：** 问题有解当且仅当能找到一个集合 $U=\{1,...,n\}$ 的子集 $S$，使得： - 记 $x=|S|$ 为 $S$ 的大小，则 $\sum_{i\in S}d_i=(x-1)k$。 **证明：** - **充分性：** 显然对于集合 $S$ 和 $T=U-S$，都是一个满足 $m=n-1$ 的子问题，而我们已经证明过了 $m=n-1$ 必定有解，则对 $S,T$ 分别构造解即可。 - **必要性：** 考虑构造一张图 $G$，$G$ 中有 $1,...,n$ 这些节点，如果两种原料在一道菜里同时选用则连一条边。发觉 $G$ 中至多有 $n-2$ 条边，则 $G$ 一定不连通。设 $G$ 有一个连通块 $S$，则相当于 $S$ 必须满足 $m=n-1$ 的有解约束，即 $\sum_{i\in S}d_i=(x-1)k$。证毕。 总之，只要我们能找到一些物品的集合 $S$ 满足 $\sum d=(|S|-1)k$，就能构造出符合题意的解。如何求这个 $S$ 呢？显然考虑做背包 DP。而由于右边带了一个 $|S|$，我们再做一步转化，将 $|S|k$ 移到左边，即要求 $\sum (d-k)=-k$ 这样就变成一道经典的 01 背包问题了。直接求解的时间复杂度为 $O(n\sum d_i)=O(n^2k)$，用 bitset 优化即可做到 $O(\dfrac{n^2k}{w})$。 其他想说的话： - 这题确实是一道锻炼思维的题，据我个人观察，考场上坐我旁边的选手们人均思考了一小时以上。 - 我大致想出了正解的思路，但没有想出 bitset 优化，前边 $n\leq 4$ 的特判又挂了（哈哈哈哈哈），感觉 $100->85$ 没什么，$85->70$ 确实是自己的水平问题…… - 希望以后 NOI 能多出今年这样的思维好题吧。