听见下雨的声音题解

VinstaG173 · 2021-10-07 09:06:11 · 题解

这一题是我们学校数学竞赛组的同学不知道哪里找来的一个题，同学们一致认为这题中这么多二进制和按位处理有点更适合 OIer 的思维（主要就构造而言~~证明确实很 MO 但是众所周知做 OI 题不需要选手会证明~~。

首先证明 m \le 2^n-n，即至少有 n 个人无法夺冠。

有一个显然的事情是每一项的最后一名无法夺冠，因为比赛到这一项是他必然淘汰。但是有多项最后一名是同一个人的时候为什么还有至少 n 人无法夺冠呢？

事实上，我们按任意顺序排列这 n 个项目（我们假设就是按最简单的方式，即按编号从 1 到 n），然后对每个项目依次进行如下操作找出每个项目的“落败者”和每位“落败者”的“落败项”：

选择该项目除去已成为“落败者”的选手之外的最后一名，成为该项目的“落败者”，并规定该项目为此“落败者”的“落败项”。

我们断言：每位“落败者”在其“落败项”的比赛结束后必然已经淘汰，故他们均无法夺冠。

对比赛项目编号归纳。第 1 项的“落败者”是该项目的最后一名，显然必被淘汰。假设前 m-1 项的“落败者”都会被淘汰，考虑第 m 项的“落败者”。假设存在一种场次安排使得他在项目 m 比赛后不淘汰，设有 x 名实力比他更弱的选手能够参加项目 m 的比赛。由“落败者”的定义，这些人分别是前 m-1 项之一的“落败者”，由归纳假设以及他们能够参加项目 m 的比赛知他们的“落败项”均尚未比赛，故这一场比赛至少是倒数第 x+1 场，淘汰的人数至少为 2^x 人。而 x \ge 0 时 2^x \ge x+1，所以作为当前第 m 项的倒数第 x+1 名他理应被淘汰，矛盾。故我们的断言成立。

下面给出一种各项目实力排名和场次安排的构造方法使得有 2^n-n 名选手能夺冠。鉴于得出此构造的思维过程比较复杂~~其实是比较 MO~~，我将过程放到 std 之后，各位若有兴趣可以去看看。

首先，我们将选手编号改为从 0 到 2^n-1。然后我们规定二进制的第 i 位表示的是从高到低的第 i 位，即 2^{n-i} 对应的二进制位。

我们规定项目 i 的实力排名：第 j 名的编号为 2^n-j \oplus 2^{n-i}，其中 \oplus 表示按位异或运算，也可以理解为将 2^n-j 的第 i 位上数值取反（01 互换）。

现在我们发现选手 2^{n-i} 是第 i 项的最后一名，无法夺冠。对其余选手，我们设其编号二进制第 a_1,a_2,\dots,a_k 位为 1，其余位为 0（显然有 k \ge 2），如下给出一种让他能够夺冠的场次安排：

第 a_j 场比赛项目 a_{j+1}（j=1,2,\dots,k-1），第 a_k 场比赛项目 a_1。对不等于任意 a_j 的 t，第 t 场比赛项目 t。

容易验证这样的构造使得每位选手均能夺冠，各位有兴趣可以自行验证，在此题解的最后我也会证明为什么可以夺冠。

代码很短很好写。时间复杂度 O(2^nn)。数据范围这么小是因为我只会写 O(4^nn) 的 checker（

Code:

#include<cstdio>
#define rg register
int n,m,l,tg[16],c;
int main()
{
    scanf(" %d",&n),l=1<<n,m=l-n,printf("%d\n",m);
    for(rg int v=l>>1;v;v>>=1)for(rg int i=l-1;~i;--i)printf("%d%c",(i^v)+1,i?' ':'\n');
    for(rg int i=0,t=1,b=0;i<l;++i)
    {
        if(i==t){t<<=1,++b;continue;}printf("%d ",i+1),tg[c=0]=-1;
        for(rg int v=1,j=0;v<t;v<<=1,++j)if(i&v)tg[++c]=j;tg[0]=tg[c];
        for(rg int j=n-1;~j;--j)printf("%d%c",n-((j==tg[c])?(tg[--c]):j),j?' ':'\n');
    }
    return 0;
}

以下给出构造方法得出的思路。考虑归纳。n=1 时构造显然。设 n \le k 时已经构造完毕。考虑 n=k+1 时。

首先假设第一项比赛淘汰的 2^k 名选手组成的集合为 B，剩下 2^k 名选手组成的集合为 A，对 A 用归纳假设知其中有 2^k-k 人能夺冠。因此我们在 B 中希望有 2^k-1 人能夺冠，因此我们需要有更强的条件。为了得到这个条件，我们不妨设剩下的项目中均是 B 中选手排名前 2^k。这样我们发现第一场比赛剩下的任一项目都可以使得 A 全员淘汰，对 B 中选手是没有影响的，可以看作一个“废项”。对条件进行加强，往证一个引理：

引理 1. 2^n 名选手，n+1 个项目，可以让其中一项作为“废项”不计分，则有 2^n-1 名选手可能夺冠。

对于此引理的证明，我们仿照以上过程得到集合 A,B，对 A 用归纳假设。此时我们发现我们需要更强的条件使得 B 全员可以夺冠，仿照上面又得到一“废项”，因此往证另一个引理：

引理 2. 2^n 名选手，n+2 个项目，可以让其中 2 项作为“废项”不计分，则全员均可能夺冠。

依照以上过程得到集合 A,B，只要有两项分别以 A,B 为前一半，对 A,B 分别用归纳假设即证。因此引理 1. 得证，因此原题得证。

我们考虑如何得到这样的集合 A,B。容易发现某一项的排名中将最高位取反时，编号最高位为 0,1 的选手恰满足 A,B 的性质。依此类推我们得到了具体的构造方法。

事实上上面的过程并不严谨，因为对条件加强相当于是减弱了命题，因此引理 2 弱于引理 1，引理 1 又弱于原题。但是我们由此过程得出的直接构造的方法是正确的。

现在再来证明构造方法的正确性。

我们先证明一个结论：经过 k 场比赛后，剩下的选手编号前 k 位均相同。

对 k 归纳。k=0 时显然成立。设 k=x 时成立，考虑第 x+1 场比赛的比赛项目。

如果该项目编号不超过 x，由于剩下的选手编号前 x 位相同，因此他们的排名即是按编号从大到小，淘汰的选手即为第 x+1 位为 0 的一半，剩下的第 x+1 位均为 1，故结论仍成立。

如果该项目编号等于 x+1，则剩下的选手中排名前一半的编号第 x+1 位均为 0，结论仍成立。

同理该项目编号大于 x+1 时剩下的选手中前一半的编号第 x+1 位均为 1。故结论对 k=x+1 仍成立。

观察以上结论的证明过程，我们同时知道当且仅当第 j 场比赛安排项目 j 时编号第 j 位为 0 的选手能不被淘汰。显然对于上面的构造，我们在我们希望夺冠的选手编号为 0 的位置 j 处均安排项目 j，编号为 1 的位置 j 处均不安排项目 j，故他不会在任意一场比赛中被淘汰，因此最终能够夺冠。

听见下雨的声音 题解

听见下雨的声音题解