POJ 2960 S-Nim

本文主要是介绍POJ 2960 S-Nim，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://poj.org/problem?id=2960

这个题算是比较简单的博弈了，跟那个只能取fibonacci数博弈一样求没堆石子的sg值，然后看异或之后是否为0，为0是必败态，否则为必胜态

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int maxn=10010;int sg[maxn],s[110],K;
int get_sg(int i)
{if(i==0) return 0;if(sg[i]!=-1) return sg[i];bool vis[maxn]={0};for(int j=0;j<K&&s[j]<=i;j++)vis[get_sg(i-s[j])]=1;for(int j=0;;j++)if(!vis[j]) return j;
}
int main()
{int n,a,b;while(scanf("%d",&K)&&K){for(int i=0;i<K;i++)scanf("%d",&s[i]);sort(s,s+K);memset(sg,-1,sizeof(sg));for(int i=0;i<=10000;i++)sg[i]=get_sg(i);/* for(int i=0;i<=12;i++)cout<<sg[i]<<" ";cout<<endl;*/scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&a);int ans=0;for(int j=0;j<a;j++){scanf("%d",&b);ans^=sg[b];}printf(ans==0?"L":"W");}puts("");}return 0;
}

这篇关于POJ 2960 S-Nim的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---