首页 > 代码库 > BZOJ 1874 取石子游戏 (NIM游戏)

BZOJ 1874 取石子游戏 (NIM游戏)

题解:简单的NIM游戏,直接计算SG函数,至于找先手策略则按字典序异或掉,去除石子后再异或判断,若可行则直接输出。

#include  const int N=1005;int SG[N],b[N],hash[N],a[N],sum,tmp,i,j,n,m;  void FSG(int s){      SG[0]=0;      for(int i=1;i<=s;i++){          for(int j=1;b[j]<=i&&j<=m;j++)hash[SG[i-b[j]]]=i;          for(int j=0;j<=s;j++)if(hash[j]!=i){SG[i]=j;break;}      }  }  int main(){      scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&a[i]);      scanf("%d",&m); for(i=1;i<=m;i++)scanf("%d",&b[i]);      FSG(N);      for(i=1;i<=n;i++)sum^=SG[a[i]];      if(!sum){printf("NO");return 0;}      for(i=1;i<=n;i++){          tmp=sum^SG[a[i]];          for(j=1;b[j]<=a[i]&&j<=m;j++)          if(!(tmp^SG[a[i]-b[j]])){              printf("YES\n%d %d",i,b[j]);              return 0;          }      }  }