自动搬运

查看原文

来自洛谷，原作者为

	yummy 这个人是时代的眼泪，什么也没有留下

搬运于2025-08-24 22:28:55，当前版本为作者最后更新于2021-02-12 14:45:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

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)$。

• 类似地，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$。