【henuacm2016级暑期训练-动态规划专题 C】Little Girl and Maximum XOR

在这里输入题意

【题解】

考虑r最后的二进制形式为 1xxxxx 那么我们肯定想让第一个最高位的1保留。因此我们选取的另外一个数字一定是 0xxxxx的形式。那么我们贪心地选取数字b=01111..1 然后看看这个数字b是否大于等于L 如果满足,显然它也是满足小于等于R的。那么我们选取的a=100000..0 那么结果显然就是最大的了。为11111...11

但是
如果b<L
那么我们就显然不能满足最后的结果第一位是1了。
所以b的第一位也只能是1了。
即
a=1xxxxxx
b=1xxxxxx
那么我们接着看a的第二位,(也即R的第二位
如果R的第二位为0
那么我们很想让b的第二位为1
但是不行。
因为这样的话。
b>a>R
所以b的第二位只能为0
也即如R的第i位为0的话。
选取的b的相应位上的数字也只能为0
现在我们得到了
a=10xxxx
b=10xxxx
接下来根据R第三位是否为1.
可以得到相应的方案:
1.为0,那么b的相应位也为0
2.为1,那么把b的这一位置为0,后面全都置为1,看看是不是大于等于L,是的话,a的这一位后面一直到结束都置为0.
按照这样的贪心策略搞就好。

【代码】

/*
    f[i][j][k]前i个位置,第i个位置放j这个颜色,然后形成了k个联通块的最小花费

*/
#include <bits/stdc++.h>
using namespace std;

const int N = 100;

long long l,r;
long long two[N+10];
int a[N+10],b[N+10];

int main()
{
    #ifdef LOCAL_DEFINE
        freopen("D:\rush.txt","r",stdin);
    #endif // LOCAL_DEFINE

    ios::sync_with_stdio(0),cin.tie(0);
    cin >> l >> r;
    two[0] = 1;
    for (int i = 1;i <= 61;i++) two[i] = two[i-1]*2;
    int cnt = -1;
    while (r>0){
        a[++cnt] = r%2;
        r>>=1;
    }

    for (int i = cnt;i >= 0;i--){
        if (a[i]==0) continue;

        //a[i]==1
        long long temp = 0;
        for (int j = 0;j < i;j++) temp+=two[j];
        for (int j = i+1;j <= cnt;j++)
            if (a[j]==1)
                temp+=two[j];
        if (temp>=l){
            for (int j = i+1;j <= cnt;j++)
                if (a[j]==1)
                    temp-=two[j];
            temp+=two[i];
            cout<<temp<<endl;
            return 0;
        }
    }
    cout<<0<<endl;
    return 0;
}