洛谷P2431 正妹吃月饼 题解

题目链接：P2431 正妹吃月饼

题意：

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

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

uim让正妹随便吃。

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

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

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

输入格式：

两个数，\(A,B\)。

输出格式：

正妹能吃到最多的数量

数据范围：

\(1 \le A,B \le 2^{63}-1\)

先吃块月饼再来写题解

显然我们会优先吃质量小的月饼。

但是怎么吃能保证正好在 \([A,B]\) 间呢？

不难发现，如果要吃满 \(A\) ，能获得的最大价值就是 \(\mathrm{popc}(A)\)

这里 \(\mathrm{popc}(x)\) 表示 \(x\) 在二进制下的 \(1\) 的个数。

证明很简单（其实靠直觉看的出来）

如果想尽可能吃小的，你会发现你不得不吃掉 \(A\) 二进制下最高位那个 \(1\) ，不然你到不了 \(A\) 。

所以我们只要从 \(A\) 开始从小到大一个一个（警觉）吃即可。

时间复杂度 \(\mathcal{O}(1)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

int a,b,c,d;
unsigned int t;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    
    cin >> a >> b; c=((1ll << 62) - 1) ^ a;
    d = __builtin_popcountll(a);
    for(; c; c-=t) if(a + (t=c&(-c)) <= b) a+=t, ++d; else break;
    cout << d << '\n';
    return 0;
}