BZOJ 1874: [BeiJing2009 WinterCamp]取石子游戏(SG函数)
标签：tput center inline 范围 gpo div rip inpu post
Time Limit: 5 Sec Memory Limit: 162 MB
Submit: 871 Solved: 365
[Submit][Status][Discuss]
Description
小H和小Z正在玩一个取石子游戏。 取石子游戏的规则是这样的，每个人每次可以从一堆石子中取出若干个石子，
每次取石子的个数有限制，谁不能取石子时就会输掉游戏。 小H先进行操作，他想问你他是否有必胜策略，如果有
，第一步如何取石子。
Input
输入文件的第一行为石子的堆数N
接下来N行，每行一个数Ai，表示每堆石子的个数 接下来一行为每次取石子个数的种类数M
接下来M行，每行一个数Bi，表示每次可以取的石子个数，
输入保证这M个数按照递增顺序排列。
N≤10 Ai≤1000
对于全部数据，M≤10，Bi≤10
Output
输出文件第一行为“YES”或者“NO”，表示小H是否有必胜策略。
若结果为“YES”,则第二行包含两个数，第一个数表示从哪堆石子取，第二个数表示取多少个石子，
若有多种答案，取第一个数最小的答案，
若仍有多种答案，取第二个数最小的答案。
Sample Input
4
7
6
9
3
2
1
2
Sample Output
YES
1 1
Hint
样例中共有四堆石子，石子个数分别为7、6、9、3，每人每次可以从任何一堆石子中取出1个或者2个石子，小H有
必胜策略，事实上只要从第一堆石子中取一个石子即可。
HINT
Source
这题不算是很难，数据范围很小，直接暴力求SG函数。
转移题目已经给出了
判断的时候枚举每一堆石子，看看拿走几个仍然满足条件（判断的时候不用暴力枚举，直接用求出来的ans答案,结合异或的性质）
注意一个特别坑的地方！！
^的运算级比==低！！
#include
#include
#include
#include
using namespace std;
const int MAXN=1e6+10,INF=1e9+10;
inline char nc()
{
static char buf[MAXN],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
char c=nc();int x=0,f=1;
while(c‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=nc();}
while(c>=‘0‘&&c‘9‘){x=x*10+c-‘0‘;c=nc();}
return x*f;
}
int S[1005],SG[1005],N,M;
int a[MAXN],b[101];
main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
freopen("b.out","w",stdout);
#else
#endif
N=read();
for(int i=1;iread();
M=read();
for(int j=1;jread();
sort(b+1,b+M+1);
int limit=1001;
for(int i=1;i)
{
memset(S,0,sizeof(S));
for(int j=1;j)
S[ SG[i-b[j]] ] = 1;
for(int j=0;;j++)
if(S[j]==0)
{SG[i]=j;break;}
}
int ans=0;
for(int i=1;i)
ans=ans^(SG[a[i]]);
if(ans==0) {printf("NO\n");return 0;}
for(int i=1;i)
{
for(int j=1;j)
{
if( (ans ^ SG[a[i]-b[j]] ^ SG[a[i]]) == 0) //好坑啊。。
{
printf("YES\n%d",i);
printf(" %d",b[j]);
return 0;
}
}
}
return 0;
}
BZOJ 1874: [BeiJing2009 WinterCamp]取石子游戏(SG函数)
标签：tput center inline 范围 gpo div rip inpu post
原文地址：https://www.cnblogs.com/zwfymqz/p/8463268.html
评论