367
技術社區[雲棲]
poj 2960,hdu 1536 S-NIM 博弈
同樣的題目，又不會寫了，還是沒有完全理解博弈的內涵，又看了遍論文。
明天一定要搞懂
目前最新的想法是每個sg函數值代表的是到達必敗態的方法，如果2個必勝方法一樣，那麼為輸，否則為勝。明天再好好看看
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int s[101];
int k;
int sg[10005];
int get_sg(int x)
{
if(~sg[x])return sg[x];
int vis[101],i;
memset(vis,0,sizeof(vis));
for(i=0;i<k;i++)
{
if(s[i]>x)break;
vis[get_sg(x-s[i])]=1;
}
for(i=0;vis[i];i++);
return sg[x]=i;
}
int main()
{
int i;
while(~scanf("%d",&k)&&k)
{
memset(sg,-1,sizeof(sg));
sg[0]=0;
for(i=0;i<k;i++) scanf("%d",&s[i]);
sort(s,s+k);
int n,T,ans;
scanf("%d",&T);
while(T--)
{
ans=0;
scanf("%d",&n);
while(n--)
{
scanf("%d",&i);
ans^=get_sg(i);
}
putchar(ans?'W':'L');
}
puts("");
}
}
最後更新：2017-04-03 16:49:07