原題鏈接
簡要翻譯:
Mr.Chanek與另一個人玩一個取硬幣游戲,他先手，玩家在自己的回合內可以取走硬幣堆中的一個，如果硬幣堆里有偶數個硬幣，玩家也可以選擇取走硬幣總數的一半，兩名玩家都是絕對聰明的，他們都希望拿到手中的硬幣盡可能多，
這道題的坑點在于游戲人的目的是最大化手上的硬幣數量，而不是比對手多來贏得比賽，
在可以取 \(n/2\) 時馬上取確實能保證比對手多，但是這不一定能使手上的硬幣最大化，
也就是說，我們希望取走 \(n/2\) ，但不一定現在，
我們需要再單獨取走1個逼迫對手取走下一個，使我在取走 \(n/2\) 后留下的還是一個奇數，
這里需要注意的是 \(n=4\) 時，直接取走2要更優，
目測每次n為偶數就直接取 \(n/2\) 的不是TLE就是WA，至于為什么會T，我也很好奇
#include <cstdio>
typedef long long ll;
#define REG register
inline char getc(){
static char buf[1<<14],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++;
}
inline ll scan(){
REG ll a=0; REG char ch=0;
while(ch<48) ch=getc();
while(ch>=48) a=a*10+ch-48,ch=getc();
return a;
}
inline void print(ll x){
if(x>9){
print(x/10); putchar(x%10+48);
}else{
putchar(x+48);
}
}
ll t,x;
int main(){
t=scan();
while(t--){
x=scan();
REG ll c=1,d,ans=0;
while(x){
if(x&1) d=1;
else{
if((x>>1)&1) d=x>>1;
else{
if(x>4) x-=2,ans++;
d=x>>1;
}
}
if((c++)&1) ans+=d;
x-=d;
}
print(ans); putchar('\n');
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/135375.html
標籤：C++
上一篇：寫給計算機專業同學：大學學過C語言，是否須繼續學習C++編程？
下一篇：學習第39天