原題鏈接： https://codeforces.com/problemset/problem/1425/A
測驗樣例
input
2
5
6
output
2
4
Note
For the first case, the game is as follows:
- Mr. Chanek takes one coin.
- The opponent takes two coins.
- Mr. Chanek takes one coin.
- The opponent takes one coin.
For the second case, the game is as follows:
- Mr. Chanek takes three coins.
- The opponent takes one coin.
- Mr. Chanek takes one coin.
- The opponent takes one coin.
題意： 現在 C h a n e k Chanek Chanek和對手玩一個博弈游戲，規則是這樣，有一個寶箱中含有 n n n個金幣，每個人互動進行一回合， C h a n e k Chanek Chanek先開始，進行操作有兩種選擇：
- 你可以拿走一個金幣
- 如果寶箱中金幣數量為偶數，你可以拿走寶箱金幣的一半，
當寶箱金幣數量為0時，游戲結束，他們都試圖得到這最大的金幣數量，且他們都玩得最優，問 C h a n e k Chanek Chanek能獲得的最大金幣數，
解題思路： 既然是最優問題，我們就要思考，什么時候最優，如果我可以進行第二步操作，那么我們是不是傾向于進行第二步操作， 因為這樣的收益是目前最大的，當然，這只考慮到你自己，你沒有考慮到別的因素，如果我們進行完第二步操作后，別人只能進行第一步操作，而你又能進行第二步操作這是不是最優的？當然是，那么這種情況其實就是 4 4 4的倍數的時候，考慮到這個我們則可以進行選擇了，在模擬回合的時候我們要變換角色，可以通過01異或來解決該問題，同時我們也只需要統計 C h a n e k Chanek Chanek的硬幣數即可，
AC代碼
/*
*郵箱：unique_powerhouse@qq.com
*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://www.uj5u.com/yidong/190981.html
標籤：其他