BZOJ 1874: [BeiJing2009 WinterCamp]取石子游戏

Time Limit: 5 Sec Memory Limit: 162 MB
Submit: 957 Solved: 394
[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有

必胜策略,事实上只要从第一堆石子中取一个石子即可。

解题思路

简单的SG函数。首先暴力求出所有的SG函数值,异或即可。结果本蒟蒻因为最后输出方案时,
位运算没有加括号调了半天。。

代码

#include<bits/stdc++.h>

using namespace std;
const int N = 15;
const int MAXN = 1005; inline int rd(){
int x=0,f=1;char ch=getchar();
while(ch>'9' || ch<'0'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
} int n,m,f[N],a[N],ans;
int sg[MAXN],MAX=-1;
bool vis[MAXN]; inline void get_SG(){
for(register int i=1;i<=MAX;i++){
memset(vis,false,sizeof(vis));
for(register int j=1;f[j]<=i;j++)
vis[sg[i-f[j]]]=1;
for(register int j=0;j<=N;j++)
if(!vis[j]) {
sg[i]=j;
break;
}
}
} int main(){
memset(f,0x3f,sizeof(f));
n=rd();
for(register int i=1;i<=n;i++) a[i]=rd(),MAX=max(a[i],MAX);
m=rd();
for(register int i=1;i<=m;i++) f[i]=rd();
get_SG();
// for(register int i=1;i<=n;i++) cout<<a[i]<<" "<<sg[a[i]]<<endl;
for(register int i=1;i<=n;i++) ans^=sg[a[i]];
if(!ans) puts("NO");
else {
puts("YES");
for(register int i=1;i<=n;i++)
for(register int j=1;j<=m;j++)
if(a[i]>=f[j] && (sg[a[i]-f[j]]^ans^sg[a[i]])==0){
printf("%d %d",i,f[j]);
return 0;
}
}
return 0;
}
上一篇:eclipse中启动服务时提示端口被占的2种解决方案


下一篇:Long类型参数传到前端精度丢失的解决方案