2020年浙江理工大学新生赛 B Cly的博弈

注意：本文的代码可以AC，但解释可能有误，思路仅供参考

Description
Cly很喜欢博弈，这天他和他的分身DD_BOND玩起了一个博弈游戏（本体当然是先手了），游戏规则如下，请你判断谁能赢得游戏。
最初有一个数字n，每次操作可以选择一个数字x满足0<x<n，且n%x==0，接着用n-x替换原本数字，谁不能操作谁就输了。
对于每次询问如果先手能赢，你需要告诉cly第一步能选择的最大x是什么，为了方便起见，你最后只需要告诉他所有询问x的和就行了。

Input
第一行查询数字q (1<=q<=1e5)
接下来q行每行输入一个数字n (1<=n<=1e5)

Output
对于每次查询如果先手胜，输出clynb，否则输出DD_BONDNB
最后输出一个和sum

Sample Input
【样例1输入】

1 1

【样例2输入】

1 2

Sample Output
【样例1输出】

DD_BONDNB 0

【样例2输出】

clynb 1

题目分析：
选择x∈(0,n)，使n%x==0，然后n-=x，找不到这个x（不能操作）为输

假设n=1：
第①步不能操作，先手输

假设n=2：
①只能选择x=1，n=2-1=1（到假设n=1）
②不能操作，先手赢

假设n=3：
①只能选择x=1，n=3-1=2（到假设n=2）
②只能选择x=1，n=2-1=1
③不能操作，先手输

假设n=4：
①如果选择x=1，n=4-1=3（到假设n=3）
②只能选择x=1，n=3-1=2
③只能选择x=1，n=2-1=1
④不能操作，先手赢

①如果选择x=2，n=4-2=2（到假设n=2）
②只能选择x=1，n=2-1=1
③不能操作，先手输

可以再往下分析，得出结论：

如果先手可以使 n=1, 那么先手赢

而

奇数=1*奇数*······*奇数 偶数=1*(2^n)*(奇数 或 1)

又

n=n-x

所以

奇数只能变为偶数 偶数可以选择让它变为奇数

要使n=n-x=1，n原来必然为偶数
所以

先手遇到偶数必赢，否则必输

所以

如果（输入的值为偶数），判负 否则，第一步可选的最大x为n的最大奇因数

代码如下：

#include<iostream> #include<cstdio> using namespace std; int main(){int q,n,sum=0;cin>>q;while(q--){scanf("%d",&n);//使用cin会TLE if(n%2==1) cout<<"DD_BONDNB\n";else{cout<<"clynb\n";while(n%2==0)n/=2;//n除以2，直到n为奇数 sum+=n;}}cout<<sum;return 0; }

总结

以上是生活随笔为你收集整理的2020年浙江理工大学新生赛 B Cly的博弈的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。