(一)巴什博奕(Bash Game):只有一堆n个物品,两个人轮流从这堆物品中取物,规
定每次至少取一个,最多取m个。最后取光者得胜。
显然,如果n=m+1,那么由于一次最多只能取m个,所以,无论先取者拿走多少个,
后取者都能够一次拿走剩余的物品,后者取胜。因此我们发现了如何取胜的法则:如果
n=(m+1)r+s,(r为任意自然数,s≤m),那么先取者要拿走s个物品,如果后取者拿走
k(≤m)个,那么先取者再拿走m+1-k个,结果剩下(m+1)(r-1)个,以后保持这样的
取法,那么先取者肯定获胜。总之,要保持给对手留下(m+1)的倍数,就能最后获胜。
这个游戏还可以有一种变相的玩法:两个人轮流报数,每次至少报一个,最多报十
个,谁能报到100者胜。
(二)威佐夫博奕(Wythoff Game):有两堆各若干个物品,两个人轮流从某一堆或同
时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。
这种情况下是颇为复杂的。我们用(ak,bk)(ak ≤ bk ,k=0,1,2,…,n)表示
两堆物品的数量并称其为局势,如果甲面对(0,0),那么甲已经输了,这种局势我们
称为奇异局势。前几个奇异局势是:(0,0)、(1,2)、(3,5)、(4,7)、(6,
10)、(8,13)、(9,15)、(11,18)、(12,20)。
可以看出,a0=b0=0,ak是未在前面出现过的最小自然数,而 bk= ak + k,奇异局势有
如下三条性质:
1。任何自然数都包含在一个且仅有一个奇异局势中。
由于ak是未在前面出现过的最小自然数,所以有ak > ak-1 ,而 bk= ak + k > ak
-1 + k-1 = bk-1 > ak-1 。所以性质1。成立。
2。任意操作都可将奇异局势变为非奇异局势。
事实上,若只改变奇异局势(ak,bk)的某一个分量,那么另一个分量不可能在其
他奇异局势中,所以必然是非奇异局势。如果使(ak,bk)的两个分量同时减少,则由
于其差不变,且不可能是其他奇异局势的差,因此也是非奇异局势。
3。采用适当的方法,可以将非奇异局势变为奇异局势。
假设面对的局势是(a,b),若 b = a,则同时从两堆中取走 a 个物体,就变为了
奇异局势(0,0);如果a = ak ,b > bk,那么,取走b – bk个物体,即变为奇异局
势;如果 a = ak , b < bk ,则同时从两堆中拿走 ak – ab + ak个物体,变为奇异局
势( ab – ak , ab – ak+ b – ak);如果a > ak ,b= ak + k,则从第一堆中拿走多余
的数量a – ak 即可;如果a < ak ,b= ak + k,分两种情况,第一种,a=aj (j < k)
,从第二堆里面拿走 b – bj 即可;第二种,a=bj (j < k),从第二堆里面拿走 b – a
j 即可。
从如上性质可知,两个人如果都采用正确操作,那么面对非奇异局势,先拿者必胜
;反之,则后拿者取胜。
那么任给一个局势(a,b),怎样判断它是不是奇异局势呢?我们有如下公式:
ak =[k(1+√5)/2],bk= ak + k (k=0,1,2,…,n 方括号表示取整函数)
奇妙的是其中出现了黄金分割数(1+√5)/2 = 1。618…,因此,由ak,bk组成的矩形近
似为黄金矩形,由于2/(1+√5)=(√5-1)/2,可以先求出j=[a(√5-1)/2],若a=[
j(1+√5)/2],那么a = aj,bj = aj + j,若不等于,那么a = aj+1,bj+1 = aj+1
+ j + 1,若都不是,那么就不是奇异局势。然后再按照上述法则进行,一定会遇到奇异
局势。
(三)尼姆博奕(Nimm Game):有三堆各若干个物品,两个人轮流从某一堆取任意多的
物品,规定每次至少取一个,多者不限,最后取光者得胜。
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> using namespace std; typedef long long ll; int main() { int T; cin>>T; int n,m; while(T--) { scanf("%d%d",&n,&m); if(n%(m+1)==0) printf("second "); else printf("first "); } }
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> using namespace std; typedef long long ll; int main() { int n; while(~scanf("%d",&n)) { if(n%3==0) printf("Cici "); else printf("Kiki "); } }
/*hdu1527 简单威佐夫博弈 只需要判断是否满足奇异局势条件即可 */ #include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <cmath> using namespace std; typedef long long ll; int main() { int a,b; while(~scanf("%d%d",&a,&b)) { if(a>b) swap(a,b); int k=b-a;//第k+1个奇异局势 //cout<<k<<endl; int p=(int)((k*(1+sqrt(5.0)))/2); //cout<<p<<endl; printf("%d ",(a==p)?0:1); } }
/*hdu15 简单威佐夫博弈 只需要判断是否满足奇异局势条件即可 */ #include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <cmath> using namespace std; typedef long long ll; int main() { int a,b; double g=(1+sqrt(5.0))/2; while(~scanf("%d%d",&a,&b)&&(a||b)) { int k=b-a;//第k+1个奇异局势 int p=(int)(k*g); if(a==p) {printf("0 ");continue;} printf("1 "); if(a>p) { printf("%d %d ",p,p+k); } for(int i=a-1;i>=0;i--) { int x=i,y=b; int l=b-i; if((int)(g*l)==x) { printf("%d %d ",x,y); } } for(int i=b-1;i>=0;i--) { if(a==b) break; int x=a,y=i; if(x>y) swap(x,y); int l=y-x; if((int)(g*l)==x) { printf("%d %d ",x,y); } } } }
#include <iostream> #include <cstdio> using namespace std; int main() { int n; while(scanf("%d",&n),n) { int a; int ans=0; while(n--) { scanf("%d",&a); ans^=a; } if(ans) cout<<"Rabbit Win!"<<endl;//非奇异局势 else cout<<"Grass Win!"<<endl; } return 0; }
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn=200000+100; int pile[maxn]; int main() { int m; while(scanf("%d",&m)&&m) { int ans=0; for(int i=1;i<=m;i++) { scanf("%d",&pile[i]); ans^=pile[i]; } if(ans==0) { printf("No "); continue; } printf("Yes "); for(int i=1;i<=m;i++) { if(pile[i]>(ans^pile[i])) { printf("%d %d ",pile[i],pile[i]^ans); } } } }
S表示起点。如果n为偶数,那么所有格子可以被2*1的砖块覆盖掉。这样先手每次都移动到当前1*2的另外一块。、
先手必赢。 如果n为奇数。出了起始那个店,其余点都可以被覆盖。所有后手赢
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int main() { int n; while(~scanf("%d",&n)&&n) { if(n&1)printf("ailyanlu "); else printf("8600 "); } }
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int main() { int n; while(~scanf("%d",&n)&&n) { if(n>=3) cout<<"Bob"<<endl; else cout<<"Alice"<<endl; } }
*题目大意:
* 对于n堆石子,每堆若干个,两人轮流操作,每次操作分两步,
* 第一步从某堆中去掉至少一个,第二步(可省略)把该堆剩余
* 石子的一部分分给其它的某些堆。最后谁无子可取即输。
*解题思路:
* 1、先考虑1堆的时候,1堆当然是N点(必胜点),
* 2、然后考虑2堆,细想一下可以发现,当2堆一样时,这个时候
* 的目的就是要把对方给逼到只有2堆都是1的时候,就能必胜了。
* 但是想一下,后手只要模范先手所做的动作,那么最后就会形成
* 两堆都是1的局势,所以当2堆相同时,是一个P点(必败点)。
* 注意当2堆不一样的时候,先手可以把它变成一样,此时变为N点。
* 3、考虑3堆,这个时候,先手必定是可以把局势变成2堆相同的堆的,
* 那么先手肯定胜利,为N点。** (发现,当堆为偶数堆两两同高的时候,此时是P点)
** 偶数:
* 4、当n >= 4堆的时候可以发现,可以把堆的高度按从小到大排列。
* 当n为偶数的时候,可以把最高的那一堆跟最小的那一堆变成一样,
* 然后把高度差用来平衡剩余的那些堆,注意一定是可以平衡的,
* 因为把剩余的堆相邻两两的差值投射到y轴上发现这些离散的线段和
* 小于最高堆于最小堆的差值。* 奇数:
* 5、当n >= 4堆的时候可以发现,可以把堆的高度按从小到大排列。
* 当n为奇数的时候,可以把最高堆给去掉,然后分配给其它堆,
* 注意前面的相邻堆两两的差值投射到y轴,最后的总和还是小于* 最高堆的。
总之,奇数堆是必胜点,偶数堆要判断是否两堆两两相等(必败态),否则必胜态。#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn=100; int a[maxn]; int main() { int n; while(~scanf("%d",&n)&&n) { for(int i=1;i<=n;i++) scanf("%d",&a[i]); int ans=0; int flag=1; if(n%2==1) { cout<<1<<endl; flag=0; } else { sort(a+1,a+n+1); for(int i=1;i<=n;i+=2) { if(a[i]!=a[i+1]) { cout<<1<<endl; flag=0; break; } } } if(flag) cout<<0<<endl; } }
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn=100; int a[maxn]; int fac[15]={2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768}; void solve(int n,int m,int p) { if(n<=2*m)//金币数足够贿赂 { if(n==p) { printf("%d ",m-(n-1)/2); return; } else if((p&1)==(n&1)) { printf("1 "); return; } else { printf("0 "); return; } } if(n==2*m+1) { if(p==n) { printf("0 "); return; } else if(p&1)//保命优先 { printf("1 "); return; } else { printf("0 "); return; } } int t=n-2*m;//不够贿赂 for(int i=0;i<15;i++) { if(t==fac[i]) { printf("0 "); return; } } for(int i=1;i<=14;i++) { if(t<fac[i]) { if(p>2*m+fac[i-1]&&p<2*m+fac[i]) printf("Thrown "); else printf("0 "); return ; } } } int main() { int n,m,p; int T; scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&m,&p); solve(n,m,p); } }