感觉思路和洛谷现有题解不太一样,来发一篇题解。
你将举行一场 \(\texttt{1 V 1}\) 竞技比赛 \(\texttt{Atcoder Janken}\)。 \(N\) 个初始编号为 \(1\sim N\) 选手将会参加比赛。你只有 \(M\) 个比赛场,所以你需要分派给每一个场地两个选手编号。当然,你不能分派一个选手编号给多个比赛场地。比赛共有 \(N\) 轮,每一轮流程如下:
你希望在 \(N\) 轮中没有选手与同一名选手对决多次。将编号分配方案输出。数据保证有解。
我们反过来看,什么时候两个人会再次遇到。由于 \(2m+1=n\) 的情况最难,只考虑这种情况。
假设两个人初始编号为 \(x,y\),先不考虑取模等,第一次相遇时编号为 \(x+a,y+a\),第二次相遇时编号为 \(x+b,y+b\)。容易发现,两场比赛编号的差相等。
现在考虑取模,则差 \(d\) 与差 \(n-d\) 等价。例如 \(n=7\) 时,相差为 \(2\) 的场地编号组合有 \((1,3),\ (2,4),\ (3,5),\ (4,6),\ (5,7),\ (6,1),\ (7,2)\),因此场地编号中这些一共只能出现一次。
将其推广,场地编号中每种差只能出现一次。假设出现的所有差为 \(d_1\sim d_m,\ d_i<d_{i+1}\)。一个显然的思路是让小的编号搭配大的差,避免编号重复。
同时,一个编号只能出现一次。因此,不妨设 \(d_1=1\),那么下一项只能为 \(3\) 而不能为 \(2\)。举例来说,如果 \(d=1\) 的编号组合是 \((3,4)\),则 \(d=2\) 的组合只能是 \((3,5),(2,4)\),但这样都有重复编号出现,舍。
总之,所有编号需要满足任意 \(d_i+d_j\neq n\) 且相邻两项之差至少为 \(2\)。
然后我们来构造编号。
如果 \(n\) 为奇数,差为 \(1,3,5\cdots\),这样任意两项之差必然为偶数,不等于 \(n\),直接 \(\texttt{pass}\)。
如果 \(n\) 为偶数,一个尽可能多地构造出 \(d\) 的方法是使得第 \(t\) 大的和第 \(t\) 小的 \(d\) 的和为 \(n-1\)。例如 \(n=10\) 时构造出的 \(d\) 为 \(1,3,6,8\)。
但是我们发现当 \(n\) 为四的倍数,这样构造的 \(d\) 少了一项。例如 \(n=12\) 时,构造出的 \(d=1,3,8,10\)。我们可以添加的有 \(5\) 或 \(6\)。但是如果我们添加差为 \(6\),会发现在 \(6\) 轮过后,原来的对手互换位置出现。所以我们只能添加 \(5\)。
推而广之,如果 \(n\) 为偶数,构造 \(d=1,3\cdots,(n-1)-3,(n-1)-1\),并根据 \(n\) 是否为 \(4\) 的倍数决定是否添加 \(d=\dfrac n 2-1\)。
具体实现时,可以规律地处理出 \(d\) 数组,并且从大到小排序(代码实现时与上文分析时采用的排序方式不同)。然后对于所有场地,其中一个选手为 \(1\sim m\),另一个选手编号为 \(i+d_i\)。时间复杂度 \(O(n\log n)\),如果稍微动动脑筋按照顺序处理 \(d\) 数组,时间复杂度 \(O(n)\)。
int n, m, d[maxn]; int main () { read(n); read(m); if(n & 1) { rep(i, 1, n / 2) d[i] = 2 * i - 1; reverse(d + 1, d + (n / 2) + 1); rep(i, 1, m) write(i), putchar(' '), writeln(i + d[i]); } else { int nD = 0; int mid = (n / 2 - 1) / 2; rep(i, 1, mid) d[++nD] = i * 2 - 1, d[++nD] = n - i * 2; if(mid * 2 < (n / 2 - 1)) d[++nD] = n / 2 - 1; sort(d + 1, d + nD + 1, greater<int>()); rep(i, 1, m) write(i), putchar(' '), writeln(i + d[i]); } return 0; }