HDU – 5969 最大的位或 想法题

http://acm.hdu.edu.cn/showproblem.php?pid=5969 （合肥）区域赛签到题。。。orz

题意：给你l,r,求x|y的max，x,y满足l<=x<=y<=r.

题解：初始想法是找到形如（111，1000）、(11111,100000)····这样的进位点，一旦区间里有这种相邻两位进位的或一下就可以得到1111····，必然最大。（后面的是瞎搞）如果区间里没有，说明l,r二进制长度一样，于是从最高位往下找，一直找到不一样的一位，变成了前一种有进位的情况。这个算法的正确性完全没有证明，但是头铁。。结果一直wa。

正确的想法是对于二进制下r的每个0，去找在l,r区间是否存在一个数K可以把这个0变成1，顺便把剩下所有的数变成1.如果可以就输出变化后的数。

算法是从r的二进制最高位开始往底扫，遇到一个0，就找一个最大的数k，使得k|r将这一位的0变成1。然后判断一下k是否大于 l 。

找k的方法是将从r的第一个0开始的将其后面的数组全部变为0，然后-1，直观地看就是将第一个0前面的1变成0，后面全部变成1.

保存r二进制用一个数组，清零的时候维护一个sum简化操作。

ac代码

#define    _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
typedef long long ll;
ll l, r;
ll pow(ll x) {
    if (x == )return ;    ll s = ;
    while (x--) {
        s <<= ;
    }
    return s;
}
ll ans[];int main(){
    int t;
    cin >> t;
    while (t--) {
        cin >> l >> r;
        ll sum=;
        ll bit = ,  rr = r;
        int cnt = ;
        while (rr) { ans[cnt++] = (rr & ); rr >>= ; }        for(int i=;i<cnt;i++){
            if (ans[i] == ) {
                ll k = r - sum - ;
                if (k >= l)ans[i] = ;
            }
            else { sum += pow(i); }
        }
        sum = ;
        for (int i = ; i < cnt; i++){ sum += pow(i)*ans[i]; }
        cout << sum << endl;    }
}