Codecherf START51 Div4 Chef & Cook Game

发表于 分类于 阅读次数： Changyan：

Codecherf START51 Div4 Chef & Cook Game

Problem

There is a non-negative integer array AA of length NN. Chef and Cook will play a game on the array with Chef starting first.

In one turn the player will perform the following operation:

  • Choose two indices i,j such that $1 \le i \lt j \le N$ and $A_i \gt 0$.
  • Set $A_i \gets A_i-1$ and $A_j \gets A_j+1$,subtract 1 from $A_i$ and add 1 to $A_j$

The player who is unable to perform the operation loses. If both Chef and Cook play optimally, who will win?

解法：

首先，对于a[i]是偶数的位置，我们很容易想出来对照操作:只要你选了这个位置，我也选，因此对于偶数的位置我们不需要考虑。因此单独考虑a[i]为奇数的位置，我们可以将其转化为Nim游戏，对于i位置，可以移动到大于i的任意位置，因此可以看作可以取1~N-i个石子,所以我们把奇数位置的所有N-i异或起来，如果异或和不为0，则为先手必胜，否则先手必败。

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve(){
	cin>>n;
	rep(i,1,n) cin>>a[i];
	if(n==1){
		cout << "Cook\n";
		return ;
	}
	LL sum=0;
	rep(i,1,n){
		if(a[i]&1) sum^=(n-i);
	}
	cout << (sum?"Chef":"Cook") << "\n";
}