題目連結

1425A

題解

題意

一堆石子，數量為奇數時可以取1一個，數量為偶數時可以取一半。
玩家先手，求最多可以獲取的石子數量。

思路

為了獲取最多的石子數量：

1. 數量為奇數時：只能取1個，然後對手進入情況2，我們只能取剩下的；
2. 數量為偶數時：為了儘可能最大化所能取的石子數量，我們儘可能使得對手只能取1個，即使得對手取時數量為奇數；同時使得我們取石子時數量為偶數。
   為了實現這個情況，我們判斷一下當前石子數量的一半是否為奇數，如果是，我們就取一半；如果不是，我們就取一個，對應的，對手也只能取一個，之後所得到的偶數的一般必然是個奇數。證明略。
3. 此外我們發現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; // SpecialJudge
        else if ((n / 2) % 2) { // TheFirstSituation
            f += n / 2;
            s += 1;
            n = (n / 2) - 1;
        } else { // TheSecondSituation
            f += 1, s += 1;
            n -= 2;
        }
    }
    printf("%lld\n", fs ? f : (s + 1));
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    cin >> T;
    while (T--) {
        cin >> n;
        if (n == 1) cout << 1 << endl;
        else solve(n);
    }
    return 0;
}