【UVA1378】A Funny Stone Game (博弈-求SG值-输出方案)
【題目】
| Description The funny stone game is coming. There are n piles of stones, numbered with 0, 1, 2, ..., n ? 1. Two
|
?
【題目翻譯】
David 玩一個石子游戲。游戲中,有n堆石子,被編號為0..n-1。兩名玩家輪流取石子。每一輪游戲,每名玩家選取3堆石子i,j,k(i<j,j<=k,且至少有一枚石子在第i堆石子中),從i中取出一枚石子,并向j,k中各放入一枚石子(如果j=k則向k中放入2顆石子)。最先不能取石子的人輸。
???請編程幫助David。
???石子堆的個數不會超過23,每一堆石子不超過1000個。
?
【分析】
首先,假設第i堆有xi個石子,那么可以先把xi%2。
因為在同一堆中的兩顆石子是一模一樣的。對方對這顆石子做什么,你就可以對另外一顆石子做同樣的事,相當于這兩顆一樣的石子不存在。
因為每顆石子可以變成兩顆放到后面去,也就是說它的轉移狀態和它的編號有關。
可以將每一顆石子看作是一堆石子,如果它是第p堆中的石子,把么它所代表的這堆石子的個數為n-1-p。
因為石子堆是互不干擾的,因此這個游戲可以看作由若干個只有一堆石子的游戲組成。(把其單獨考慮開來)
求它能到達的子狀態的尼姆和更新自己的sg值即可。跟掃樓梯一題差不多,即使這堆石子的個數為偶數個,他可能還是有用的,即可以拆分也把狀態改變為平衡狀態的,要把這個也考慮上。(好像說得不是很清楚,具體看代碼吧~~)
?
代碼如下:(看錯數據范圍了,懶得改了,就醬吧~)
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #include<queue> 7 using namespace std; 8 #define Maxn 1010 9 10 int n; 11 int a[2*Maxn],b[2*Maxn],sg[2*Maxn]; 12 bool vis[2*Maxn]; 13 14 void get_sg(int x) 15 { 16 memset(vis,0,sizeof(vis)); 17 for(int i=1;i<x;i++) 18 for(int j=i;j<x;j++) 19 { 20 vis[sg[i]^sg[j]]=1; 21 } 22 for(int i=0;i<=2000;i++) 23 if(vis[i]==0) {sg[x]=i;break;} 24 } 25 26 bool output(int x,int now) 27 { 28 for(int i=x-1;i>=1;i--) 29 for(int j=i;j>=1;j--) 30 if((sg[i]^sg[j])==now) 31 { 32 printf("%d %d %d\n",n-x,n-i,n-j); 33 return 1; 34 } 35 return 0; 36 } 37 38 int main() 39 { 40 int kase=0; 41 for(int i=1;i<=1000;i++) get_sg(i); 42 while(1) 43 { 44 scanf("%d",&n); 45 if(n==0) break; 46 int ans=0; 47 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 48 for(int i=1;i<=n;i++) b[i]=a[n-i+1]; 49 for(int i=1;i<=n;i++) 50 { 51 if(b[i]%2==1) ans^=sg[i]; 52 } 53 printf("Game %d: ",++kase); 54 if(ans==0) {printf("-1 -1 -1\n");continue;} 55 int mx=0; 56 for(int i=0;(1<<i)<=ans;i++) 57 if((1<<i)&ans) mx=(1<<i); 58 for(int i=n;i>=1;i--) 59 if(b[i]!=0) {if(output(i,ans^sg[i])) break;} 60 } 61 return 0; 62 } [UVA1378]?
2016-04-17?17:12:38
轉載于:https://www.cnblogs.com/Konjakmoyu/p/5401461.html
總結
以上是生活随笔為你收集整理的【UVA1378】A Funny Stone Game (博弈-求SG值-输出方案)的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: leetcode 18 -- 4Sum
- 下一篇: ubuntu安装SSH2