[CCPC2016Hefei] I / HDU5969 作者: rin 时间: November 5, 2016 分类: Algo [http://acm.hdu.edu.cn/showproblem.php?pid=5969](http://acm.hdu.edu.cn/showproblem.php?pid=5969 "http://acm.hdu.edu.cn/showproblem.php?pid=5969") >###Problem Description >B君和G君聊天的时候想到了如下的问题。 给定自然数$$l$$和$$r$$ ,选取2个整数$$x,y$$满足$$l \leq x \leq y \leq r $$,使得$$x|y$$最大。 其中|表示按位或，即C、 C++、 Java中的|运算。 ###Input 包含至多10001组测试数据。 第一行有一个正整数，表示数据的组数。 接下来每一行表示一组数据，包含两个整数$$l$$,$$r$$。 保证 $$0 \leq l \leq r \leq 10^{18}$$。 ###Output 对于每组数据输出一行，表示最大的位或。 1.钦定上界就是$$y=r$$ :hj-huamoji52: 2.判断$$l$$和$$r$$二进制位数的大小关系$$lenL, lenR$$ 3.如果不相等，那么$$x=(111111\ldots )_{2}$$（$$lenR-1$$个1）一定大于等于$$l$$，小于等于$$r$$，那么$$l|r$$的结果就是$$2^{lenR}-1$$ 4.如果相等，令$$x=l$$，将$$x,r$$的最高位对齐，从高位往低位一位一位比较，把碰到的第一个不同的位$$i$$，置$$x[i]=0$$，再将$$x$$剩下的都置1 <!--more--> ```c++ #include <cstdio> #include <algorithm> #include <iostream> using namespace std; typedef long long LL; inline LL cntBit(LL a) { //计算a的二进制长度 LL cnt = 1; while (a >>= 1) { cnt++; } return cnt; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); int T; cin >> T; LL L, R; while (T--) { cin >> L >> R; LL LCnt = cntBit(L); LL RCnt = cntBit(R); if (LCnt < RCnt) { //如果两数长度不同，只需将较长的R 全部置1（除去R最高位的RCnt-1个1 大于 L） LL t = R; for (LL i = 0; i < RCnt-1LL; i++)t |= (1LL << i); cout << t << endl; } else if(LCnt == RCnt) { LL i = -1; for (i = LCnt-1; i >= 0LL; i--) { //若长度相同，从高到低找到第一个不同位i， LL mask = 1LL << (LL)i; if ((L&mask) == (R&mask)) continue; else break; } //因为要根据L来推X，所以以下直接用L代表X if (i > 0) //将L的i置零（保证L<R）然后将i之后的位都置1（保证L>左边界），这样的值满足题意 { LL tail = (1LL << i) - 1LL; //（都是1的部分） LL head = L & ((-1LL) & (1LL << i)); //（构造一个111110000之类的值来取L的高位） L = head | tail; } //cout << L << "|" << R << "=" << (L | R) << endl; cout << (L|R)<< endl; //Y=R } } return 0; } ``` 标签: none
看到代码就头晕了QAQ一说到算法就想打人
算法多美
窝一直想说两件让我很方的事：
1是你的头像
2是你文章里包含你学校的超链接……
看你方我也不知怎么方了起来