【bzoj1874】取石子游戏

  • 本文为博主原创,未经许可不得转载

题解

首先我们求出所有状态的$SG$函数,很显然这道题中$x$的后继状态为$succ(x)=${$ x-v |v\in B $}

那么所有$SG(A[i])$的抑或和不为$0$是先手必胜的条件

至于输出方案,暴力枚举即可

这道题目告诉我一定要注意位运算的优先级,博主因为这个wa掉多次

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
#define FILE "read"
using namespace std;
const int MAXN=(int)1e3,D=50;
int n,m,ans,a[15],b[15],check[MAXN+D],sg[MAXN+D];
namespace INIT{
char buf[1<<15],*fs,*ft;
inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int read(){
int x=0,f=1; char ch=getc();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getc();}
while(isdigit(ch)) {x=x*10+ch-'0'; ch=getc();}
return x*f;
}
}using namespace INIT;
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
n=read(); for(int i=1;i<=n;++i) a[i]=read();
m=read(); for(int i=1;i<=m;++i) b[i]=read();
for(int i=1;i<=MAXN;++i){
for(int j=1;j<=m;++j) if(i-b[j]>=0) check[sg[i-b[j]]]=i;
for(int j=0;j<=MAXN;++j) if(check[j]!=i) {sg[i]=j; break;}
}
for(int i=1;i<=n;++i) ans^=sg[a[i]];
if(ans){
puts("YES");
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
if((ans^sg[a[i]]^sg[a[i]-b[j]])==0){
printf("%d %d\n",i,b[j]);
exit(0);
}
}
}
else puts("NO");
return 0;
}
文章目录
  1. 1. 题解
  2. 2. 参考代码
,