題目:http://acm.hdu.edu.cn/showproblem.php?pid=1848

題意:有3堆石子,石子數量分別為a,b,c,有兩個玩家,每次只能從任意一堆中取f個,這里的f只能為fibnacci數,問是先手勝

還是先手敗.

分析:由于石子的數量都在1000以內,那么我們可以先預處理出1000以內的SG函數值,然后對于3堆石子,我們進行異或,如果為

0說明先手必敗,否則必勝,當然求SG函數的值用深搜就行了.

#include <iostream> #include <string.h> #include <stdio.h>using namespace std; const int N = 1005; const int M = 25;int fib[25]; int SG[N];int mex(int x) {bool vis[M];memset(vis,0,sizeof(vis));for(int i=0;i<M;i++){int t = x - fib[i];if(t < 0) break;if(SG[t] == -1)SG[t] = mex(t);vis[SG[t]] = 1;}for(int i=0;;i++)if(!vis[i]) return i; }void Init() {fib[0] = 1;fib[1] = 2;for(int i=2;i<M;i++)fib[i] = fib[i-1] + fib[i-2];memset(SG,-1,sizeof(SG));for(int i=0;i<N;i++)SG[i] = mex(i); }int main() {Init();int a,b,c;while(~scanf("%d%d%d",&a,&b,&c)){if(a == 0 && b == 0 && c == 0) break;int ans = 0;ans ^= SG[a];ans ^= SG[b];ans ^= SG[c];if(ans) puts("Fibo");else puts("Nacci");}return 0; }

題目:http://acm.hdu.edu.cn/showproblem.php?pid=1536

分析:本題基本上跟上體一樣,只是把3堆改為x堆,把取fibnacci數列顆石子改為取指定輸入的石子個數.那么做法實際上一

樣,我們對輸入的序列進行排序,然后求出它們的SG函數的值,然后直接用即可.

#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h>using namespace std; const int N = 10005; const int M = 105;int a[M]; int SG[N]; int n;int mex(int x) {bool vis[M];memset(vis,0,sizeof(vis));for(int i=0;i<n;i++){int t = x - a[i];if(t < 0) break;if(SG[t] == -1)SG[t] = mex(t);vis[SG[t]] = 1;}for(int i=0;;i++)if(!vis[i]) return i; }int main() {while(~scanf("%d",&n)){if(n == 0) break;for(int i=0;i<n;i++)scanf("%d",&a[i]);sort(a,a+n);memset(SG,-1,sizeof(SG));for(int i=0;i<N;i++)SG[i] = mex(i);int m;scanf("%d",&m);while(m--){int ans = 0;int len,t;scanf("%d",&len);for(int i=0;i<len;i++){scanf("%d",&t);ans ^= SG[t];}if(ans) printf("W");else printf("L");}puts("");}return 0; }

總結

以上是生活随笔為你收集整理的取石子游戏与SG函数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。