AcWing3485. 最大异或和

news/2024/3/29 22:32:40/文章来源:https://blog.csdn.net/weixin_41179697/article/details/129244212

先看题目:

说实话,我看到这道题就想用滑动窗口,但是滑了一下发现不太对啊,如果我用滑动窗口的话,那么最后肯定是一个固定长度为m的窗口在持续计算,区间长度小于m的区间的异或和肯定会被遗漏。然后我就想怎么用Trie树来解决这道题,但是我没想明白呜呜呜。

所以前去看了y总的视频题解。

先大致说一下什么是Trie树好了,Trie也叫字典树,它的核心就是通过存储不同字符串的公共前缀来减少查找字符串的时间。

 

看图,对于abuse和about这两个字符串,我们想把他们放到Trie树种,发现他们俩有共同的前缀ab,所以就在b后面开始分叉,然后各走各的分叉。

这道题就是在这个基础上做的。

然后这道题求的是区间的异或和,所以我们还得知道异或的一个特性。我们遍历数组,计算每个前缀的异或和,如果我们想要计算一个区间[i,j]的异或值,那么我们就可以用s[i,j]=s[j]^s[i - 1]求取。为什么可以这么算呢?这是因为一个数和本身异或,结果为0.

好,又一个知识点出来了。

那么现在开始看题:

因为数据范围是2^31-1,那么异或和也最多是31位二进制,也就是说最多是31位二进制就能表示每个数字,那么从0到30就对应异或和的二进制位。

先不考虑区间长度最大为M,我们要找到的是最大的异或和,怎么怎么找呢?

目前我们在Trie树中存储了j以前的前缀异或和,如果想找到一个前缀异或和s[i]和s[j]的异或结果最大的话,应该怎么处理呢?

我们知道异或的计算方法:1^0 = 1, 0 ^ 0 = 0, 1 ^ 1 = 0;那么现在我们有一个s[j],想得到一个和它异或后的最大结果,就要保证最高位尽可能地不同。

假如s[j] = 10101001,那么我们在遍历这棵Trie树的时候,希望能够找到最高位为0的节点,这样才能使异或结果的最高位为1,如果找不到为0的节点,那么只好找最高位为1的节点,尽量保证接下来遍历的节点和s[j]的异或结果为1好了。

这个就是当区间长度不限时我们的计算方式,但是现在题目要求长度最大为M,怎么办呢?去Trie树中删掉吗,好像有点难呢。我们在这里采用伪装删除的方法,用cnt记录经过这个节点的元素的个数。如果要删除某个元素,那么就找到这个元素对应的最后一个结束节点,把它的cnt值-1好了。所以如果我们发现当前遍历到了i>m的前缀异或,为了保证窗口中最多有m个异或和,我们必须删除最前面的异或和,也就是s[i - m - 1]这个异或和了。

 

代码来喽:

#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<cmath>
#include<cstring>
#include<algorithm>
//#define ll long long
const int N = 100010 * 31;  //最多是1e5,每个数最多31位,所以最多一共31*1e5个节点
int cnt[N];
int s[N];  //前缀异或和 
int son[N][2];
int idx;
using namespace std;
void insert(int x, int v){int p = 0;for(int i = 30; i >= 0; i--){  int u = (x >> i) & 1;//如果当前节点没有这个分叉,那么我们就新建一个分叉,这个idx可以认为是不同分叉的编号//用这个idx可以获取到每个分叉,然后就可以从这个分叉接着往下走了if(!son[p][u]) son[p][u] = ++idx;  p = son[p][u];  //从这个分叉往下走cnt[p] += v;  //经过这个分叉的元素的个数+1或者-1,增加一个元素或者删除一个元素} 
} 
int query(int x){int res = 0;int p = 0;for(int i = 30; i >= 0; i--){ //一定要从最高位开始往下,因为我们希望能够保证最高位最大 int u = x >> i & 1;if(cnt[son[p][!u]]) {  //能够保证和当前位不同,异或结果为1p = son[p][!u];//在整理这个异或和,当前位异或值为1,可以认为之前的结果为res,//现在在res后面又加了一位1,那么现在的结果就是res*2+1res = res * 2 + 1;  }else {p = son[p][u];res = res * 2;}}return res; 
}
int main(){int n, m;scanf("%d%d", &n, &m);int x;for(int i = 1; i <= n; i++){scanf("%d", &x);s[i] = s[i - 1] ^ x; }int res = 0;insert(s[0], 1);  //1代表插入一个数for(int i = 1; i <= n; i++){//删除最前面的元素,例如当i = m+1,那么就把s[0]删除,因为他不在长度为m的窗口内部了。//现在树中有if(i > m) insert(s[i - m - 1], -1); res = max(res, query(s[i]));  //找到和s[i]异或后的最大结果insert(s[i], 1); //别忘了把这个添加到树中} printf("%d\n", res);return 0;
} 

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

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

相关文章

FSP:Flow of Solution Procedure (CVPR 2017) 原理与代码解析

paper&#xff1a;A Gift From Knowledge Distillation: Fast Optimization, Network Minimization and Transfer Learningcode&#xff1a;https://github.com/HobbitLong/RepDistiller/blob/master/distiller_zoo/FSP.py背景深度神经网络DNN逐层生成特征。更高层的特征更接近…

决策树在sklearn中的实现

目录 一.模块sklearn.tree 二.建模基本流程 三.DecisionTreeClassifier重要参数 1.criterion 2.random_state & splitter 3.剪枝参数max_depth 4.剪枝参数min_samples_leaf & min_samples_split 5.max_features & min_impurity_decrease 6.class_weight …

Python IDE:对于 Python 初学者来说,最好的 IDE 是什么?

Python 是科技界最简单、使用最广泛的编程语言之一。它是一种高级通用编程语言&#xff0c;强调代码可读性并使用面向对象的方法。Python可以用来完成很多任务&#xff0c;包括网站开发、软件开发、 自动化 和数据分析 专业开发人员使用Python开发各种流行的软件程序&#xff0…

深入理解Spring MVC上

Spring MVC 是一种基于 Spring 框架的 Web 框架&#xff0c;它提供了一种基于 Model-View-Controller&#xff08;MVC&#xff09;的设计模式&#xff0c;用于构建 Web 应用程序。在 Spring MVC 中&#xff0c;Controller 接受并处理 HTTP 请求&#xff0c;并将其转发给适当的 …

多表left join 慢sql问题

作为个人记录&#xff0c;后续再填坑a对p是1对多 ,p对llup 1对多SELECTa.id,p.id,t1.id FROMliv_series_product aINNER JOIN liv_product p ON p.id a.product_idLEFT JOIN ( SELECT llup.id, llup.product_id, llup.room_id FROM liv_live_user_product llup WHERE llup.ro…

Tomcat部署及多实例

Tomcat部署及多实例一、Tomcat简介1、Tomcat核心组件2、什么是JSP二、Tomcat数据流向1、Tomcat数据流向2、Tomcat-Nginx数据流向三、Tomcat服务部署安装1、安装jdk包2、解压Tomcat所需的安装包3、在/etc/profile添加环境变量4、启动服务并查看5、在浏览器网页验证6、创建用户&a…

为什么硬件性能监控很重要

当今的混合网络环境平衡了分布式网络和现代技术的实施。但它们并不缺少一个核心组件&#xff1a;服务器。保持网络正常运行时间归结为监控和管理导致网络停机的因素。极有可能导致性能异常的此类因素之一是硬件。使用硬件监控器监控网络硬件已成为一项关键需求。 硬件监视器是…

优化知识管理方法丨整理零碎信息,提高数据价值

信息流时代&#xff0c;知识成集合倍数增长&#xff0c;看似我们学习了很多知识&#xff0c;但知识零碎无系统&#xff0c;知识之间缺乏联系&#xff0c;没有深度&#xff0c;所以虽然你很努力&#xff0c;但你发现自己的能力增长特别缓慢&#xff0c;你需要整理知识将零散的知…

蓝桥杯:染色时间

蓝桥杯&#xff1a;染色时间https://www.lanqiao.cn/problems/2386/learning/?contest_id80 问题描述 输入格式 输出格式 样例输入输出 样例输入 样例输出 评测用例规模与约定 解题思路&#xff1a;优先队列 AC代码(Java)&#xff1a; 问题描述 小蓝有一个 n 行 m 列…

std::chrono笔记

文章目录1. radio原型作用示例2. duration原型&#xff1a;作用示例3. time_point原型作用示例4. clockssystem_clock示例steady_clock示例high_resolution_clock先说感觉&#xff0c;这个库真恶心&#xff0c;刚接触感觉跟shi一样&#xff0c;特别是那个命名空间&#xff0c;太…

vue2 diff算法

diff是什么 diff 算法是一种通过同层的树节点进行比较的高效算法 其有两个特点&#xff1a; ♥比较只会在同层级进行, 不会跨层级比较 ♥在diff比较的过程中&#xff0c;循环从两边向中间比较 diff 算法的在很多场景下都有应用&#xff0c;在 vue 中&#xff0c;作用于虚拟 dom…

预备2-CMD常用命令

CMD常用命令 先学简单常用的, 其余的要用在学 打开Cmd窗口 Win键R> 输入Cmd回车鼠标点击开始 > 附件>Cmd打开一个窗口,在地址栏输入cmd 操作目录 1.dir 查询当前目录有哪些文件 2.cd.. 上一级目录 3.cd e: 切换到E盘 4.d: 直接去d盘 5.cd /d e:abc 直接去E盘的abc目…

2023年房地产行业研究报告

第一章 行业发展概况 房地产业是指以土地和建筑物为经营对象&#xff0c;从事房地产开发、建设、经营、管理以及维修、装饰和服务的集多种经济活动为一体的综合性产业&#xff0c;是具有先导性、基础性、带动性和风险性的产业。主要包括&#xff1a;土地开发&#xff0c;房屋的…

解决AAC音频编码时间戳的计算问题

1.主题音频是流式数据&#xff0c;并不像视频一样有P帧和B帧的概念。就像砌墙一样&#xff0c;咔咔往上摞就行了。一般来说&#xff0c;AAC编码中生成文件这一步&#xff0c;如果使用的是OutputStream流写入文件的话&#xff0c;就完全不需要计算时间。但在音视频同步或者使用A…

debian 部署nginx https

我是flask 处理请求单进程&#xff0c; 差点意思 &#xff0c; 考虑先flask 在往下走 一&#xff1a;安装nginx 因为我是debian 系统&#xff0c;所以我的建议是直接 sudo apt-get install nginx 你也可以选择在官网下载&#xff0c; 但是我搭建ssl 的时候安装openssl非常的麻…

【无标题】(2019)NOC编程猫创新编程复赛小学组真题含参考

&#xff08;2019&#xff09;NOC编程猫创新编程复赛小学组最后6道大题。前10道是选择填空题 略。 这道题是绘图题&#xff0c;没什么难度&#xff0c;大家绘制这2个正十边形要注意&#xff1a;一是不要超出舞台&#xff1b;二是这2个正十边形不要相交。 这里就不给出具体程序了…

数睿通2.0数据服务功能模块发布

文章目录引言API 目录API 权限API 日志结语引言 数睿通 2.0 之前基本完成了数据集成和数据开发两大模块&#xff0c;也因此得到了一些朋友的帮助和支持&#xff0c;在此由衷的表示感谢&#xff0c;你们的支持便是我们更新的最大动力&#xff01; 目前&#xff0c;数据服务模块…

色环电阻的阻值如何识别

这种是色环电阻&#xff0c;其外表有一圈圈不同颜色的色环&#xff0c;现在在一些电器和电源电路中还有使用。下面的两种色环电阻它颜色还不一样&#xff0c;一个蓝色&#xff0c;一个土黄色&#xff0c;其实这个蓝色的属于金属膜色环电阻&#xff0c;外表涂的是一层金属膜&…

狂神说:面向对象(三)——多态

多态// 对象能执行什么方法&#xff0c;主要看对象左边的类型&#xff0c;和右边的没有关系多态&#xff1a;同一方法可以根据发送对象的不同而采用不同的行为方式父类&#xff1a;public class Person {public void run(){System.out.println("Person > run");}}…

【并发编程学习篇】深入理解CountDownLatch

一、CountDownLatch介绍 CountDownLatch&#xff08;闭锁&#xff09;是一个同步协助类&#xff0c;允许一个或多个线程等待&#xff0c;直到其他线程完成操作集。CountDownLatch使用给定的计数值&#xff08;count&#xff09;初始化。await方法会阻塞直到当前的计数值被coun…