題目鏈接
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; // 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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/150098.html
標籤：其他