题目链接
1425A
题解
题意
一堆石子，数量为奇数时可以取1一个，数量为偶数时可以取一半。
玩家先手，求最多可以获取的石子数量。
思路
为了获取最多的石子数量：
- 数量为奇数时：只能取
1个，然后对手进入情况2，我们只能取剩下的； - 数量为偶数时：为了尽可能最大化所能取的石子数量，我们尽可能使得对手只能取
1个，即使得对手取时数量为奇数；同时使得我们取石子时数量为偶数。
为了实现这个情况，我们判断一下当前石子数量的一半是否为奇数，如果是，我们就取一半；如果不是，我们就取一个，对应的，对手也只能取一个，之后所得到的偶数的一般必然是个奇数。证明略。 - 此外我们发现
1和4是个特殊情况，需要特判一下。
AC代码
#include<bits/stdc++.h>using namespace std;using ll = long long;int T;
ll n;void solve(ll n) {
ll f = 0, s = 0; // To distinguish between first and second hands.bool fs = true;if (n & 1) n -= 1, fs = false;while (n) {
if (n == 4) f += 3, s += 1, n = 0; // SpecialJudgeelse if ((n / 2) % 2) {
// TheFirstSituationf += n / 2;s += 1;n = (n / 2) - 1;} else {
// TheSecondSituationf += 1, s += 1;n -= 2;}}printf("%lld\n", fs ? f : (s + 1));
}int main() {
#ifndef ONLINE_JUDGEfreopen("input.txt", "r", stdin);
#endifcin >> T;while (T--) {
cin >> n;if (n == 1) cout << 1 << endl;else solve(n);}return 0;
}