【题解 线段树】[蓝桥杯 2022 省 A] 选数异或
题目描述:
[蓝桥杯 2022 省 A] 选数异或
题目描述
给定一个长度为 n n n 的数列 A 1 , A 2 , ⋯ , A n A_{1}, A_{2}, \cdots, A_{n} A1,A2,⋯,An 和一个非负整数 x x x, 给定 m m m 次查询, 每次询问能否从某个区间 [ l , r ] [l, r] [l,r] 中选择两个数使得他们的异或等于 x x x 。
输入格式
输入的第一行包含三个整数 n , m , x n, m, x n,m,x 。
第二行包含 n n n 个整数 A 1 , A 2 , ⋯ , A n A_{1}, A_{2}, \cdots, A_{n} A1,A2,⋯,An。
接下来 m m m 行,每行包含两个整数 l i , r i l_{i}, r_{i} li,ri 表示询问区间 [ l i , r i ] \left[l_{i}, r_{i}\right] [li,ri] 。
输出格式
对于每个询问, 如果该区间内存在两个数的异或为 x x x 则输出 yes, 否则输出 no。
样例 #1
样例输入 #1
4 4 1
1 2 3 4
1 4
1 2
2 3
3 3
样例输出 #1
yes
no
yes
no
提示
【样例说明】
显然整个数列中只有 2,3 的异或为 1 。
【评测用例规模与约定】
对于 20 % 20 \% 20% 的评测用例, 1 ≤ n , m ≤ 100 1 \leq n, m \leq 100 1≤n,m≤100;
对于 40 % 40 \% 40% 的评测用例, 1 ≤ n , m ≤ 1000 1 \leq n, m \leq 1000 1≤n,m≤1000;
对于所有评测用例, 1 ≤ n , m ≤ 1 0 5 , 0 ≤ x < 2 20 , 1 ≤ l i ≤ r i ≤ n 1 \leq n, m \leq 10^5,0 \leq x<2^{20}, 1 \leq l_{i} \leq r_{i} \leq n 1≤n,m≤105,0≤x<220,1≤li≤ri≤n , 0 ≤ A i < 2 20 0 \leq A_{i}<2^{20} 0≤Ai<220 。
蓝桥杯 2022 省赛 A 组 D 题。
分析:
对于异或,我们有如下性质:
a x o r b = c − > a x o r c = b a\ xor\ b=c->a\ xor\ c=b a xor b=c−>a xor c=b
于是问题就转化成:
∃ i ∈ [ l , r ] , ∃ j ∈ [ l , r ] \exists i\in[l,r],\exists j\in[l,r] ∃i∈[l,r],∃j∈[l,r],有 a [ j ] = a [ i ] x o r x a[j]=a[i]\ xor\ x a[j]=a[i] xor x
对于每一个 i i i,我们如何寻找合法的 j j j呢?
对于一个 i i i,如果他有若干个合法的j,我们显然只要找到最近的那个j就可以了。
我们用一个数组 L a [ i ] La[i] La[i]表示数字 i i i上次出现的位置
那么对于位置 i i i,他最近的一个j的位置就是 L a [ a [ i ] x o r x ] La[a[i]\ xor\ x] La[a[i] xor x]
这样我们就找到了每个数字最近的合法数字的位置。
那么对于一个区间 [ l , r ] [l,r] [l,r],我们如何进行求解呢?
由于题目中的问题是问我们是否存在这样一对数字满足条件
也就是说这是一个存在性问题,只要存在一对合法的数字即可
就是说:
∃ i ∈ [ l , r ] , 有 L a [ i ] > = l \exists i\in[l,r],有La[i]>=l ∃i∈[l,r],有La[i]>=l
因此我们只需要对区间 [ l , r ] [l,r] [l,r]之间所有的 L a [ i ] La[i] La[i]求一个最大值即可
线段树可以维护
Code
#include<bits/stdc++.h>
using namespace std;const int N = 1e5+10;
map < int , int > Now,La;
int n,m,k;struct Tr{int tr[4*N];void Insert(int x,int l,int r,int po,int v){if (l == r){tr[x] = v; return;}int Mid = (l+r)>>1;if (po <= Mid) Insert(x<<1,l,Mid,po,v);else Insert(x<<1|1,Mid+1,r,po,v);tr[x] = max(tr[x<<1],tr[x<<1|1]);return ;}int Ask(int x,int l,int r,int L,int R){if (L <= l && r <= R) return tr[x];int Mid = l+r>>1;int Max = 0;if (L <= Mid) Max = max(Max,Ask(x<<1,l,Mid,L,R));if (R > Mid) Max = max(Max,Ask(x<<1|1,Mid+1,r,L,R));return Max;}
}tr;int a[N];int main(){scanf("%d %d %d",&n,&m,&k);for (int i = 1; i <= n; i++) scanf("%d",&a[i]);for (int i = 1; i <= n; i++){int x = 0;if (Now.count(a[i]^k)) x = Now[a[i]^k];Now[a[i]] = i;tr.Insert(1,1,n,i,x);}for (int i = 1; i <= m; i++){int l,r; scanf("%d %d",&l,&r);int Max = tr.Ask(1,1,n,l,r);if (Max >= l) printf("yes\n");else printf("no\n");}return 0;
}
相关文章:
【题解 线段树】[蓝桥杯 2022 省 A] 选数异或
题目描述: [蓝桥杯 2022 省 A] 选数异或 题目描述 给定一个长度为 n n n 的数列 A 1 , A 2 , ⋯ , A n A_{1}, A_{2}, \cdots, A_{n} A1,A2,⋯,An 和一个非负整数 x x x, 给定 m m m 次查询, 每次询问能否从某个区间 [ l , r ] [l, r] [l,r] 中选择两…...
宠物喂食器方案智能开发设计
现在年轻人特别是在一、二、三线城市的,工作节奏快、加班、出差、旅游成常态,无法经常在宠物身边照看,宠物智能自动喂食机能够解放宠主的双手和解决不能长时间在处的无奈,很好地满足了年轻宠物主照顾宠物的需求。宠物主和宠物都需…...
chatgpt综述阅读理解
Summary of ChatGPT-Related research and perspective towards the future of large language models 摘要 本文总结了语言模型在遵循指令和人类反馈方面的相关工作,包括训练语言模型来理解指令并按照指令执行任务,以及提高语言模型的性能和理解能力的…...
XCTF-RSA-2:baigeiRSA2、 cr4-poor-rsa
baigeiRSA2 题目描述 import libnum from Crypto.Util import number from functools import reduce from secret import flagn 5 size 64 while True:ps [number.getPrime(size) for _ in range(n)]if len(set(ps)) n:breake 65537 n reduce(lambda x, y: x*y, ps) m …...
js 根据word文档模板导出内容
一、创建word导出模板 1、本地创建一个test.docx 2、将最终需要的文档内容及样式编辑完成(图1) 3、将所需动态值的位置,替换为变量参数(图2) 注: 动态值书写 图1 图2 模板值的书写要求 二、项目中使用 1、安装依赖 npm install docxtemplater-image-module-free --save n…...
AIGC | 如何用“Flow”,轻松解决复杂业务问题
随着LLM(大语言模型)的爆火,不少企业都在寻找通过LLM解决企业业务问题的方法,以达到降本增效的效果。但是,当面对较为复杂的业务问题(如:背景资料多、问题分类多、条件判断复杂、涉及模块多等&a…...
多级菜单 树结构 排序 前端 后端 java
目录 省流: 正文: v1.0版 前端传的值: 后端代码: v2.0版 v3.0版 省流: 前端提交过来整个树即可。 给整个树进行sort。代码如下: public static void sort(List<Node> tree){int i 0;for…...
LAN-Free在数据备份时的应用与优势
在灾备领域中,常见的备份架构有LAN、LAN-Free和Server-Free备份,其中LAN备份架构图见图1,LAN-Free备份架构图见图2,Server-Free备份架构图见图3,途中红色箭头为备份数据流量走向: 图 1 图 2 图 3 从图1、图…...
HTML 文档声明和语言设置
HTML 文档声明 DOCTYPE 文档类型声明,用于告诉浏览器的解析器,该以那种 HTML 版本来解析这个文件。 HTML 5 版本声明 <!DOCTYPE html>XHTML 1.0 严格版声明 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http:/…...
【C++基础知识学习笔记】精华版(复习专用)
常用语法 函数重载(Overload) 规则: 函数名相同 参数个数不同、参数类型不同、参数顺序不同 注意: 返回值类型与函数重载无关 调用函数时,实参的隐式类型转换可能会产生二义性 默认参数 C++ 允许函数设置默认参数,在调用时可以根据情况省略实参。规则如下: 默认参数只能…...
探索ChatGPT在学术写作中的应用与心得
随着人工智能的迅猛发展,ChatGPT作为一种强大的自然语言处理模型,逐渐在学术界引起了广泛的关注。本文将探讨ChatGPT在学术写作中的应用,并分享使用ChatGPT进行学术写作时的一些经验和心得。 01 — ChatGPT在学术写作中的应用 1.文献综述和…...
Android:怎么学习才能更好的进大厂呢?
怎么学习才能更好的进大厂呢? 很多朋友都在问这个问题。 其实没有什么特别的技巧,就是依靠自己的毅力和决心。一天做不到,就一个月;一个月做不到,就一年。只要有决心,无论学历或资历如何,都不是…...
CSS标点符号换行问题
最近遇到一个奇怪的现象,元素中中文文本正常显示,但是加了一堆符号后中文文本居然换行了. div{width: 200px;border: 1px solid blue;word-break: break-all;} <div>文本</div>经过研究发现,因为标点符号不允许出现在行首和行尾,连带着符号…...
jdbc Preparestatement防止SQL注入的原理
2023-10-28T03:37:11.264132Z 2 Execute select * from users where username liulemon and password \ or \1\ 1\ 可以看到这一行,预编译时?变成了转义字符 useServerPrepStmtstrue加上这句才能预编译...
如何控制 LLM 的输出格式和解析其输出结果?
现在很多人对于如何使用像 ChatGPT 这样的 LLM 已经比较有经验了,可以使用各种不同的 Prompt 得到自己想要的结果。但有时候我们的使用场景不局限于手动操作,而是需要结合程序去调用 API,并且解析 API 的返回结果,从而实现一些自动…...
【Linux】 ps 命令使用
ps (英文全拼:process status)命令用于显示当前进程的状态,类似于 windows 的任务管理器。 语法 ps [选项] ps命令 -Linux手册页 著者 ps最初由布兰科兰克斯特撰写<lankestefwi.uva.nl>。迈克尔K约翰逊<johnsonmred…...
C++二分查找算法的应用:长度递增组的最大数目
本文涉及的基础知识点 二分查找 题目 给你一个下标从 0 开始、长度为 n 的数组 usageLimits 。 你的任务是使用从 0 到 n - 1 的数字创建若干组,并确保每个数字 i 在 所有组 中使用的次数总共不超过 usageLimits[i] 次。此外,还必须满足以下条件&…...
提示3D标题编辑器仍在运行怎么解决,以及3D标题编辑器怎么使用
在进行视频剪辑时,尤其是剪辑一些带有文字的开场视频,一般都会使用具有立体效果的3D标题,这样制作出来的视频效果不仅好看,还非常的炫酷,但是对于一些刚刚开始接触视频剪辑的小伙伴来说,可能对3D标题还不是…...
1. PPT高效初始化设置
1. PPT高效初始化设置 软件安装:Office 2019 主题和颜色 颜色可以在白天与黑夜切换,护眼 切换成了黑色 撤回次数 撤回次数太少,只有20次怎么办 自动保存 有时忘记保存就突然关闭,很需要一个自动保存功能 图片压缩 图…...
el-cascader级联选择器选中一个全选中问题
问题 只选中一个却把同级全选中 解决 :props中添加label、value、children属性 label、value、children属性值需要和后端返回的集合中的字段名保持一致 后端返回数据:...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...
iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...
Caliper 负载(Workload)详细解析
Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...
android13 app的触摸问题定位分析流程
一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...
从物理机到云原生:全面解析计算虚拟化技术的演进与应用
前言:我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM(Java Virtual Machine)让"一次编写,到处运行"成为可能。这个软件层面的虚拟化让我着迷,但直到后来接触VMware和Doc…...
