自动搬运

查看原文

来自洛谷，原作者为

	VinstaG173 Si Dieu n'existait pas, il faudrait l'inventer.

搬运于2025-08-24 22:34:51，当前版本为作者最后更新于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$，故他不会在任意一场比赛中被淘汰，因此最终能够夺冠。