CF-1425A Arena of Greed 题解

题目大意

一个箱子里有n个金币，两个人轮流取金币，每个人可以进行两种操作，第一种是取出一个金币，第二种是取出其中一半。只有当箱子中的金币数量为偶数的时候，才能进行第二种操作。问先手最多取出多少金币，两个人都是最优策略。

解题思路

刚开始有了思路，并且是对的。。

但是样例过不了，卡了好久。

后面看了题解，发现4要特判，我吐了。。

其他的都没问题。

（以后要注意特判啊啊啊

完整代码

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

int main() {
	int t; cin >> t;
	while (t--) {
		ll n; cin >> n;
		ll a = 0, b = 0;
		int flag = 1;
		while (n) {
			if (flag == 1) {
				if (n & 1)	a += 1, n--;
				else {
					if (n == 4)	a += 3, n = 0;
					else {
						if ((n - n / 2) & 1)	a += n / 2, n -= n / 2;
						else a++, n--;
					}
				}
			}
			else {
				if (n & 1)	n--;
				else {
					if (n == 4)	a++, n = 0;
					else {
						if ((n - n / 2) & 1)	n -= n / 2;
						else n--;
					}
				}
			}
			flag *= -1;
		}
		cout << a << endl;
	}
}