2016年1月14日 星期四

[HOJ 278][GCJ 2013 2]Many Prizes

HOJ生病惹QQ,因此我在這裡做了題目備份,請參考~

以尋找「一定會獲得獎品的最大編號的隊伍編號」為例
首先,隊伍編號和最差名次有單調性
因此我們可以二分搜隊伍編號,看看他最差的名次會是多少
至於最差的名次要怎麼求呢?
可以發現,在比了第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誤判成垃圾留言,小莫會盡快將其手動還原

注意:只有此網誌的成員可以留言。