牛客练习赛59d取石子游戏，博弈论
取石子游戏
https://ac.nowcoder.com/acm/contest/4743/D
从样例中可以看出1是必败态，它无法分成两份
2是必胜态
按博弈论讨论必胜态就是自己操作后是对方陷入必败态
从样例上看
可以转移到1的必胜态1*2,1*2+1 {1+（1+1）}即【2,3】必胜态
只能转移到上必胜态的必败态 2*2，2+3，2*3，即【4,6】必败态
可以转移到上必败态的必胜态4*2-1,4*2，。。。，2*6+1，级【7,13】必胜态
由此我们可以看出
如果上个必胜是【wl，wr】，则该必败是【2*wl，2*wr】
如果上个必败是【fl，fr】，则该必胜是【2*fl-1（fl！=1），2*fr+1】
由于左区间必败要特判不方便，所以用右区间判断
我们可以看出右区间是
必胜：必败*2+1
必败：必胜*2
。。
这样更替的
所以我们可以求出恰好包含n的右区间就可以了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n;
bool work(ll x){
ll tmp=1,flag=0;//1（必败）对应0
while(tmp<x){
flag^=1;
tmp=(tmp<<1)+flag;
}
return flag;
}
int main(){
cin>>t;
for(int i=0;i<t;i++){
cin>>n;
if(work(n)){
cout<<"XiaoHuiHui"<<endl;
}else cout<<"XiaoQiao"<<endl;
}
return 0;
} 计算时间复杂度：1e5*log2（1e8）=1e5*20——没问题（创作不易点赞再走
） 
Momenta公司福利 286人发布
投递旷视等公司10个岗位 >