定每次至少取一个,最多取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者胜。
裸的巴什博奕:
http://acm.hdu.edu.cn/showproblem.php?pid=1846
#include<iostream> #include<cstdio> using namespace std; int main() { int t; cin>>t; while(t--) { int n,m; cin>>n>>m; if(n%(m+1)==0) printf("second "); else printf("first "); } return 0; }
奇偶的博弈问题(简单题)
链接:
http://acm.hdu.edu.cn/showproblem.php?pid=2147
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int main() { int n,m; while(cin>>n>>m) { if(n==0&&m==0) break; else { if(n*m%2==1) cout<<"What a pity!"<<endl; else cout<<"Wonderful!"<<endl; } } //system("pause"); return 0; }
巴什博奕的变形:
链接:
http://acm.hdu.edu.cn/showproblem.php?pid=2149
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int main() { int n,m; while(cin>>m>>n) { if(m%(n+1)==0) cout<<"none"<<endl; else { int k; if(n<m){ for(int i=1;i<=n;i++) { if((m-i)%(n+1)==0) { k=i; cout<<i; break; } } for(int i=k+1;i<=n;i++) { if((m-i)%(n+1)==0) cout<<" "<<i; } } else { for(int i=m;i<=n-1;i++) cout<<i<<" "; cout<<n; } cout<<endl; } } return 0; }
巴什博奕水题
链接:
http://acm.hdu.edu.cn/showproblem.php?pid=2188
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int main() { int t; cin>>t; while(t--) { int n,m; cin>>n>>m; if(n<m||n%(m+1)!=0) cout<<"Grass"<<endl; else cout<<"Rabbit"<<endl; } return 0; }
巴士博弈的变形题(好题)
链接:
http://acm.hdu.edu.cn/showproblem.php?pid=1847
这也是一道巴什博弈:
这题如果你是先手,考虑你的必胜态。注意,因为任何正整数都能写成若干个2的整数次方幂之和。由于规定只能取2的某个整数次方幂,只要你留给对手的牌数为3的倍数时,那么你就必赢,因为留下3的倍数时,对手有两种情况:
1:如果轮到对方抓牌时只剩3张牌,对方要么取1张,要么取2张,剩下的你全取走,win!
2:如果轮到对方抓牌时还剩3*k张牌,对手不管取多少,剩下的牌数是3*x+1或者3*x+2。轮到你时,你又可以构造一个3的倍数。 所以无论哪种情况,当你留给对手为3*k的时候,你是必胜的。
题目说Kiki先抓牌,那么当牌数为3的倍数时,Kiki就输了。否则Kiki就能利用先手优势将留给对方的牌数变成3的倍数,就必胜。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int main() { int n; while(cin>>n) { if(n%3==0) cout<<"Cici"<<endl; else cout<<"Kiki"<<endl; } return 0; }