題目鏈接：點擊查看

題目大意：給出n堆石子，兩人輪流按照規則操作，不能操作的一方即為輸

規則：每次將第i堆減少一個石子，將第j堆和第k堆增加一個石子，i,j,k滿足(i<j<=k)

若先手能必勝，輸出先手所選擇的i,j和k，若先手必敗，輸出-1,-1,-1

題目分析：這個題目從網上看到好像是一個叫take&break的模型：

給定 n 堆石子, 每次要求取出不為零的一堆, 再放入兩堆數目比取出的一堆嚴格小的石子(可以為 0 )

而對于這個題目，我們完全可以將每一堆轉換為非0即1的狀態，因為假如任意一堆的石子個數大于等于2，先手無論怎么操作后，后手只需要模仿先手的操作即可，所以起到貢獻作用的只有奇數堆，而偶數堆對游戲的貢獻為0。

因為這個模型的要求是在取出任意一堆后放入比目前的一堆嚴格小的石子中，所以我們可以給題目中的石子重新編號：

n-1,n-2......1,0，也就是說將每一堆石子的編號改為n-i對待

然后將每一堆石子單獨視為一個子游戲，暴力sg打個表（不知道是不是模板，先存下來漲一下姿勢），最后求一下異或即可，若異或完為0，說明必敗，否則按照升序枚舉一下第一個能讓前面的異或能為0的狀態，就是必敗態了

懵懵懂懂的，寫完這個博客我還是不太懂這到底是不是個模型。。先當結論記下吧（我太菜了orz）

有個小細節注意一下，異或屬于位運算，優先級低于==，所以在if語句里記得加個括號

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=25;int sg[N];int a[N];int mex[10000];void get_sg() {sg[0]=0;for(int i=1;i<N;i++){memset(mex,false,sizeof(mex));for(int j=0;j<i;j++){for(int k=j;k<i;k++)mex[sg[j]^sg[k]]=true;}for(int j=0;;j++){if(!mex[j]){sg[i]=j;break;}}} }int main() { // freopen("input.txt","r",stdin);get_sg();int n;int kase=0;while(scanf("%d",&n)!=EOF&&n){int ans=0;for(int i=1;i<=n;i++){scanf("%d",a+i);if(a[i]&1)ans^=sg[n-i];}if(!ans){printf("Game %d: -1 -1 -1\n",++kase);continue;}for(int i=1;i<=n;i++)if(a[i])for(int j=i+1;j<=n;j++)for(int k=j;k<=n;k++)if((ans^sg[n-i]^sg[n-j]^sg[n-k])==0)//記得加括號{printf("Game %d: %d %d %d\n",++kase,i-1,j-1,k-1);goto end;}end:; }return 0; }

?

總結

以上是生活随笔為你收集整理的UVA - 1378 A Funny Stone Game(博弈+sg函数)的全部內容，希望文章能夠幫你解決所遇到的問題。

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