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;

    }

}