兔子的区间密码

兔子的区间密码

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

题意:
有一只可爱的兔子被困在了密室了,密室里有两个数字,还有一行字:
只有解开密码,才能够出去。
可爱的兔子摸索了好久,发现密室里的两个数字是表示的是一个区间[L,R]
而密码是这个区间中任意选择两个(可以相同的)整数后异或的最大值。
比如给了区间[2,5] 那么就有2 3 4 5这些数,其中 2 xor 5=7最大 所以密码就是7。
兔子立马解开了密室的门,发现门外还是一个门,而且数字越来越大,兔子没有办法了,所以来求助你。
提示:异或指在二进制下一位位比较,相同则 0 不同则 1
例如2=(010)22=(010)_22=(010)2​ 5=(101)25=(101)_25=(101)2​
所以2 xor 5=(111)2=75=(111)_2=75=(111)2​=7

题解:
首先我们让l r直接xor一下
假设
l 二进制 1010
r 二进制 1100
那么两者xor会得到 0110的结果
发现最高位发生了变化 你会发现 最大值是 0100 xor 0011
这两个值是怎么来的呢,是x 于 y 异或后的最高位 异或后得出的结果
当然如果两者最高位不相同,那么异或后的最高位肯定是那个较大的数的最高位。
如果异或后的最高位是i,那么结果就是.

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
#include <queue>
#include <string>
const int maxn = 60;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9+7;
using namespace std;


int main(){
    int t;
    cin>>t;
    while(t--){
        ll x,y;
        scanf("%lld%lld",&x,&y);
        ll temp=x^y;
        ll ans=1;
        while(temp){
            temp/=2;
            ans*=2;
        }
        printf("%lld\n",ans-1);
    }
}
题解 文章被收录于专栏

主要写一些题目的题解

全部评论

相关推荐

01-12 14:08
门头沟学院 Java
有寒假来武汉小米总部实习的大学生嘛,我也是小米的员工,想找合租舍友,仅限女生可免租半月,二月初可入住,也就是说房租是2.15开始算的哦~也可以将行李提前放过来~房屋介绍:1、房子情况:有电梯;租的是三室一厅一卫一厨,&nbsp;但是有个卧室比较小,不打算找人,只住两个人就可以了;衣柜也很大,可以放下很多衣服;房屋采光真的很好,早上起来可以在床上晒太阳的那种,十分惬意(夏季晚上十分好看!)2.&nbsp;楼下离我们很近的地方有小吃街和一个两层大超市(大概步行两分钟多就可以走到)&nbsp;,还有一个新开的麦当劳,晚上可以去吃小吃,购买物资也可以去大超市;3.&nbsp;房子基本设施齐备(洗衣机,冰箱,空调,油烟机,热水器);4.&nbsp;我有稳定的工作,生活中很注意卫生,周末有时间会自己做饭,可以投喂哦~5.&nbsp;出行:距离公交站步行10分钟不到,距政务中心,武汉小米总部三站(晚上我都是走回来的,很近的~);一个比较进的地铁,距离大概1km左右;出入我觉得很方便;6.&nbsp;房租:1150每月,押一付二,无物业费,也没有中介费和其他额外费用。7.&nbsp;民用水电燃气,用多少交多少,水电费正常平摊。希望你是:1.&nbsp;女生(本人女),不带异性回家,如有同性朋友来玩,最多过夜一晚;2.&nbsp;爱干净,讲卫生,作息正常,不吵闹,有稳定工作;3.&nbsp;好沟通,有任何问题一定要沟通,不要闷着!中介勿扰,非诚勿扰!!!希望不要浪费彼此的时间诚心有意向的可以联系我看房
租房找室友
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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