题解 P7339 【『MdOI R4』Kotori】

· · 题解

C 题的贪心和 Hack 方法

这题是 BF 姐姐出的，但是样例是我提供的。另外，20050909 不是我的生日 qwq。

BF 姐姐讲了正解，那么我就作为验题人 & 数据制造者讲讲这题的几种贪心和对应的 Hack 方法。

本文不讲正解，如果想看正解请移步其他题解（如BF的官方题解）。

如果你想看题解区分治做法的时间复杂度说明，请跳转到“对于一个区间求不小于指定数的最大值”。

如果还有错误的代码没有 Hack 成功，请大家评论区补充，共同进步。

写这篇博客是为了帮助你更好地出题 or 造数据，而非让你在这题面向数据编程。

只留下最小

代号：greedy。

做法：任意一场比赛中，如果其中一个是 1 号，或者这个人比较菜，那么尽量让 TA 获胜。

实际上，样例第 2 组数据已经把一组 Hack 构造出来了，我们要做的就是批量构造这种数据。

观察这种做法错误的原因是，如果我们某一轮选择了比较菜的选手，那么有可能这个选手下一轮会败给对方，导致接下来比赛中 1 号面对的选手反而更强。

所以我们就有了一个基本模型：a 票的同学和 b 票同学先PK，胜者和 c PK，胜者再和 1 号PK。

其中 a,b 在第一场中都有可能获胜。为了卡掉贪心，a 必然输给 c，b< c\le b+m。

若你在第一场中让 a 获胜，那么最终 1 号的对手就是 c，否则是 b。故 1 的人气要可以打败 b 而无法打败 c。

聪明的谷民们可能会想着 k\le 4 则暴算，否则贪心。所以我们需要包装这个模型，把树做大。

我们可以选择向下延伸或向上延伸。yummy 选择了向下，也就是保证 1 号，a,b,c 对应的子树中，我们安排的几个人必然可以获胜。一种简单粗暴的方法就是让这几棵子树的其他选手都打不过TA。

只留下最小和最大

代号：minmax。

做法：对于任意一棵子树，只留下可能的最菜选手（保护 1 号）和可能的最强选手（震慑对方）。

这种方法确实过了样例，且比 greedy 强，但是对于更大的数据范围，它并不一定是正确的。

我们的正解，等价于（虽然复杂度不同）对于每棵子树，把那些不能打的去掉之后取最小的。如果只保留最小最大，那么能保证不能打的都去掉了，但是不保证最大的一定是能打的里面最小的。

也就是，如果一棵子树里有至少两个能打的，这种方法就会出错。

为了避免随机化，只构造一个关键抉择是不够的，所以要递归自动生成关键抉择。

首先要生成带 a_1 的全局，可以让 a_1 在左 2^{k-1} 人中胜出但是只打得过右 2^{k-1} 人中第二名——也就是生成一个 2^{k-1} 人的全局再生成一个 2^{k-1} 人的右半边。

要生成 2^{k} 人的右半边，可以让左半边留下的最菜选手比右半边最菜选手强 m+1 淘汰右边最菜选手，也就是让基准提高 m+1 后生成左半边，恢复再生成右半边。

注意：在递归出口时，如果这个分叉是专门打别人的，不要再生成一个最小值，因为这个最小值没人可以淘汰。

记录最小值和最大值

代号：minmaxrev。

做法：对于任意一棵子树，只记录最菜的选手和最强的选手，作为该子树的获胜者票数取值范围。

这种方法的问题在于，虽然这棵子树每个获胜者的票数都在取值范围内，但不是取值范围内每个数都可能被取到。

我们先构造一棵树使这棵树的可能获胜选手为 \{a,b_{1,2,\ldots x}\}，其中 a+1< b_{\min} 且 b 序列的极差为 d。

然后让这棵树和 c 进行 PK，使得只有 b 序列的选手和 c 成为可能的获胜者，但是 a+1 打得过 c。

接下来让胜者和 1 号 PK，此时胜者票数最小值为 b_{\min}，但 1 号只打得过 a+1。

右半边的递归方法和上一个 Hack 差不多，注意递归出口处悬空即可。

不大于 a_1+m 求最大，否则求最小

代号：a1m。

这一种骗分很聪明，yummy 一时间都没有好的卡法。通过和 BF 姐姐的讨论，我们终于得到了一种Hack方法。

观察到 minmax 失效了，最关键的原因是关键选择的 a,b\le a_1+m，我们需要让一个选择的 a,b>a_1+m。

另一方面，这个选择必须影响到最终的结果——但是，间接影响也是影响啊。

所以，我们可以设一小常数 p，先和卡贪心类似地，a,b PK后和 c PK，此时 b 获胜。

然后进行 p 次 packup，第 i 次让 b-(i-1)m （也就是上回胜者）和 b-im PK，第 p 次的对手刚好是 a_1。

两边互相打得过就取较小值，否则让一边所有人和TA打

代号：retry。

这个骗分相当聪明，感谢 @银翼的魔术师 提供。个人认为有一定参考价值。

错误性写脸上了——一边所有人中不是每个都不会被淘汰。

因此怎么 Hack 也写脸上了——先构造一个会被淘汰的人，然后通过 packup 让两边实力差 >m 触发枚举。

这样的话这个不合法的数据就会和对面打起来。我们只需要让这个不合法数据影响结论即可。

万能卡法

代号：random。

即使我们出题组想了这么多可能的错解，仍然有可能有漏网之鱼，怎么办呢？

我们可以缩小数据范围，提高数据组数，在组数足够多的情况下，我们可以把一定范围内的所有情况都枚举一遍。

所以，知道为什么我们不给 T 的范围，只给 \sum n 的范围了吗？就是因为可以搞一个 T 很大而 n 很小的数据点。

对于一个区间求不小于指定数的最大值

做法参考 题解区某题解。这种方法被我注意到一开始是因为讨论区有人说自己样例没过却 AC。

讨论区的代码错误之处的 Hack 没有较高价值，但是该思想让 yummy 和 BF 都非常迷惑。

正确性没有问题，但是这个时间复杂度乍一眼看上去很像 O(3^k)。

yummy 一度想把这个代码卡满 3^k，但是多次尝试仍然只能做到 k\cdot 2^k。

通过半天的努力（真的半天哦），在“能卡掉”和“不能卡掉”之间反复横跳几次后，感性理解了复杂度。

下面将不严谨地说明该代码最高复杂度为 O(k\cdot 2^k)，假掉了请评论区指出。

记总用时为 T(k,x)（T(0,x)=1），左右半边中找 \le x 的人用时分别为 T_1(k-1,x),T_2(k-1,x)。

我们有 \max(T_1(k,x),T_2(k,x))\le T(k,x)，因为 T_1,T_2 受到了来自 T 的约束，但祖先约束更弱。

a. 都能或不能找到 \le x 的人，则 T(k,x)=T_1(k-1,x)+T_2(k-1,x)\le 2T(k-1,x)，T(k,x)\le 2^k。
b. 否则不妨让左半边找得到 \le x 的人，那么 T(k,x)=T_1(k-1,x)+T_2(k-1,x)+T_2(k-1,r_1+m)，其中 r_1 为左半边的返回值，不存在时为 \inf。

对于情形 b，等号右边三个函数中，若有一个的结果为 2^{k-1}，则 T(k,x)=2T(k-1,x)+2^{k-1}=O(k\cdot 2^k)。

当 r_1<x-m 时，可以得到左半边没有 >x 的数，故 T_1(k-1,x)=2^{k-1}。

否则令右半边的左右两半中找 \le x 的人的用时分别为 T_3(k-2,x),T_4(k-2,x)。

因此，对于情形 b，至少一个的结果为 2^{k-1}，从而总时间复杂度 \le k\cdot 2^k。