CF690A3 Collective Mindsets (hard) 做题记录

一共有 $n$ 个僵尸，每个僵尸头上有一个值域 $[1,n]$ 的数字 $a_i$，每个僵尸只能看到其他 $n - 1$ 个僵尸头顶的数字，当然，他们也知道自己的编号。 要求提供一种策略，使所有僵尸只利用自己知道的信息同时猜自己头顶的数字，保证至少有一个僵尸猜对。

对于每组数据，第一行包含两个正整数 $n$ 和 $r$，表示僵尸总数与当前僵尸的编号，下一行包括 $n−1$ 个正整数，表示当前僵尸看到的所有其他僵尸头顶的编号是多少（按僵尸编号升序排列）。你要输出当前僵尸应该猜测的数字。

时间复杂度要求线性。

神仙题。

首先如果 $x$ 知道每个人头上的数字和对 $n$ 取模的结果 $r$，那么他显然可以求出自己头上的数字。那么考虑让第 $1$ 个人猜 $r=0$，第 $2$ 个人猜 $r=1$，依次类推，第 $i$ 个人猜 $r=i-1$，就可以保证至少有一个人猜对。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

int n,m;

inline void slove()
{
	scanf("%d%d",&n,&m);
	int res=m-1;
	for(int i=1;i<=n-1;i++)
	{
		int x;
		scanf("%d",&x);
		res=(res+x)%n;
	}
	res=n-res;
	printf("%d\n",res);
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T-->0) slove();
	return 0;
}