洛谷 P2431 正妹吃月饼 解题报告

时间：2022-07-03 07:05:19

P2431 正妹吃月饼

题目描述

今天是中秋节。\(uim\)带来了一堆大小不同且味道各异的月饼。

这些月饼的质量分别是\(1g\),\(2g\),\(4g\),\(8g\),\(16g\)....后面一个是前面的2倍。每种只有一个。

uim让正妹随便吃。

正妹希望尝试尽可能多的口味，所以会吃尽可能多数量的月饼（不是重量）。而且她的确有些饿了，至少总共要吃掉\(A\) \(g\)的月饼才能满足。

然而正妹怕长胖，所以吃月饼不能合计超过\(B\) \(g\)。

她希望知道自己最多能吃多少个月饼

输入输出格式

输入格式：

两个数,\(a,b\)

输出格式：

正妹能吃到最多的数量

说明

30%数据，\(A,B<=1000\)

60%数据，\(A,B<=100000\)

100%数据，\(A,B<=2^{63}-1\)

我们当然不可以直接枚举，（其实枚举也可以跑过）

把\(B\)进行二进制拆分以后，对于每个位的1，我们可以把它去掉，然后直接把比它低的位全置1，从高到低枚举1，当第一次产生的新数比\(A\)大时，贪心的去想，就是答案了。

积累了一个错误点：1<<n

1<<n 会爆掉int！！！ 最好搞个变量one来弄

Code:

#include <cstdio>

#define ll long long

ll a,b;

ll max(ll x,ll y){return x>y?x:y;}

ll cal(ll x)

{

    ll cnt=0;

    while(x) x-=x&-x,cnt++;

    return cnt;

}

int main()

{

    scanf("%lld%lld",&a,&b);

    ll tmp=b,len=0,ans=0;

    while(tmp) len++,tmp>>=1;

    ans=max(cal(b),ans);

    ll one=1;

    for(ll i=len;i;i--)

    {

        if((b>>i-1)&1)

        {

            ll t=b^(one<<i-1);

            t|=(one<<i-1)-1;

            if(t>=a)

                ans=max(cal(t),ans);

        }

    }

    printf("%lld\n",ans);

    return 0;

}

2018.7.11

相关文章