兔子的区间密码

兔子的区间密码

https://ac.nowcoder.com/acm/problem/20860

题意:
给与一个区间,求在区间选二个数的异或值最大为多少?

思路:
对于区间[L,R]:
①:L的二进制串长度小于R的二进制串长度,例如L=101(5),R=1110(14)。由于3<4,所以111和1000一定在[L,R]区间,因为1000为二进制长度为4的最小值,111为二进制长度为3的最大值。
②:L的二进制串长度等于R的二进制串长度,则在[L,R]区间中的每一个数的最高位都为1,最高位异或后一定为0,所以等价于求区间[L-(1<<(最高位)),R-(1<<(最高位))](去掉最高位)的答案。
特判:如果L=R,则输出0,因为二个相同的数异或为0.

代码:

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll inf=998244353;

inline ll read()
{
    ll x=0, y=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
        {
            y=-y;
        }
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*y;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll a=read(), b=read();
        if(a==b)
        {
            printf("0\n");
        }
        else
        {
            ll la=(ll)log2(a), lb=(ll)log2(b);
            while(la==lb&&a!=0)
            {
                a=a^(1LL<<la);
                b=b^(1LL<<lb);
                la=(ll)log2(a);
                lb=(ll)log2(b);
            }
            printf("%lld\n",(1LL<<(lb+1))-1);
        }
    }
    return 0;
}
全部评论

相关推荐

身边有人上海、深圳&nbsp;6、7k&nbsp;都去了,真就带薪上班了。
程序员小白条:木的办法, 以后越来越差,还是家附近宅着吧,毕业的人越来越多,岗位都提供不出来,经济又过了人口红利期
点赞 评论 收藏
分享
后来123321:别着急,我学院本大二,投了1100份,两个面试,其中一个还是我去线下招聘会投的简历,有时候这东西也得看运气
无实习如何秋招上岸
点赞 评论 收藏
分享
lllllkin:感觉可以精简到一页简历,有些排版感觉不是必须的。 时间线越早的,你自己越熟悉的放前面。描述可以更精简些,一些问题解决感觉可以不用写具体技术栈,卖个关子,等面试官问。
点赞 评论 收藏
分享
评论
10
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务