sg函數
hdu 1536 http://acm.hdu.edu.cn/showproblem.php?pid=1536
1.首先,mex的介紹:
mex運算
這是一個集合的運算,表示最小的不屬于這個集合的非負整數。
例如mex{0,1,2,3}=4;
mex{0,1,3,4}=2;
mex{1,2,3,5}=?
2.然后,sg函數的定義和性質:
sg函數
sg函數的定義如下:
g(x)=mex{g(y) | y是x的后繼}
很明顯這是一個遞歸運算。
sg函數的性質了:
如果g(x)=0 那么 x 位置就是必敗點。
如果g(x)>0 那么 x 位置就是必勝點。
View Code
#include "iostream" #include "string" #include "algorithm" using namespace std; int k, a[105], f[10005]; int mex(int x) { int i, t; bool mit[105]={0}; //g(x)=mex{g(y) | y是x的后繼} for(i=0; i<k; i++) //枚舉可取方案 { t = x-a[i];//x-a[i]就是x的后繼 if(t<0) break;//要求非負,所以break if(f[t]==-1)//后繼仍然存在,繼續找 { f[t] = mex(t); } mit[f[t]] = 1;//集合中存在f[t]這個值,標記一下 } for(i=0; ; i++) { if(0==mit[i]) return i; } } int main() { int n, i, m, t, s; while(cin>>k && k) { for(i=0; i<k; i++) cin>>a[i]; sort(a, a+k); memset(f, -1, sizeof(f)); f[0] = 0; cin>>n; while(n--) { cin>>m; s = 0; while(m--) { cin>>t; if(f[t]==-1) f[t] = mex(t);//得出當前的狀態 s = s^f[t];//nim-sum游戲 } if(s==0) cout<<"L"; else cout<<"W"; } cout<<endl; } }
posted on 2012-08-16 15:59 More study needed. 閱讀(371) 評論(0) 收藏 舉報

浙公網安備 33010602011771號