Codeforce 1425 A. Arena of Greed 解析(思維)

今天我們來看看CF1425A
題目連結

題目
略，請直接看原題。

前言

明明是難度1400的題目，但總感覺不是很好寫阿，而且以下題解我感覺有些地方我也懵懵懂懂的，不是超級確定

想法

首先，這題目有一個除以$2$的動作，因此有可能聯想到$:$我們必須用二進位來看待數字$n$。
有一個不等式非常重要，在這邊重提:$\sum\limits_{n=0}^k2^n<2^{k+1}$，也就是更高位的$bit$一定比低位的所有$bit$總和還要大。
並且我們注意到，如果把一個偶數$-1$，目前最低位的$bit$會被拆成更低位的所有$bit$的總和，也就是例如:$100000_2-1_2=11111_2$，下標$_2$是指二進位。
而我們可以觀察到，如果有個偶數，且偶數的第$0$，第$1$個$bit$都是$0$，也就是例如$1100_2$這個數字。只要我們先減$1$，這樣會變成$1011_2$，因此對手只能拿$1$，使得變成$1010_2$。而$1010_2$並不符合「第$0$，第$1$個$bit$都是$0$」，因此我們直接拿一半…。
只要我們遵循「是偶數且第$0$，第$1$個$bit$都是$0$」時先拿$1$，那麼之後對手都只能拿到$1$而不能拿$\frac{n}{2}$，我們有極大的優勢。

最後如果能再注意到$:$只有當我們至少有一個大於$100_2$的$bit$時，我們才會在「是偶數且第$0$，第$1$個$bit$都是$0$」時先拿$1$，因為在$100_2$時，我們就算先拿一半，只要對手接下來也最多拿到$1$。

程式碼:

ll t,n,nn,ans;  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>t;while(t--){  
    cin>>n;nn=n;ans=0;  
    if(n&1)n--;  
    while(n>0){  
      if(n<8){  
        if(n&1)ans++,n--;  
        else ans+=n/2,n/=2;  
        if(n==0)continue;  
        if(n&1)n--;  
        else n/=2;  
        continue;  
      }  
      assert(n%2==0);  
      if(n%4==0)ans++,n-=2;  
      else ans+=n/2,n/=2,n--;  
    }  
    if(nn&1)cout<<nn-ans<<'\n';  
    else cout<<ans<<'\n';  
  }  
  return 0;  
}  

標頭、模板請點Submission看
Submission