A. Arena of Greed（博弈+贪心）2020 ICPC, COMPFEST 12, Indonesia Multi-Provincial Contest

原题链接： https://codeforces.com/problemset/problem/1425/A

测试样例

input
2
5
6
output
2
4

Note

For the first case, the game is as follows:

1. Mr. Chanek takes one coin.
2. The opponent takes two coins.
3. Mr. Chanek takes one coin.
4. The opponent takes one coin.

For the second case, the game is as follows:

1. Mr. Chanek takes three coins.
2. The opponent takes one coin.
3. Mr. Chanek takes one coin.
4. The opponent takes one coin.

题意： 现在$Chanek$和对手玩一个博弈游戏，规则是这样，有一个宝箱中含有$n$个金币，每个人交互进行一回合，$Chanek$先开始。进行操作有两种选择：

• 你可以拿走一个金币
• 如果宝箱中金币数量为偶数，你可以拿走宝箱金币的一半。

当宝箱金币数量为0时，游戏结束。他们都试图得到这最大的金币数量，且他们都玩得最优，问$Chanek$能获得的最大金币数。

解题思路： 既然是最优问题，我们就要思考，什么时候最优，如果我可以进行第二步操作，那么我们是不是倾向于进行第二步操作。 因为这样的收益是目前最大的。当然，这只考虑到你自己，你没有考虑到别的因素。如果我们进行完第二步操作后，别人只能进行第一步操作，而你又能进行第二步操作这是不是最优的？当然是，那么这种情况其实就是$4$的倍数的时候，考虑到这个我们则可以进行选择了，在模拟回合的时候我们要变换角色，可以通过01异或来解决该问题，同时我们也只需要统计$Chanek$的硬币数即可。

AC代码

/*
*邮箱：[e-mail]
*blog:https://me.csdn.net/hzf0701
*注：文章若有任何问题请私信我或评论区留言，谢谢支持。
*
*/
#include<bits/stdc++.h>	//POJ不支持

#define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量，a为初始值，n为界限值，递增
#define per(i,a,n) for (int i=a;i>=n;i--)//i为循环变量， a为初始值，n为界限值，递减。
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define fi first
#define se second
#define mp make_pair

using namespace std;

const int inf = 0x3f3f3f3f;//无穷大
const int maxn = 1e5;//最大值。
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll>  pll;
typedef pair<int, int> pii;
//*******************************分割线，以上为自定义代码模板***************************************//

ll t,n;
int main(){
	//freopen("in.txt", "r", stdin);//提交的时候要注释掉
	IOS;
	while(cin>>t){
		while(t--){
			cin>>n;
			ll ans=0;
			ll player=0;//0代表Chanek，1代表Arena。
			//开始游戏，利益最大化。
			while(n){
				if(n%2){
					if(player==0){
						ans++;
					}
					n--;
				}
				else{
					if(n==4||(n>4&&n%4!=0)){
						if(player==0){
							ans+=n/2;
						}
						n/=2;
					}
					else{
						if(player==0){
							ans++;
						}
						n--;
					}
				}
				player^=1;
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}

本文地址：https://blog.csdn.net/hzf0701/article/details/109260349