网址:https://ac.nowcoder.com/acm/contest/4743/D
题目描述:
小灰灰和小乔在玩取石子游戏,一堆石子有n个石子,小灰灰和小乔轮流操作,小灰灰先手,每次操作的人可以进行以下操作:假设当前石子数量为k,如果k>=2,那么将石子分为f(k)和k−f(k)两堆,然后选择其中任意一堆石子取走。否则当前操作的人输。其中{f(k)=x}f(k)=x,{x}x为满足满足{x*2<=k}x∗2<=k的最大整数。小灰灰和小乔都非常聪明,所以都会采用最优的策略,你知道最后小灰灰和小乔谁能赢得游戏吗?
输入描述:
输入共包含t组数据
第一行一个整数t,表示测试用例的组数
接下来t行每行一个整数n。
输出描述:
对于每组案例,如果小灰灰赢,输出“XiaoHuiHui”,否则输出“XiaoQiao”,不带双引号。
输入
10
1
2
3
4
5
6
7
8
9
10
输出
XiaoQiao
XiaoHuiHui
XiaoHuiHui
XiaoQiao
XiaoQiao
XiaoQiao
XiaoHuiHui
XiaoHuiHui
XiaoHuiHui
XiaoHuiHui
备注:
1<=t<=100000
1<=n<=1e18
题解:
没有意外,在比赛的时候这道题没有做出来,赛后看的题解
当为1的时候,先手必败 [1,1]
可以转换为1的状态:2,3 必胜 [2,3]
当只能转换为上一个必胜区间时必败 [4,6]
可以转换为上一个必败区间时 必胜 [7,12]
需要注意的就是一个时可以转换,一个是只能转换
有时候做这种数学题,可以自己先找几个例子,找规律
这道题就是从下向上进行分析
AC代码
#include<iostream> #include<algorithm> using namespace std; const long long int maxn=1e18; int main(){ //当i(索引下标) 是奇数时,表示必败,是偶数时表示必胜 long long int b[1000];//分别表示每个区间段的开始,闭区间 long long int e[1000];//分别表示每个区间段的末尾 ,闭区间 b[1]=1,e[1]=1; b[2]=2,e[2]=3; int i=3; while(e[i-1]<=maxn){ if(i&1){//i是奇数 b[i]=b[i-1]*2,e[i]=e[i-1]*2; } else{ b[i]=b[i-1]*2-1,e[i]=e[i-1]*2+1; } i++; } //for(int j=1;j<i;j++) cout<<b[j]<<" "<<e[j]<<endl; //cout<<i<<endl; int t; long long int n; cin>>t; while(t--){ cin>>n; for(i=1;;i++){ if(n>=b[i]&&n<=e[i]) break; } if(i&1){ cout<<"XiaoQiao"<<endl; } else{ cout<<"XiaoHuiHui"<<endl; } } return 0; }