牛客练习赛59——D取石子游戏

网址：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;
} 

打卡第三天，加油！！！