E&D
时间限制
1.00s
内存限制
125.00MB
题目描述
小 E 与小 W 进行一项名为 E&D 游戏。
游戏的规则如下：桌子上有 \(2n\) 堆石子，编号为 \(1 \sim 2n\) 。其中，为了方便起见，我们将第 \(2k-1\) 堆与第 \(2k\) 堆\(（1 \le k \le n）\)视为同一组。第 \(i\) 堆的石子个数用一个正整数 \(S_i\) 表示。
一次分割操作指的是，从桌子上任取一堆石子，将其移走。然后分割它同一组的另一堆石子，从中取出若干个石子放在被移走的位置，组成新的一堆。操作完成后，所有堆的石子数必须保证大于 \(1\) 。显然，被分割的一堆的石子数至少要为 \(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。
输入输出样例
输入
2
4
1 2 3 1
6
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\) 。
原题链接
P2148 [SDOI2009]E&D
题目大意
给定n对石子堆，每次操作针对一对石子堆：去掉一堆，将另外一堆石子进行分割，保证所有石子堆数量不为0
解题思路
博弈论，sg函数
-
sg定理：
设为ICG的状态，则：
nim游戏，N堆石子，单位是一对堆石子，可以先把所有单位的sg函数求出，然后再根据sg定理进而求出整堆石子的sg函数。
首先，\(sg(1,1)\)为必败点，即\(sg(1,1)=0\),设\(i=j+k\),则\(sg（i,……)=mex(sg(j,k))\)。
算起来比较，我们可以用bitset来简化操作，bitset每一位我们用来表示是否出现在mex集合里，如bitset表示的\(s(i)\),意思是所有\(j+k=i\)的sg函数，位数为\(1\)表示该位出现在mex集合里面。
复杂度过大，不过可以用来打表找规律~
打表代码：
#include<bits/stdc++.h>
using namespace std;
const int N=210;
int sg[N][N];
//设i=j+k,由题意，sg[i,…]=mex(sg[k])，s[i]相当于sg函数的集合，不过每个数都用01表示，存储mex元素
bitset<101>s[N];
inline int mex(bitset<101> b)
{
int i=0;
while(b[i])i++;
return i;
}
int main()
{
for(int i=2;i<=101;i++)
for(int j=1,k=i-1;k;j++,k--)
s[i].set(sg[j][k]=mex(s[j]|s[k]));
for(int i=1;i<=100;i++)
{
for(int j=1;j<=100;j++)
cout<<sg[i][j]<<' ';
puts("");
}
return 0;
}
打表结果：iujie
根据打表结果，
- \(i \in 奇数，j \in 奇数\),有\(sg(i,j)=0\)
- \(sg(i,j)=sg(j,i)\)
- \(n\) 列和 \(2n\) 列有一定联系，对 \(j \in 偶数,\)有 \(sg(i,j)=sg(\frac{i-1}{2}+1,\frac{j}{2})+1\)
可以递归求解
- 算法复杂度：\(o(nlogn)\)
代码
#include<bits/stdc++.h>
using namespace std;
int t,n,x,y;
inline int sg(int n,int m)
{
if((n&1)&&(m&1))return 0;
else if(!(m&1))return sg((n-1>>1)+1,m>>1)+1;
else
return sg(m,n);
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int res=0;
for(int i=0;i<n/2;i++)
{
scanf("%d%d",&x,&y);
res^=sg(x,y);
}
puts(res?"YES":"NO");
}
return 0;
}