题解:CF1968F(Equal XOR Segments)
题解:CF1968F(Equal XOR Segments)
题目翻译:定义一个序列是好,当且仅当可以将其分成大于 1 1 1 份,使得每个部分的异或和相等。现在给定一个长度为 n n n 的序列 a a a,以及 q q q 次查询,每次查询中,询问序列 a a a 的第 l l l 到 r r r 位是不是好的。( n ≤ 2 ⋅ 1 0 5 n\leq2\cdot10^5 n≤2⋅105 并且 q ≤ 2 ⋅ 1 0 5 q\leq2\cdot10^5 q≤2⋅105)
第一步,要缩小范围。我们不难发现这个段数要么是 2 2 2,要么是 3 3 3,如果有多于 4 4 4 段,那么将其中任意三段合并,根据异或的性质可以证明对最终结果没有影响,这样一直合并,一直将段数减少 2 2 2,早晚能变成 2 2 2 或 3 3 3 段。
第二步,考虑如何求答案。如果询问道一段区间异或起来(用前缀异或和 s s s 维护)为 0 0 0,那么一定可以分成两段;否则也就是难点——分成三段的情况。那么就相当于找到两个数 x x x 和 y y y( l < x < y < r l<x<y<r l<x<y<r)使得 s x ⨁ s l − 1 = s y ⨁ s x = s r ⨁ s y s_x\bigoplus s_{l-1}=s_y\bigoplus s_x=s_r\bigoplus s_y sx⨁sl−1=sy⨁sx=sr⨁sy。这个式子就等价于找到 s y = s l − 1 s_y=s_{l-1} sy=sl−1 以及 s x = s r s_x=s_r sx=sr。那么我们用一个 map<int, vector<int>> 存储某一个数在 s s s 中出现在哪些位置,然后用 upper_bound 和 lower_bound 二分求出能否找到合理的 x x x 和 y y y 并且保证 x < y x<y x<y。比如说,我们在等于 s l − 1 s_{l-1} sl−1 的 vector 里面找到小于 r r r 最大的 y y y,在等于 s r s_r sr 的 vector 里面找到大于 l l l 里最小的 x x x,判断,如果 l < x < y < r l<x<y<r l<x<y<r 就可以,否则就不行。
具体见代码。
#include <bits/stdc++.h>
#define N 220000
using namespace std;
int t, n, q, a[N], l, r;
int s[N];
map<int, set<int>> id;
int main() {scanf("%d", &t);while (t--) {id.clear();scanf("%d%d", &n, &q);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);s[i] = s[i - 1] ^ a[i];if (id.find(s[i]) == id.end()) {id[s[i]] = {i};} else {id[s[i]].insert(i);}}for (int i = 1; i <= q; i++) {scanf("%d%d", &l, &r);if ((s[r] ^ s[l - 1]) == 0) {printf("Yes\n");} else {auto u = id[s[l - 1]].upper_bound(r - 1);if (u == id[s[l - 1]].begin()) {printf("No\n");} else {u--;auto v = id[s[r]].lower_bound(l);if (v != id[s[r]].end() && l <= *v && *v < *u && *u < r) {printf("Yes\n");} else {printf("No\n");}}}}}return 0;
}
相关文章:
题解:CF1968F(Equal XOR Segments)
题解:CF1968F(Equal XOR Segments) 题目翻译:定义一个序列是好,当且仅当可以将其分成大于 1 1 1 份,使得每个部分的异或和相等。现在给定一个长度为 n n n 的序列 a a a,以及 q q q 次查询…...
Python操作MySQL实战
文章导读 本文用于巩固Pymysql操作MySQL与MySQL操作的知识点,实现一个简易的音乐播放器,拟实现的功能包括:用户登录,窗口显示,加载本地音乐,加入和删除播放列表,播放音乐。 点击此处获取参考源…...
【Linux系统】进程间通信
本篇博客整理了进程间通信的方式管道、 system V IPC的原理,结合大量的系统调用接口,和代码示例,旨在让读者透过进程间通信去体会操作系统的设计思想和管理手段。 目录 一、进程间通信 二、管道 1.匿名管道 1.1-通信原理 1.2-系统调用 …...
北大国际医院腹膜后纤维化课题组 多学科协作开辟治疗新径
腹膜后纤维化(Retroperitoneal Fibrosis,简称RPF)是一种罕见的自身免疫性疾病,其核心特征是纤维组织的异常增生与硬化。这种疾病主要影响肾脏下方的腹主动脉和髂动脉区域,增生的纤维组织会逐渐压迫周围的输尿管和下腔静脉,从而导致一系列并发症,包括主动脉瘤、肾功能衰竭等,甚至…...
面试数据库八股文十问十答第七期
面试数据库八股文十问十答第七期 作者:程序员小白条,个人博客 相信看了本文后,对你的面试是有一定帮助的!关注专栏后就能收到持续更新! ⭐点赞⭐收藏⭐不迷路!⭐ 1)索引是越多越好吗ÿ…...
【C++题解】1133. 字符串的反码
问题:1133. 字符串的反码 类型:字符串 题目描述: 一个二进制数,将其每一位取反,称之为这个数的反码。下面我们定义一个字符的反码。 如果这是一个小写字符,则它和字符 a 的距离与它的反码和字符 z 的距离…...
【Python编程实战】基于Python语言实现学生信息管理系统
🎩 欢迎来到技术探索的奇幻世界👨💻 📜 个人主页:一伦明悦-CSDN博客 ✍🏻 作者简介: C软件开发、Python机器学习爱好者 🗣️ 互动与支持:💬评论 &…...
AI网络爬虫:批量爬取电视猫上面的《庆余年》分集剧情
电视猫上面有《庆余年》分集剧情,如何批量爬取下来呢? 先找到每集的链接地址,都在这个class"epipage clear"的div标签里面的li标签下面的a标签里面: <a href"/drama/Yy0wHDA/episode">1</a> 这个…...
md5强弱碰撞
一,类型。 1.弱比较 php中的""和""在进行比较时,数字和字符串比较或者涉及到数字内容的字符串,则字符串会被转换为数值并且比较按照数值来进行。按照此理,我们可以上传md5编码后是0e的字符串,在…...
【Docker故障处理篇】运行容器报错“docker: failed to register layer...file exists.”解决方法
【Docker故障处理篇】运行容器报错“docker: failed to register layer...file exists.” 一、Docker环境介绍2.1 本次环境介绍2.2 本次实践介绍二、故障现象2.1 运行容器消失2.2 重新运行容器报错三、故障分析四、故障处理4.1 停止 Docker 服务:4.2 备份重要数据4.3 清理冲突…...
小红书-社区搜索部 (NLP、CV算法实习生) 一面面经
😄 整个流程按如下问题展开,用时60min左右面试官人挺好,前半部分问问题,后半部分coding一道题。 各位有什么问题可以直接评论区留言,24小时内必回信息,放心~ 文章目录 1、自我介绍2、介绍下项目:微信-多模态小视频分类2.1、看你用了cross-att来融合多模态信息,cross…...
解读makefile中的.PHONY
在 Makefile 中,.PHONY 是一个特殊的目标,用于声明伪目标(phony target)。伪目标是指并不代表实际构建结果的目标,而是用来触发特定动作或命令的标识。通常情况下,.PHONY 会被用来声明一组需要执行的动作&a…...
linux配置防火墙端口
配置防火墙,添加或删除端口,需要有root权限。 防火墙常用命令如下: 1.查看防火墙状态: systemctl status firewalld active(running):开启状态,正在运行中 inactive(dead):关闭状态ÿ…...
sklearn线性回归--岭回归
sklearn线性回归--岭回归 岭回归也是一种用于回归的线性模型,因此它的预测公式与普通最小二乘法相同。但在岭回归中,对系数(w)的选择不仅要在训练数据上得到好的预测结果,而且还要拟合附加约束,使系数尽量小…...
三十一、openlayers官网示例Draw Features解析——在地图上自定义绘制点、线、多边形、圆形并获取图形数据
官网demo地址: Draw Features 先初始化地图,准备一个空的矢量图层,用于显示绘制的图形。 initLayers() {const raster new TileLayer({source: new XYZ({url: "https://server.arcgisonline.com/ArcGIS/rest/services/World_Imagery/…...
医疗科技:UWB模块为智能医疗设备带来的变革
随着医疗科技的不断发展和人们健康意识的提高,智能医疗设备的应用越来越广泛。超宽带(UWB)技术作为一种新兴的定位技术,正在引领着智能医疗设备的变革。UWB模块作为UWB技术的核心组成部分,在智能医疗设备中发挥着越来越…...
Java面试题大全(从基础到框架,中间件,持续更新~~~)
从Java基础到数据库,Spring,MyBatis,消息中间件,微服务解决全部Java面试过程中的问题。(持续更新~~) Java基础 2024最新Java面试题——java基础 MySQL基础 mysql基础知识——适合不太熟悉数据库知识的小…...
零知识证明在隐私保护和身份验证中的应用
PrimiHub一款由密码学专家团队打造的开源隐私计算平台,专注于分享数据安全、密码学、联邦学习、同态加密等隐私计算领域的技术和内容。 隐私保护和身份验证是现代社会中的关键问题,尤其是在数字化时代。零知识证明(Zero-Knowledge Proofs&…...
15.微信小程序之async-validator 基本使用
async-validator是一个基于 JavaScript 的表单验证库,支持异步验证规则和自定义验证规则 主流的 UI 组件库 Ant-design 和 Element中的表单验证都是基于 async-validator 使用 async-validator 可以方便地构建表单验证逻辑,使得错误提示信息更加友好和…...
元宇宙vr科普馆场景制作引领行业潮流
在这个数字化高速发展的时代,北京3D元宇宙场景在线制作以其独特的优势,成为了行业内的创新引领者。它能够快速完成空间设计,根据您的个性化需求,轻松设置布局、灯光、音效以及互动元素等,为您打造出一个更加真实、丰富…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...
处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...
MySQL 知识小结(一)
一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库,分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷,但是文件存放起来数据比较冗余,用二进制能够更好管理咱们M…...
