自动搬运

查看原文

来自洛谷，原作者为

	League丶翎 **

搬运于2025-08-24 21:50:17，当前版本为作者最后更新于2019-11-05 21:28:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

[POI2014]SUP-Supercomputer

1 一些思考

之前做这题是因为做了一套 CSP-S 模拟题

然后被这道题坑了（惨兮兮）

出那套题的人估计自己也没有想清楚，所有部分分的解法都是错的（各种知世不对的贪心）...

当然满分做法是正确的

但是在目前看到的各种证明中都是各种错误贪心（狗头保命

对于满分做法的解释也是模糊不清（贪心+显然

所以来证明下最优方案的存在性

可能有锅，轻喷

2 题意

略

3 Solution

3.1 最优方案

假设存在一种策略满足下面条件

1. 能够使得前 $x$ 层用 $x$ 步删完 （一）
2. 后面每次都可以删除 $k$ 个节点 （二）

那么这样的策略必然是最优的

证明很显然，前 $x$ 层不可能用少于 $x$ 步删完，后面的节点每次删除 $k$ 个（最大值）次数肯定是最少的

那么现在的问题是是否存在这样一种策略满足上面的条件

3.2 最优方案存在的证明

假设足够聪明的你当前已经取完了前 $x$ 层，但是用了 $y$ 步 $(x\leq y)$，并且后面节点可以每次删除 $k$ 个来清空，也就是满足 （二）

这样的方案是很好构造的，因为并没有要求前面 $x$ 层 最 优

显然的，上方必然存在另外一个满足已经取完了前 $x'$ 层，使用了 $y'$ 步 $(x'\leq y')$的状态

没错，这里我们不要求后面节点可以每次删除 $k$ 个来清空

我们取最近的一个这样的状态 $x'$ ，对于 $x'$ 层到 $x$ 层进行分析

那么，对于 $(x,y)$ 和 $(x',y')$ 有两种关系：

1. $y-x>y'-x'$
2. $y-x=y'-x'$

3.2.1 第一种情况

对于第一种情况，我们用 $p>x-x'$ 步取完了第 $(x',x]$ 层

对于足够聪明的你，显然会尽量不让这 $x-x'$ 层中的节点 “卡住” 而选择某种方案，那么这 $p$ 步每一步都取到了 $k$ 个节点，那么第 $x'$ 层也满足（二），并且相比第 $x$ 层来说 $y'-x'<y-x$ ，也就是说更接近满足 （一） 了

那么如果当前的状态使得你不得不被 “卡住” ，那么被 “卡住” 时，从 $x'$ 层到被卡住的层的所有点必然已经全部被删除，否则你就可以选择这些点中深度最浅的进行删除。到这里你会发现，这与假设 最近的一个这样的状态 x' 不符，产生矛盾，故不成立

那么在第一种情况中，可以将 $(x,y)$ 替换为 $(x',y')$ ，使得在满足（二）的条件下更接近满足（一）

3.2.2 第二种情况

对于第二种情况，我们利用 $x-x'$ 步取完了第 $(x',x]$ 层

在这里需要分别讨论：

假设 $x-x'>1$，根据上面的证明，$(x+1,x')$ 层的删除必然可以每次删 $k$ 个，并且每层都恰好是 $k$ 个

假设 $x-x'=1$，那么说明第 $x$ 行 $\leq k$

显然每层 $k$ 个的情况可以直接由 $(x,y)$ 转移到 $(x',y')$ 而忽略掉，而 $<k$ 个的情况可以通过从上面 $[1,x']$ 层选择一些叶子节点 “补” 到当前层来使得当前层到 $k$ 个，显然，这样的方法仅仅会使得 $y'$ 减小

那么，通过 “补” 的方式，也使得 $x'$ 层在满足（二）的情况下更接近（一）

3.2.3 总结

所以说，通过转移到最近的 $(x',y')$ ，必然是满足（二），且更加接近满足（一）的

倘若一直没有找到满足（一）的层，而第一层必然是满足（一）的，我们令第一层为 $x'$ 即可，那么第一层也就满足（二）了

故必然存在这样的层 $x$ 同时满足（一）（二），即存在最优方案

4 代码

略