网课:第二章模拟、枚举与贪心---兔子的区间密码

2024-05-16 00:20

本文主要是介绍网课:第二章模拟、枚举与贪心---兔子的区间密码,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

链接:登录—专业IT笔试面试备考平台_牛客网
来源:牛客网
 

题目描述

有一只可爱的兔子被困在了密室了,密室里有两个数字,还有一行字:
只有解开密码,才能够出去。
可爱的兔子摸索了好久,发现密室里的两个数字是表示的是一个区间[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

输入描述:

第一行一个数 T,表示数据组数。
接下来 T 行,每行两个数 L,R, 表示区间[L,R]。

输出描述:

输出共T行每行一个整数,表示[L,R]的密码。

示例1

输入

5
1 10
2 3
3 4
5 5
2 5

输出

15
1
7
0
7

备注:

对于30%的数据 
1  ≤ T ≤ 10 
0 ≤ L ≤ R ≤ 100
对于另外10%的数据 
L=R
对于70%的数据 
1 ≤ T ≤ 10 
0 ≤ L ≤ R ≤ 50000
对于100%的数据 
1 ≤ T ≤ 10000 
0 ≤ L ≤ R ≤ 1018
(对于100%的数据) 输入数据较大,请使用快速读入。

做法

这题也是挺巧妙的,完全没想到,只能说学习学习吧。

从第一位开始对比 l 和 r 的二进制数,直到遇到不同的位,构造两个二进制数,一个前几位相同的加上0剩下的全是1,另一个前几位相同的加上1剩下全是0。构造的两个二进制数都在 l 和 r 的范围内,且异或值最大

#include<bits/stdc++.h>
using namespace std;
int t;
long long l,r;
long long ksm(int a,int b) {//快速幂long long tmp=a,ans=1;while(b){if( (b & 1) == 1)  ans*=tmp;tmp*=tmp;b>>=1;}return ans;
}
long long read(){//快读long long x=0;int f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
int main(){scanf("%d",&t);while(t--){l=read();r=read();if(l==r){cout<<0<<endl;continue;}string a,b;while(r){b+=r%2+'0';r/=2;a+='0';}int cnt=0;while(l){a[cnt++]=l%2+'0';l/=2;}int idex;for(int i=a.size()-1;i>=0;i--){if(a[i]!=b[i]) {idex=i;break;}}for(int i=idex-1;i>=0;i--){a[i]='1';b[i]='0';}long long ans=0;for(int i=0;i<a.size();i++){if(a[i]!=b[i]) ans+=ksm(2,i);}cout<<ans<<endl;}
}

wa的原因:

没用快速幂

这篇关于网课:第二章模拟、枚举与贪心---兔子的区间密码的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/993339

相关文章

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

SpringSecurity 认证、注销、权限控制功能(注销、记住密码、自定义登入页)

《SpringSecurity认证、注销、权限控制功能(注销、记住密码、自定义登入页)》SpringSecurity是一个强大的Java框架,用于保护应用程序的安全性,它提供了一套全面的安全解决方案... 目录简介认识Spring Security“认证”(Authentication)“授权” (Auth

CSS模拟 html 的 title 属性(鼠标悬浮显示提示文字效果)

《CSS模拟html的title属性(鼠标悬浮显示提示文字效果)》:本文主要介绍了如何使用CSS模拟HTML的title属性,通过鼠标悬浮显示提示文字效果,通过设置`.tipBox`和`.tipBox.tipContent`的样式,实现了提示内容的隐藏和显示,详细内容请阅读本文,希望能对你有所帮助... 效

Oracle登录时忘记用户名或密码该如何解决

《Oracle登录时忘记用户名或密码该如何解决》:本文主要介绍如何在Oracle12c中忘记用户名和密码时找回或重置用户账户信息,文中通过代码介绍的非常详细,对同样遇到这个问题的同学具有一定的参... 目录一、忘记账户:二、忘记密码:三、详细情况情况 1:1.1. 登录到数据库1.2. 查看当前用户信息1.

SpringBoot使用Jasypt对YML文件配置内容加密的方法(数据库密码加密)

《SpringBoot使用Jasypt对YML文件配置内容加密的方法(数据库密码加密)》本文介绍了如何在SpringBoot项目中使用Jasypt对application.yml文件中的敏感信息(如数... 目录SpringBoot使用Jasypt对YML文件配置内容进行加密(例:数据库密码加密)前言一、J

MySQL9.0默认路径安装下重置root密码

《MySQL9.0默认路径安装下重置root密码》本文主要介绍了MySQL9.0默认路径安装下重置root密码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录问题描述环境描述解决方法正常模式下修改密码报错原因问题描述mysqlChina编程采用默认安装路径,

MySQL修改密码的四种实现方式

《MySQL修改密码的四种实现方式》文章主要介绍了如何使用命令行工具修改MySQL密码,包括使用`setpassword`命令和`mysqladmin`命令,此外,还详细描述了忘记密码时的处理方法,包... 目录mysql修改密码四种方式一、set password命令二、使用mysqladmin三、修改u

电脑密码怎么设置? 一文读懂电脑密码的详细指南

《电脑密码怎么设置?一文读懂电脑密码的详细指南》为了保护个人隐私和数据安全,设置电脑密码显得尤为重要,那么,如何在电脑上设置密码呢?详细请看下文介绍... 设置电脑密码是保护个人隐私、数据安全以及系统安全的重要措施,下面以Windows 11系统为例,跟大家分享一下设置电脑密码的具体办php法。Windo

数据库oracle用户密码过期查询及解决方案

《数据库oracle用户密码过期查询及解决方案》:本文主要介绍如何处理ORACLE数据库用户密码过期和修改密码期限的问题,包括创建用户、赋予权限、修改密码、解锁用户和设置密码期限,文中通过代码介绍... 目录前言一、创建用户、赋予权限、修改密码、解锁用户和设置期限二、查询用户密码期限和过期后的修改1.查询用

C#实现获得某个枚举的所有名称

《C#实现获得某个枚举的所有名称》这篇文章主要为大家详细介绍了C#如何实现获得某个枚举的所有名称,文中的示例代码讲解详细,具有一定的借鉴价值,有需要的小伙伴可以参考一下... C#中获得某个枚举的所有名称using System;using System.Collections.Generic;usi