题解 P3571 【[POI2014]SUP-Supercomputer】

· · 题解

[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 代码

略