以尋找「一定會獲得獎品的最大編號的隊伍編號」為例
首先,隊伍編號和最差名次有單調性
因此我們可以二分搜隊伍編號,看看他最差的名次會是多少
至於最差的名次要怎麼求呢?
可以發現,在比了第i場比賽後,基本上就決定了最終名次的第N-i個bit
因此,可以輸的要先輸
問題是,要怎麼儲存目前可能和隊伍u比賽的隊伍集合呢?
首先,我們需要的資訊是:存不存在另一個隊伍v可以讓u再輸一場?
經過觀察,每比完一場比賽,這個集合就變成了原本的二分之一
因此,我們只要儲存比u強的有幾隊(以下稱作l),比u弱的有幾隊(以下稱作r)就好了
最佳策略是:
如果l有東西(?),就跟它比然後輸掉一場,剩下的,因為要在輸掉的隊伍集合中盡量保留比u強的,所以l先盡量自己跟自己比,這樣就能保證留下來輸掉的l最大化
如果沒有的話,就只剩一條路走了(跟r比)
「可能獲得獎品的最大編號的隊伍編號」也是一樣的道理
要注意的是,不要和我一樣把1LL<<N寫成1<<N了
想說負數哪來的XD
害我debug好久QAQ
code:
#include<cstdio> #include<algorithm> #include<cassert> using namespace std; typedef long long LL; int N; LL P; LL MinRank(const LL u) { LL l=u,r=(1LL<<N)-1LL-u; LL ans=0LL; for(int i=N-1;i>=0;i--) { if(r>0LL) { r--; const LL sum=1LL+l+r; l/=2LL,r/=2LL; if(l+r<sum/2LL)l++; } else { assert(l>0LL); ans+=1LL<<i; l--; l/=2LL; } assert(1LL+l+r==(1LL<<i)); } assert(l==0LL&&r==0LL); return ans+1LL; } LL MaxRank(const LL u) { LL l=u,r=(1LL<<N)-1LL-u; LL ans=0LL; for(int i=N-1;i>=0;i--) { if(l>0LL) { ans+=1LL<<i; l--; const LL sum=1LL+l+r; l/=2LL,r/=2LL; if(l+r<sum/2LL)r++; } else { assert(r>0LL); r--; r/=2LL; } assert(1LL+l+r==(1LL<<i)); } assert(l==0LL&&r==0LL); return ans+1LL; } LL WeakWinner() { LL l=0LL,r=(1LL<<N)-1LL; while(l<r) { const LL mid=(l+r+1LL)/2LL; if(MinRank(mid)<=P)l=mid; else r=mid-1LL; } return r; } LL StrongLoser() { LL l=0LL,r=(1LL<<N); while(l<r) { const LL mid=(l+r)/2LL; if(MaxRank(mid)<=P)l=mid+1LL; else r=mid; } return r; } int main() { int testcase;scanf("%d",&testcase); while(testcase--) { scanf("%d%lld",&N,&P); printf("%lld %lld\n",StrongLoser()-1LL,WeakWinner()); } return 0; }
沒有留言:
張貼留言
歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原
注意:只有此網誌的成員可以留言。