小H和小Z正在玩一个取石子游戏。 取石子游戏的规则是这样的,每个人每次可以从一堆石子中取出若干个石子,每次取石子的个数有限制,谁不能取石子时就会输掉游戏。 小H先进行操作,他想问你他是否有必胜策略,如果有,第一步如何取石子。
N≤10 Ai≤1000
裸SG函数啊
然而我连SG函数都不会求了,WA了一会儿之后照别人代码改发现vis公用了...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=,M=;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} int n,a[N],m,b[N];
int sg[M],vis[M];
int dfs(int u){//printf("dfs %d\n",u);
if(sg[u]!=-) return sg[u];//printf("y\n");
bool vis[N];memset(vis,,sizeof(vis));
for(int i=;i<=m && b[i]<=u;i++) vis[dfs(u-b[i])]=;
for(int i=;;i++) if(!vis[i]) {sg[u]=i;break;}
return sg[u];
}
int main(){
//freopen("in","r",stdin);
memset(sg,-,sizeof(sg));sg[]=;
n=read();
for(int i=;i<=n;i++) a[i]=read();
m=read();
for(int i=;i<=m;i++) b[i]=read();
sort(b+,b++m);
int sum=;
for(int i=;i<=n;i++) sum^=dfs(a[i]);
if(sum!=){
puts("YES");
int flag=;
for(int i=;i<=n && !flag;i++)
for(int j=;j<=m && b[j]<=a[i];j++)
if( ( sum^dfs(a[i])^dfs(a[i]-b[j]) )== ) {printf("%d %d\n",i,b[j]);flag=;break;}
}else puts("NO");
}