【SPOJ】25844 MAXXOR - Find the max XOR value

第一眼:哇,枚举。

第二眼:哇, L , R ⩽ 1 0 9 L,R\leqslant 10^9 L,R109

枚举是不可能的了。

这时我们就需要动一下脑子。

分两种情况:

L = R L=R L=R L ≠ R L\not = R L=R

L = R L=R L=R 的时候,直接输出 0 就可以了。

L ≠ R L \not = R L=R 的时候:设 x = L ⊕ R x = L \oplus R x=LR,那么答案为最小的 2 k − 1 2^k-1 2k1 2 k − 1 ⩾ x 2^k-1 \geqslant x 2k1x 也就是 2 k > x 2^k > x 2k>x

证明如下:

第一步:证明没有例外。

我们想让异或之后二进制下最高位尽量高,我们就先取最大的 R R R,然后再取一个数使得该位尽量为 0 0 0

如果 L L L 这一位是 1 1 1,我们都知道异或是不进位加法, 1 ⊕ 1 1 \oplus 1 11 当然等于 0 0 0,不用考虑这一位。找后面的也同理。

如果 L L L 这一位是 0 0 0 符合上述条件,此时答案最高位和 x x x 都相同。而 2 k − 1 2^k-1 2k1 是最高位相同的最大的数,所以答案一定不超过 2 k − 1 2^k-1 2k1

第二步:证明可以取到。

以下称在二进制里表示 2 i 2^i 2i 的那一位叫做第 i i i 位。

因为 x = L ⊕ R x=L \oplus R x=LR,在第 k − 1 k-1 k1 位为 1 1 1,说明 L ∼ R L \sim R LR 之间有一个位置的第 k − 1 k-1 k1 位发生了变化。而且 L ∼ R L \sim R LR 是要一起变化的,每次都要加 1 1 1,意思就是肯定有一个位置从 111 … 1 111 \dots 1 1111(一共 k − 1 k-1 k1 1 1 1),变成了 100 … 0 100 \dots 0 1000(一共 k − 1 k-1 k1 0 0 0)。所以这两个数异或起来为 2 k − 1 2^k-1 2k1

证明完毕。理论存在,实践,开始!

#include<bits/stdc++.h>
using namespace std;
int l,r;
int main(){cin>>l>>r;r^=l;for(int i=0;;i++){if(1<<i>r){ cout<<(1<<i)-1;//这里不打括号就会CE,别问我怎么知道的。(哭)  break;}}return 0;
}

去掉头文件和 namespace 只有 12 12 12 行,太简便了。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/24487.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Linux:进程信号(二.信号的保存与处理、递达、volatile关键字、SIGCHLD信号)

目录 1.信号保存 1.1递达、未决、阻塞等概念 1.2再次理解信号产生与保存 1.3信号集操作函数 sigset_t类型 sigemptyset() 函数 sigismember()函数 sigaddset ()函数 sigdelset() 函数 sigprocmask()系统调用 sigpending()系统调用 2.信号的处理/递达 2.1信号处理时…

【JavaEE】SpringMVC获取HTTP中的元素

目录 一、获取URL中的参数PathVariable二、上传⽂件RequestPart三、获取Cookie/Session3.1 HttpServletRequest和 HttpServletResponse3.2 获取Cookie3.2.1 使用HttpServletRequest3.2.2 使用注解CookieValue 3.3 设置session3.4 获取session3.4.1 使用HttpServletRequest3.4.2…

React低代码项目:用户登陆

吐司问卷&#xff1a;用户登陆 Date: February 17, 2025 4:12 PM (GMT8) JWT **概念&#xff1a;**登陆成功后&#xff0c;服务端返回一个 token JWT组成&#xff1a; JWT 由三个部分组成&#xff1a;头部&#xff08;Header&#xff09;、载荷&#xff08;Payload&#xf…

集合与反射

一、集合体系 集合一共分为两部分&#xff1a;Collection&#xff08;单列集合&#xff09;每个元素&#xff08;数据&#xff09;只包含一个值。 Map&#xff08;双列集合&#xff09;每个元素包含两个值&#xff08;键值对&#xff09;。 二、ArrayList和LinkedList的区别 数…

ubuntu:桌面版磁盘合并扩容

下载gparted磁盘编辑器 apt-get install gparted 打开gparted 更改目标分区大小 当遇到这个报错时&#xff0c;需要在命令行执行原分区的挂载指令 查看该分区信息 记住该目录&#xff0c;并在命令行执行 mount -o remount -rw /# 示例&#xff1a;mount -o remount -rw /v…

全国各省山峰分布SHP数据详解及其在科学研究与旅游规划中的应用

一、引言 在中国这片广袤无垠的土地上&#xff0c;山峰作为自然界的壮丽景观&#xff0c;不仅构成了大地的骨架&#xff0c;更承载着丰富的自然资源和深厚的文化底蕴。 全国各省山峰分布SHP数据&#xff0c;作为一种地理信息系统&#xff08;GIS&#xff09;中的矢量数据格式…

向量数据库milvus部署

官方文档 Milvus vector database documentationRun Milvus in Docker (Linux) | Milvus DocumentationMilvus vector database documentation 按部署比较简单&#xff0c;这里说一下遇到的问题 一&#xff1a;Docker Compose 方式部署 1、镜像无法拉取,(docker.io被禁) …

Java 基础面试题

&#x1f9d1; 博主简介&#xff1a;CSDN博客专家&#xff0c;历代文学网&#xff08;PC端可以访问&#xff1a;https://literature.sinhy.com/#/literature?__c1000&#xff0c;移动端可微信小程序搜索“历代文学”&#xff09;总架构师&#xff0c;15年工作经验&#xff0c;…

清华大学《AIGC发展研究3.0》

大家好&#xff0c;我是吾鳴。 AIGC已经爆火好长一段时间了&#xff0c;特别是DeepSeek的爆火&#xff0c;直接让很多之前没有体会过推理模型的人可以免费的使用上推理模型&#xff0c;同时DeepSeek产品形态也是全球首创&#xff0c;就是直接把AI的思考过程展示给你看&#xff…

苹果CMS泛目录站群架构:无缓存刷新技术的SEO实战

一、技术背景与行业痛点 传统泛目录站群系统普遍依赖静态缓存机制&#xff0c;导致两个核心问题&#xff1a; 缓存臃肿&#xff1a;运行3-6个月后缓存文件可达数百GB量级&#xff0c;严重影响服务器性能内容僵化&#xff1a;缓存机制导致页面TDK&#xff08;标题/描述/关键词…

iview table组件中修改按钮时 要注意是否真的修改了值

如图所示&#xff0c; switch按钮的默认值用dj来控制&#xff0c;但是如果没有加事情去修改切换后的值的话&#xff0c;那么他只会修改本身的显示值&#xff0c;但是我们需要跟着修改的列表数据的dj值是不会修改的&#xff0c;所以要注意&#xff0c;一定要加上事情去修改确定的…

Go中slice和map引用传递误区

背景 关于slice和map是指传递还是引用传递&#xff0c;很多文章都分析得模棱两可&#xff0c;其实在Go中只有值传递&#xff0c;但是很多情况下是因为分不清slice和map的底层实现&#xff0c;所以导致很多人在这一块产生疑惑&#xff0c;下面通过代码案例分析slice和map到底是…

Linux网络基础(协议 TCP/IP 网络传输基本流程 IP VS Mac Socket编程UDP)

文章目录 一.前言二.协议协议分层分层的好处 OSI七层模型TCP/IP五层(或四层)模型为什么要有TCP/IP协议TCP/IP协议与操作系统的关系(宏观上是如何实现的)什么是协议 三.网络传输基本流程局域网(以太网为例)通信原理MAC地址令牌环网 封装与解包分用 四.IP地址IP VS Mac地址 五.So…

python-leetcode-乘积最大子数组

152. 乘积最大子数组 - 力扣&#xff08;LeetCode&#xff09; class Solution:def maxProduct(self, nums: List[int]) -> int:if not nums:return 0max_prod nums[0]min_prod nums[0]result nums[0]for i in range(1, len(nums)):if nums[i] < 0:max_prod, min_prod…

图像处理之图像边缘检测算法

目录 1 图像边缘检测算法简介 2 Sobel边缘检测 3 经典的Canny边缘检测算法 4 演示Demo 4.1 开发环境 4.2 功能介绍 4.3 下载地址 参考 1 图像边缘检测算法简介 图像边缘检测是计算机视觉和图像处理中的基本问题&#xff0c;主要目的是提取图像中明暗变化明显的边缘细节…

React 源码揭秘 | Effect更新流程

前面的文章介绍了 hooks和commit流程&#xff0c;算是前置知识&#xff0c;这篇来讨论一下useEffect的原理。 useEffect用来处理副作用&#xff0c;比如网络请求&#xff0c;dom操作等等, 其本质也是个hooks&#xff0c;包含hooks的memorizedState, updateQueue, next Effec…

【Linux】vim 设置

【Linux】vim 设置 零、起因 刚学Linux&#xff0c;有时候会重装Linux系统&#xff0c;然后默认的vi不太好用&#xff0c;需要进行一些设置&#xff0c;本文简述如何配置一个好用的vim。 壹、软件安装 sudo apt-get install vim贰、配置路径 对所有用户生效&#xff1a; …

qt-C++笔记之QtCreator新建项目即Create Project所提供模板的逐个尝试

qt-C笔记之QtCreator新建项目即Create Project所提供模板的逐个尝试 code review! 文章目录 qt-C笔记之QtCreator新建项目即Create Project所提供模板的逐个尝试1.Application(Qt):Qt Widgets Application1.1.qmake版本1.2.cmake版本 2.Application(Qt):Qt Console Applicati…

Vue 项目中配置代理的必要性与实现指南

Vue 项目中配置代理的必要性与实现指南 在 Vue 前端项目的开发过程中&#xff0c;前端与后端地址通常不同&#xff0c;可能引发跨域问题。为了在开发环境下顺畅地请求后端接口&#xff0c;常常会通过配置**代理&#xff08;proxy&#xff09;**来解决问题。这篇文章将详细解析…

Linux运维命令-三剑客(grep awk sed)

目录 1.简介 2.命令详解 2.1.grep命令 2.1.1.功能 2.1.2.常见的使用场景及命令 2.2.awk命令 2.2.1.功能 2.2.2.常见的使用场景及命令 2.3.sed命令 2.3.1.功能 2.&#xff13;.2.常见的使用场景及命令 3.总结 1.简介 在Linux中&#xff0c;grep、awk、sed 命令常被称…