题解 P7339 【『MdOI R4』Kotori】

## C 题的贪心和 Hack 方法 这题是 BF 姐姐出的，但是样例是我提供的。另外，$20050909$ 不是我的生日 qwq。 BF 姐姐讲了正解，那么我就作为验题人 & 数据制造者讲讲这题的几种贪心和对应的 Hack 方法。 **本文不讲正解，如果想看正解请移步其他题解（如[BF的官方题解](https://www.luogu.com.cn/blog/bfqaq/solution-p7339)）。** **如果你想看题解区分治做法的时间复杂度说明，请跳转到“对于一个区间求不小于指定数的最大值”。** 如果还有错误的代码没有 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$ 很小的数据点。 ## 对于一个区间求不小于指定数的最大值 做法参考 [题解区某题解](https://ctcode.blog.luogu.org/Yukino)。这种方法被我注意到一开始是因为讨论区有人说自己样例没过却 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)$。 - 类似地，a 情形中 $T_2(k-1,x)=T_3(k-2,x)+T_4(k-2,x)\le 2T_2(k-2,x)$。 - 否则令 $T_3$ 为找到 $\le x$ 的半边，则 $T_2(k-1,x)=T_3(k-2,x)+T_4(k-2,x)+T_4(k-2,r_3+m)$。 - 若 $r_3<r_1$，那么第二次调用 $T_2$（记为 $T'_2)$ 时的 $T_3$（记为 $T'_3$）就因所有数都比 $r_1$ 小而 $=2^{k-2}$。 - 因此 $r'_3\ge r_1$。另一方面 $r'_4>r'_3+m$，故 $r'_2\ge r'_4>r_1+m$，和 $r'_2\le r_1+m$ 矛盾。 因此，对于情形 b，至少一个的结果为 $2^{k-1}$，从而总时间复杂度 $\le k\cdot 2^k$。