CF323B - Tournament-Graph

题意：构造一个 \(n\) 大小的锦标赛图，即每两点之间恰有一条有向边，满足任意点对 \((u,v)\)，都存在一条从 \(u\) 到 \(v\)，长度不超过 \(2\) 的路径。

方法一

考虑奇数情况，假设我们的点是在环上排列的，那么我们对任意的跨越不超过半个环的边都连上，也就是说，我们把点看成圆上的若干个等分点，每条边就相当于一个弦。弦会分出两个弧，因为没有半圆所以互不相等，我们选择劣弧的顺时针连接。

可以证明这样是可以的。形式化的讲，\(i\) 到模意义下区间 \([i+1,i+\lfloor n/2\rfloor]\) 都是有边的。考虑两点 \((x,y)\)，如果 \(y\) 在区间 \([x+1,x+\lfloor n/2\rfloor]\) 中，显然只需要一步。否则，\(y\) 到 \(x\) 之间距离不会超过 \(n-1\)，那么 \(x\) 先走到 \(x+n/2\)，就一定能一步走到 \(y\)。

然后考虑偶数，我们发现偶数就是奇数加一个点。只要新的点和原来的点构成的任意点对都满足条件即可。

我们可以从新的点到奇数点连边，从偶数点到新的点连边。然后很明显就排除两类点对，只需要检查奇数到新点，新点到偶数的情况。

奇数到新点显然是方便的，因为除了 \(n=4\)，奇数后 \(n/2\) 个点中必有偶数。同样，除了 \(n=4\)，偶数前 \(n/2\) 个点中必有奇数。这就完美了，只有 \(4\) 不能处理，而样例告诉我们 \(4\) 是无解的。

rng_58：https://codeforces.com/contest/323/submission/4766093

方法二

对于每个点对，考虑它们顺时针方向的距离。如果是奇数就顺时针连，否则就逆时针连。

考虑证明正确性。

对于点对 \((x,y)\)，首先 \(y-x\bmod n\) 是偶数。那么，\(x\) 和 \(y\) 之间一定有和 \(x\) 距离是奇数的点，以此为中转就能两步到达 \(y\)。

非常方便，没有任何的分类讨论。

KrK：https://codeforces.com/contest/323/submission/4237631

方法三

考虑如果我们已经有了一个 \(n-2\) 的图，扩张到 \(n\)。新的两个点谁连谁都无所谓，所以就 \(n-1\) 连到 \(n\)。然后考虑它们到原来的点的所有边，我们可以从 \(n\) 到 \(i\) 再从 \(i\) 到 \(n-1\)，这样它们就构成了一个三元环，很明显都是成立的。

但是这样需要基础图。\(n=3\) 是简单的三元环。\(n=4\) 不行，就要从 \(n=6\) 开始，但是发现边数只有 \(15\)，可以直接暴力枚举得到基础图。