UVa 1378 A Funny Stone Game [博弈论 SG函数]

A Funny Stone Game

题意:

$n \le 23$堆石子,每次选择$i < j \le k$,从$i$拿走1颗$j,k$各放入一颗,不能取就失败。求先手是否必胜以及第一次取的策略


一开始一直在想游戏怎么会结束...眼残没发现$i<j.....$

然后,解这类组合游戏问题重要的一步是发现独立的子游戏

本题中每个石子是互不影响的

$sg[i]$为一颗在$i$的石子的状态

$sg[i]=mex\{sg[j] \oplus sg[k]\}$

然后就$\oplus$起来就行了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=;
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,s[N];
int sg[N],use[N*N];
int main(){
freopen("in","r",stdin);
int cas=;
while( (n=read()) ){
printf("Game %d: ",++cas);
for(int i=;i<=n;i++) s[i]=read();
sg[n]=;
for(int i=n-;i>=;i--){
memset(use,,sizeof(use));
for(int j=i+;j<=n;j++)
for(int k=j;k<=n;k++) use[ sg[j]^sg[k] ]=;
for(int j=;;j++) if(!use[j]) {sg[i]=j;break;}
}
int ans=;
for(int i=;i<=n;i++) if(s[i]&) ans^=sg[i];
if(ans!=){
int i,j,k;
for(i=;i<=n;i++) if(s[i]){
int flag=; ans^=sg[i];
for(j=i+;j<=n;j++){
if(ans==) {k=j,flag=;break;}
for(k=j+;k<=n;k++) if( (ans^sg[j]^sg[k])== ) {flag=;break;}
if(flag) break;
}
if(flag) break; ans^=sg[i];
}
printf("%d %d %d\n",i-,j-,k-);
}else puts("-1 -1 -1");
}
}
上一篇:P1055 [NOIP2008 普及组] ISBN 号码


下一篇:狼道