题意:
n堆石子,两人轮流取石子,每次取的个数的范围是 【a,b】,取完一堆就获胜,最后不能操作的输。
题解:
暴力SG+找规律
首先,如果有一堆的个数在【a,b】之间,一定是先手必胜。
否则的话,将区间【a,b】作为不可到达状态,为什么?因为 取完一堆游戏就结束了,所以谁都不会将当前状态变到区间【a,b】中去。然后暴力出sg值就可以找到规律了。
代码中 函数 print() 为 暴力的程序。
代码:
#include<bits/stdc++.h>
#define N 257
#define INF 0x3f3f3f3f
#define eps 1e-10
#define pi 3.141592653589793
#define mod 998244353
#define LL long long
#define pb push_back
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
int n,a,b,w[N];
int SG(int x)
{
if (a==1) return (x-b-1)%(b+1);
if (x<a) return 0;
x=(x-b)%(a+b);
x/=a;
if (x<2) return 1^x;
return x;
}
void print()
{
int sg[N]={0};
for (int i=b+1;i<100;i++)
{
int k[100]={0};
for (int j=a;j<=b;j++) if (i-j>=0) if (!(i-j>=a && i-j<=b)) k[sg[i-j]]=1;
for (int j=0;;j++) if (!k[j])
{
sg[i]=j;
break;
}
cout<<i<<' '<<sg[i]<<endl;
}
}
int main()
{
// cin>>a>>b;
// print();
int T;
sc(T);
while(T--)
{
int fg=0,ans=0;
sccc(n,a,b);
for (int i=0;i<n;i++)
{
sc(w[i]);
if (w[i]>=a && w[i]<=b) fg=1;
}
for (int i=0;i<n;i++) ans^=SG(w[i]);
if (fg || ans) puts("Yes");else
puts("No");
}
}