贪心——HDU-5969 最大的位或

HDU-5969：http://acm.hdu.edu.cn/showproblem.php?pid=5969

一开始也是分了类，觉得要两种情况，l 与 r 位数相同与不同的情况，仔细想一下，可以一起处理，从最高位（左侧符号位）开始，遇到不同后面全部补1即可。

刚写好交信心满满，一交就Wrong answer，写了一个暴力求的对数器，确定算法是对的，也知道了问题在哪。

第一，数据相同时，没有结果，要处理。
第二，碰到不同后，将 r 后面的全部置1：
```
 r = r | (t << s);
```
一开始写的是 r = r | (1 << s); 我用了1，1默认是int，左移超过31，就超范围了。

#include <iostream>

using namespace std;

typedef long long ll;

int main() {

    ll l, r,t=;

    int N;

    cin >> N;

    while (N--) {

        while (cin >> l >> r) {

            int s = ;

            if (l == r) {

                cout << l << endl;

                continue;

            }

            if (l > r)swap(l, r);

            while (((l >> s) & ) == ((r >> s) & )) {

                s--;

            }

            while (s--) {

                r = r | (t << s);

            }

            cout << r << endl;

        }

    }

    return ;

}

心得：贪心法，找普遍规律，处理特殊数据，不要老想知道为什么这样解，用暴力法检验算法的正确性，算法的证明是数学家的事。

巴特西

贪心——HDU-5969 最大的位或

最新文章

热门文章