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

今天我們來看看CF1425A

題目連結

題目

略，請直接看原題。

前言

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

@copyright petjelinux 版權所有

觀看更多正版原始文章請至petjelinux的blog

想法

首先，這題目有一個除以\(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

巴特西

A. Arena of Greed 解析(思維)

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

前言

想法

程式碼:

最新文章

热门文章