取石子游戏 题意: 给你含有k个石子的石子堆。假设当前石子数量为k,如果k>=2,那么将石子分为f(k)和k−f(k)两堆,然后选择其中任意一堆石子取走。否则当前操作的人输。其中f(k)=x,x为满足满足x∗2<=k的最大整数。 小灰灰和小乔都非常聪明,所以都会采用最优的策略,你知道最后小灰灰和小乔谁能赢得游戏吗?
分析: 容易知道如果轮到某方时k=1,那么他输了,现在来分析胜利和失败是如何进行转化的,假设轮到小灰灰时有k个石子,我们令a=k/2,b=k-k/2。
1.a为必胜态,b为必胜态。 如果小灰灰选择a,那么就把b留给了对手(因为b为必胜态,下同),对手胜;如果小灰灰选择b,那么就把a留给了对手,对手胜。则k为必败态。
2.a为必胜态,b为必败态。 小灰灰选择只要选择a,将b留给对手,那么小灰灰就胜利了。(因为对手得到的b为必败态),则k为必胜态。
3.a为必败态,b为必胜态。 小灰灰选择只要选择b,将a留给对手,那么小灰灰就胜利了。(因为对手得到的a为必败态),则k为必胜态。
4.a为必败态,b为必败态。 那么小灰灰不管选择那个,对手都将得到的必败态,则k为必胜态。
分析完后写个程序来找规律。
打表代码:
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2020; bool book[N]; ll a[1010]; int main(){ book[1]=false; //1为必败态 printf("XiaoQiao\n"); for(int i=2;i<=1000;i++){ if(book[i/2]==false&&book[i-i/2]==false) book[i]=true; else if(book[i/2]==true&&book[i-i/2]==true) book[i]=false; else book[i]=true; if(book[i]) printf("XiaoHuiHui\n"); else printf("XiaoQiao\n"); } return 0; }AC代码:
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2020; bool book[N]; ll a[1010]; int main(){ a[1]=1;a[2]=2; for(int i=3;i<=61;i++){ if(i&1) a[i]=2*a[i-1]-1; else a[i]=2*a[i-1]+1; } for(int i=2;i<=61;i++){ a[i]=a[i-1]+a[i]; } int t; scanf("%d",&t); while(t--){ ll n; scanf("%lld",&n); int p=lower_bound(a+1,a+62,n)-a; if(p%2==0) printf("XiaoHuiHui\n"); else printf("XiaoQiao\n"); } return 0; }