题解 P2431 【正妹吃月饼】

· · 题解

这里挑战一下最短代码题解

看到 1,2,4,8,16... 我们就能想到这是一道关于位运算骚操作的题目。但是盲目遍历显然会T。那么怎么办呢？

经过一番思索瞎猜，我们可以发现一个规律：如果从高位到低位遍历，那么 a 和 b 在最高的不同的位之前都是不能动的。这么说可能有点不明白举个糖炒栗子：

a=16: 010000
b=25: 011001
        ↑
      就是它

我们暂且把它称为异位。这样我们就发现了一个好方法：把 a 异位后的所有位都填上 1，就珂以填充尽量多的 1 了。吼啊

但是这样还有一个问题，如果碰见这样的情况：

a=32: 100000
b=39: 100111
         ↑

也就是 b 在异位后全为 1，这样取到 b 更优。（然而数据太水，不判它都过了）

珂以证明，其他所有情况取到 1 的个数不会大于上面的取法。

接下来就是代码实现了：

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long x,y; scanf("%lld %lld",&x,&y);
    long long t=x^y; //取异位，这里偷了个懒，因为异位后面的1对答案没有影响
    while (t>0) t>>=1, x|=t; //把x异位后面填上1
    long long q=0; while (x>0) x&=x-1, q++; //判x中1的个数
    long long r=0; while (y>0) y&=y-1, r++; //判y中1的个数
    printf("%lld\n",max(q,r));
    return 0;
}