ABC165E

本文主要是介绍ABC165E，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

感觉思路和洛谷现有题解不太一样，来发一篇题解。

题目描述

你将举行一场 \(\texttt{1 V 1}\) 竞技比赛 \(\texttt{Atcoder Janken}\)。 \(N\) 个初始编号为 \(1\sim N\) 选手将会参加比赛。你只有 \(M\) 个比赛场，所以你需要分派给每一个场地两个选手编号。当然，你不能分派一个选手编号给多个比赛场地。比赛共有 \(N\) 轮，每一轮流程如下：

• 对于每一名选手，如果他的编号已经被分配了比赛场地，他将会去与对手对决。
• 然后每一名选手的编号 \(+1\)，如果编号变成了 \(N+1\) ，那么将它变为 \(1\) 。 （即选手的编号会变化，而比赛场对决的选手的编号，每一轮都一样。）

你希望在 \(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;
}

这篇关于ABC165E的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！