由于每个质量的月饼只有一个,并且质量恰好是2的整数倍,所以考虑将一个质量看成一个二进制位。
那么也就是说,我们要构造一个二进制数 \(x\),使得 \(x\) 的 \(1\) 的个数最多,且满足 \(a\le x \le b\)。
那么这就可以用类似数位 \(DP\) 的思路来做,从高位往低位看,若 \(a_i=b_i=1\),那么这一位只能填 \(1\);若 \(a_i=b_i=0\),这一位只能填 \(0\);若 \(a_i=0,b_i=1\),我们在这一位填 \(0\),之后的每一均填 \(1\) 即可满足约束条件。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a,b;
int lena,lenb;
int sa[100],sb[100];
int main() {
cin>>a>>b;
vector<int> s1,s2;
while(a) {s1.push_back(a%2); a/=2;}
while(b) {s2.push_back(b%2); b/=2;}
for(int x:s1) sa[++lena]=x;
for(int x:s2) sb[++lenb]=x;
int ans=0;
for(int i=lenb;i>=1;i--) {
if(sa[i]==1&&sb[i]==1) ans++;
if(sa[i]==0&&sb[i]==1) {
ans+=i-1;
break;
}
}
cout<<ans;
return 0;
}