ABC165E

2022/5/26 23:20:56

本文主要是介绍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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程