A. Arena of Greed 解析(思維)

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

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

題目
略，請直接看原題。

前言

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

@copyright petjelinux 版權所有
觀看更多正版原始文章請至petjelinux的blog

想法

首先，這題目有一個除以(2)的動作，因此有可能聯想到(:)我們必須用二進位來看待數字(n)。
有一個不等式非常重要，在這邊重提:(sumlimits_{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<<'
';
    else cout<<ans<<'
';
  }
  return 0;
}

標頭、模板請點Submission看
Submission