本文最后更新于40 天前，其中的信息可能已经过时，如有错误请发送邮件到big_fw@foxmail.com

P2148 [SDOI2009] E&D

题目描述

小 E 与小 W 进行一项名为 E&D 游戏。

游戏的规则如下：桌子上有 2n 堆石子，编号为 $1 \sim 2n$。其中，为了方便起见，我们将第 $2k-1$ 堆与第 $2k$ 堆$（1 \le k \le n）$视为同一组。第 $i$ 堆的石子个数用一个正整数 $S_i$ 表示。

一次分割操作指的是，从桌子上任取一堆石子，将其移走。然后分割它同一组的另一堆石子，从中取出若干个石子放在被移走的位置，组成新的一堆。操作完成后，所有堆的石子数必须保证大于 0。显然，被分割的一堆的石子数至少要为 2。两个人轮流进行分割操作。如果轮到某人进行操作时，所有堆的石子数均为 1，则此时没有石子可以操作，判此人输掉比赛。

小 E 进行第一次分割。他想知道，是否存在某种策略使得他一定能战胜小 W。因此，他求助于小 F，也就是你，请你告诉他是否存在必胜策略。例如，假设初始时桌子上有 4 堆石子，数量分别为 ${1,2,3,1}$。小 E 可以选择移走第 1 堆，然后将第 2 堆分割（只能分出 1 个石子）。接下来，小 W 只能选择移走第 4 堆，然后将第 3 堆分割为 1 和 2。最后轮到小 E，他只能移走后两堆中数量为 1 的一堆，将另一堆分割为 1 和 1。这样，轮到小 W 时，所有堆的数量均为 1，则他输掉了比赛。故小 E 存在必胜策略。

输入格式

本题有多组数据。

第一行一个整数 T，表示数据组数。

对于每组数据：

第一行一个整数 N，表示桌子上共有 N 堆石子，这里的 N 即为题目描述中的 $2n$。

第二行 N 个整数 $S_{1 \dots N}$。

输出格式

对于每组数据，如果小 E 必胜，则一行一个字符串 YES，否则一行一个字符串 NO。

输入输出样例 #1

输入 #1

2
4
1 2 3 1
6
1 1 1 1 1 1

输出 #1

YES
NO

说明/提示

对于 $20\%$ 的数据，$N=2$。

对于另外 $20\%$ 的数据，$N \le 4，S_i \le 50$。

对于 $100\%$ 的数据，$1 \le T \le 20$，$1 \le N \le 2 \times 10^4$ 且 $N$ 为偶数，$1 \le S_i \le 2 \times 10^9$。

思路

sg函数，每个sg表示一种情况，，并由多种博弈，得出最终博弈的结论，能想到用sg函数是因为将第 2k−1 堆与第 2k 堆（1≤k≤n）$视为同一组，丢弃一堆，分开一组堆，多组的情况得出最终结论。
但是我们不知道他有什么规律
所以我们可以通过打表得出结论，我们已知sg(1,1)情况为0，然后每种情况可以转换成之前的情况（如情况2，可以由0，1转换而来）

打表思路

设一组两堆石子的数量为(x,y)。
每次操作只会改变其中一组，不会影响其他组，因此每一组都是一个独立子游戏。根据 SG 定理，最终局面的 SG 值等于所有子游戏 SG 值的异或和。
对于状态 (x,y)(x,y)(x,y)：

移走 y，将 x 分成 k 和 x-k，可以转移到 (k,x−k)；
移走 x，将 y 分成 k 和 y−k，可以转移到 (k,y−k)。

int dp[MAXN][MAXN];
int get_sg(int x,int y){
	if(dp[x][y]!=-1)return dp[x][y];

	set<int> se;
	for(int k=1;k<x;k++) se.insert(get_sg(k,x-k));
	for(int k=1;k<y;k++) se.insert(get_sg(k,y-k));
	
	int res=0;
	while(se.count(res)) res++;
	return dp[x][y]=dp[y][x]=res;
}


	memset(dp, -1, sizeof(dp));
	for(int i=1;i<=16;i++){
		for(int j=1;j<=16;j++){
			cout<<"x:"<<i<<" y:"<<j<<" sg:"<<get_sg(i,j)<<endl;
		}
		cout<<endl;
	}

然后我们可以观察到
$z=(x-1)|(y-1)$
然后统计z的最低位连续1的个数，即为sg

所以我们可以通过一个get_sg快速得到这一组的sg，然后把所有结果异或就行了

代码

//Sunshine sunshine ladybugs awake,
//Clap your hooves and do a little shack.
#include<bits/stdc++.h>
#define int long long
#define endl "\n"

using namespace std;

using PII=pair<int,int> ;
const int MAXN=50;
const int mod=998244353;
const int INF=0x3f3f3f3f3f3f3f3f;

void solve(){
	auto get_sg=[&](int x,int y)->int{
		int z=(x-1)|(y-1);
		int sg=0;
		while(z&1){
			sg++;
			z>>=1;
		}
		return sg;
	};
	
	int n;cin>>n;
	int ans=0;
	vector<int> a(n);
	for(auto &x:a)cin>>x;
	for(int i=0;i<n;i+=2){
		ans^=get_sg(a[i],a[i+1]);
	}
	
	cout<<(ans?"YES":"NO")<<endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;cin>>t;while(t--)
	solve();
	return 0;
}