?

傳送門：S-Nim

題意：給n個數的集合s， 再給m 組數據，每組表示 k 堆石子，每次可以取的個數只能是集合s中的數量。問先手勝還是輸？

分析：sg函數的經典運用，先預處理出所有數量為0~10000的石子的sg值，然后判斷k堆石子的sg值異或和是否為0來判斷先手的輸贏。

#include <cstdio> #include <cstring> #include <algorithm> #define N 110 using namespace std; int n,m,k; int sg[N*N],a[N]; int dfs(int x) {if(~sg[x])return sg[x];int vis[N],temp;memset(vis,0,sizeof(vis));for(int i=0;i<n;i++){int temp=x-a[i];if(temp<0)break;temp=dfs(temp);vis[temp]=1;}for(int i=0;;i++){if(vis[i])continue;return sg[x]=i;}} int main() {while(scanf("%d",&n),n){memset(sg,-1,sizeof(sg));for(int i=0;i<n;i++){scanf("%d",&a[i]);}sort(a,a+n);for(int i=0;i<=10000;i++)if(sg[i]==-1)dfs(i);scanf("%d",&m);while(m--){scanf("%d",&k);int x,ans=0;for(int i=0;i<k;i++){scanf("%d",&x);ans^=sg[x];}if(ans)printf("W");else printf("L");if(!m)puts("");}} } View Code

?

轉載于:https://www.cnblogs.com/lienus/p/4326803.html

總結

以上是生活随笔為你收集整理的hdu 1536（博弈）的全部內容，希望文章能夠幫你解決所遇到的問題。

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