首页 > 代码库 > 【poj2960】 S-Nim
【poj2960】 S-Nim
http://poj.org/problem?id=2960 (题目链接)
题意:经典Nim游戏,只是给出了一个集合S,每次只能取S[i]个石子。
Solution
g(x)=mex{SG(x-s[1]),SG(x-s[2])……}
数据范围很小,可以暴力求SG,顺便记忆化一下。不知道为什么用map就TLE了。。。只好开数组了。
代码:
// poj2960#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<map>#define inf 2147483640#define LL long long#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);using namespace std;inline LL getint() { LL x=0,f=1;char ch=getchar(); while (ch>‘9‘ || ch<‘0‘) {if (ch==‘-‘) f=-1;ch=getchar();} while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘;ch=getchar();} return x*f;}const int maxn=10010;int k,n,m,sg[maxn],s[maxn];void calsg(int x) { if (sg[x]!=-1) return; //map<int,bool> mark; bool mark[10010]; memset(mark,0,sizeof(mark)); int temp; for (int i=1;i<=k;i++) { temp=x-s[i]; if (temp>=0) { if (sg[temp]==-1) calsg(temp); mark[sg[temp]]=1; } } for (int i=0;;i++) if (!mark[i]) {sg[x]=i;return;}}int main() { while (scanf("%d",&k)!=EOF && k) { for (int i=1;i<=k;i++) scanf("%d",&s[i]); sg[0]=0; for (int i=1;i<=maxn;i++) sg[i]=-1; scanf("%d",&m); while (m--) { scanf("%d",&n); int ans=0; while (n--) { int x;scanf("%d",&x); if (sg[x]==-1) calsg(x); ans^=sg[x]; } if (ans) printf("W"); else printf("L"); } printf("\n"); } return 0;}
【poj2960】 S-Nim
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。