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

痛定思痛。 2023-07-15 09:25 9阅读 0赞

## 题目描述： ##

小灰灰和小乔在玩取石子游戏，一堆石子有n个石子，小灰灰和小乔轮流操作，小灰灰先手，每次操作的人可以进行以下操作：  
假设当前石子数量为k，如果k>=2，那么将石子分为f(k)和k−f(k)两堆，然后选择其中任意一堆石子取走。否则当前操作的人输。  
其中f(k)=x，x\{为满足满足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

题意：让你把一个数k分成两个更小的数，k/2、k-k/2  
我们从大到小不是很容易做，因为他可能分成两个偶数、两个奇数、一奇一偶，不容易做。  
所以我们从小往大看会发现他的输赢是一段一段的，如果某个数k是必胜态，那么2 \* k是必败态，反之亦然，那么我们通过前10个数可以算出前20个数，会发现每一段的最后一个数是有规律的  
1、3、6、13、26…  
分别是 \* 2+1 和 \* 2交替操作，tot为偶数次是小灰灰必胜态，奇数次是小灰灰必败态，我们只需要往后找就可以了。

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<map>
    #include<queue>
    #include<vector>
    #include<set>
    #include<sstream>
    using namespace std;
    typedef long long ll;
    const ll maxn=1e6+10;
    const ll inf=0x3f3f3f3f3f3f3f3f;
    int main()
    { 
    	ios::sync_with_stdio(false);
    	cin.tie(0);cout.tie(0);
    	ll t;
    	cin>>t;
    	while(t--)
    	{ 
    		ll n;
    		cin>>n;
    		ll sum=1,tot=1;
    		while(sum<n)
    		{ 
    			if(tot&1)	
    				sum=sum*2+1;
    			else
    				sum=sum*2;
    			tot++;
    		}
    		if(tot&1)
    			cout<<"XiaoQiao"<<endl;
    		else
    			cout<<"XiaoHuiHui"<<endl;
    	}
    	return 0;
    }