首页 > 代码库 > uva 1378 - A Funny Stone Game sg博弈
uva 1378 - A Funny Stone Game sg博弈
题意:David 玩一个石子游戏。
游戏中,有n堆石子,被编号为0..n-1。两名玩家轮流取石子。 每一轮游戏。每名玩家选取3堆石子i,j,k(i<j,j<=k,且至少有一枚石子在第i堆石子中)。 从i中取出一枚石子,并向j。k中各放入一枚石子(假设j=k则向k中放入2颗石子)。
最 先不能取石子的人输。 石子堆的个数不会超过23。每一堆石子不超过1000个。
解法:看上去是将石子都往右移,直到全部都到了n-1堆不能移为止。
首先是考虑每堆石子事实上是独立的一个子游戏,堆与堆之间不相互影响。
然后就是个数是偶数的对不会影响必胜必败态,必败态无法通过移动偶数堆得石子来扭转局面。由于必胜者仅仅需对称操作就可以。所以每堆石子就成了01的状态,sg值仅仅是跟位置有关系了。预处理出每一个位置的sg值就可以。计算第一个可行步骤时候。暴力推断ijk就可以。
代码:
/****************************************************** * @author:xiefubao *******************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <vector> #include <algorithm> #include <cmath> #include <map> #include <set> #include <stack> #include <string.h> //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 #define zero(_) (_<=eps) const double pi=acos(-1.0); typedef long long LL; const int Max=100010; const LL INF=0x3FFFFFFF; int sg[100]; bool rem[100]; int n; void init() { sg[0]=0; for(int i=1; i<=25; i++) { memset(rem,0,sizeof rem); for(int j=i-1; j>=0; j--) for(int k=j; k>=0; k--) { rem[sg[j]^sg[k]]=1; } int t=0; while(rem[t]) t++; sg[i]=t; } } bool help[100]; //0 1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42 int main() { init(); int kk=1; while(cin>>n&&n) { memset(help,0,sizeof help); int ans=0; for(int i=0; i<n; i++) { int a; scanf("%d",&a); if(a)help[i]=1; if(a&1) { ans^=sg[n-1-i]; } } printf("Game %d: ",kk++); if(ans) { for(int i=0; i<n-1; i++) { if(help[i]) { for(int j=i+1; j<n; j++) for(int k=j; k<n; k++) { if((ans^sg[n-1-i]^sg[n-1-j]^sg[n-1-k])==0) { printf("%d %d %d\n",i,j,k); goto end; } } } } end: ; } else puts("-1 -1 -1"); } return 0; }
uva 1378 - A Funny Stone Game sg博弈
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。