当前位置: 首页 > news >正文

第十三届蓝桥杯A组:选数异或——三种解法(线段树、DP、ST表)

[蓝桥杯 2022 省 A] 选数异或

题目描述

给定一个长度为 nnn 的数列 A1,A2,⋯,AnA_{1}, A_{2}, \cdots, A_{n}A1,A2,,An 和一个非负整数 xxx, 给定 mmm 次查询, 每次询问能否从某个区间 [l,r][l, r][l,r] 中选择两个数使得他们的异或等于 xxx

输入格式

输入的第一行包含三个整数 n,m,xn, m, xn,m,x

第二行包含 nnn 个整数 A1,A2,⋯,AnA_{1}, A_{2}, \cdots, A_{n}A1,A2,,An

接下来 mmm 行,每行包含两个整数 li,ril_{i}, r_{i}li,ri 表示询问区间 [li,ri]\left[l_{i}, r_{i}\right][li,ri]

输出格式

对于每个询问, 如果该区间内存在两个数的异或为 xxx 则输出 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≤1001 \leq n, m \leq 1001n,m100;

对于 40%40 \%40% 的评测用例, 1≤n,m≤10001 \leq n, m \leq 10001n,m1000;

对于所有评测用例, 1≤n,m≤105,0≤x<220,1≤li≤ri≤n1 \leq n, m \leq 10^5,0 \leq x<2^{20}, 1 \leq l_{i} \leq r_{i} \leq n1n,m105,0x<220,1lirin0≤Ai<2200 \leq A_{i}<2^{20}0Ai<220

蓝桥杯 2022 省赛 A 组 D 题。

分析

A组的题,题目有三种解法,但是这道题无论啥解法,实际上是万变不离其宗的,就是他的关键的对于某个点的预处理。想要解这题主要还是要想出这个处理。之所以写不同的这三种解法,主要是复习一下模板吧
首先,我们容易知道:若a^b=x,那么a^x=b,对于数组a[i],我们可以通过关系式,找到a[i]^x的左边的最靠近下标,明显我们需要找到最靠近的下标,而当这个下标是大于等于所需要找的区间的左端点,即可满足这个区间内可以找到两个数的异或为x。
当对于一个数,其左边没有数与其异或等于x时,那么就将其置为0,而当我们不断输入数字的时候,我们需要同时存储这个数的下标,方便循环到下一个下标的时候找到这个数字(通过a^x=b这样的关系),具体看代码

解法一:线段树

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t[400005],a[100005],Left[100005],pos[2000005];
inline void buildtree(int k,int l,int r){if(l==r){t[k]=Left[r];return;}int mid=(l+r)>>1;buildtree(k<<1,l,mid),buildtree(k<<1|1,mid+1,r);t[k]=max(t[k<<1],t[k<<1|1]);
}
inline int query(int k,int l,int r,int x,int y){if(l==x&&r==y)return t[k];int mid=(l+r)>>1;if(y<=mid)return query(k<<1,l,mid,x,y);elseif(x>mid)return query(k<<1|1,mid+1,r,x,y);else return max(query(k<<1,l,mid,x,mid),query(k<<1|1,mid+1,r,mid+1,y));
}
int main(){int n,m,x;cin>>n>>m>>x;for(int i=1;i<=n;++i){scanf("%d",&a[i]);Left[i]=pos[a[i]^x];pos[a[i]]=i;}buildtree(1,1,n);while(m--){int x,y;scanf("%d%d",&x,&y);int k=query(1,1,n,x,y);if(k>=x)printf("yes\n");else printf("no\n");}
}

解法二:DP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int f[100005],pos[5000005];
int main(){int n,m,x;cin>>n>>m>>x;for(int i=1;i<=n;++i){int a;scanf("%d",&a);f[i]=max(f[i-1],pos[a^x]);pos[a]=i;}while(m--){int l,r;scanf("%d%d",&l,&r);if(f[r]>=l)printf("yes\n");else printf("no\n");}
}

解法三:ST表

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int st[100005][20],pos[5000005];
int main(){int n,m,x;cin>>n>>m>>x;for(int i=1;i<=n;++i){int a;scanf("%d",&a);st[i][0]=pos[a^x];pos[a]=i;}int k=log2(n);for(int i=1;i<=k;++i)for(int j=1;j+(1<<i)-1<=n;++j)st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);while(m--){int l,r;scanf("%d%d",&l,&r);int len=log2(r-l+1);int p=max(st[l][len],st[r-(1<<len)+1][len]);if(p>=l)printf("yes\n");else printf("no\n");}
}

相关文章:

第十三届蓝桥杯A组:选数异或——三种解法(线段树、DP、ST表)

[蓝桥杯 2022 省 A] 选数异或 题目描述 给定一个长度为 nnn 的数列 A1,A2,⋯,AnA_{1}, A_{2}, \cdots, A_{n}A1​,A2​,⋯,An​ 和一个非负整数 xxx, 给定 mmm 次查询, 每次询问能否从某个区间 [l,r][l, r][l,r] 中选择两个数使得他们的异或等于 xxx 。 输入格式 输入的第一…...

【CTF】CTF竞赛介绍以及刷题网址

CTF&#xff08;Capture The Flag&#xff09;中文一般译作夺旗赛&#xff0c;在网络安全领域中指的是网络安全技术人员之间进行技术竞技的一种比赛形式。CTF起源于1996年DEFCON全球黑客大会&#xff0c;以代替之前黑客们通过互相发起真实攻击进行技术比拼的方式。发展至今&…...

Springboot怎么优雅实现大文件的上传

前言在软件工程里&#xff0c;在处理“大”的时候一直是一个难点和难点&#xff0c;如并发大、数据量大、文件大&#xff0c;对硬件进行升级可以解决一些问题&#xff0c;但这并不最聪明的办法&#xff0c;而对于老板来说&#xff0c;这也不是成本最小的办法。作为开发人员来说…...

2月编程语言排行榜新鲜出炉,谁又摘得桂冠?

近日&#xff0c;TIOBE公布了2023年2月编程语言排行榜&#xff0c;本月各个语言表现如何&#xff1f;谁又摘得桂冠&#xff1f;一起来看看吧&#xff01; TIOBE 2月Top15编程语言&#xff1a; 详细榜单查看TIOBE官网 https://www.tiobe.com/tiobe-index/ 关注IT行业的小伙伴…...

机器学习中的数学原理——模型评估与交叉验证

惭愧惭愧&#xff01;机器学习中的数学原理这个专栏已经很久没有更新了&#xff01;前段时间一直在学习深度学习&#xff0c;paddlepaddle&#xff0c;刷题专栏跟新了&#xff0c;这个专栏就被打入冷宫了。这个专栏名为白话机器学习中数学学习笔记&#xff0c;主要是用来分享一…...

JAVA开发(JSP的9大内置对象和4大作用域)

背景&#xff1a; 在springboot横行的javaweb开发中&#xff0c;现在的后端开发工程师基本不需要写前端JSP页面。但是作为web开发工程师&#xff0c;不懂JSP的原理和作用&#xff0c;几乎是不行的。 JSP技术介绍&#xff1a; JSP&#xff08;全称Java Server Pages&#xff…...

(4)EKF失控保护

文章目录 前言 4.1 什么时候会触发? 4.2 当失控保护触发时,会发生什么?...

数论----质数的求解(C/C++)

CSDN的uu&#xff0c;你们好呀&#xff0c;今天我们要学习的内容是数论哦&#xff01;这也是算法题中的一类题目吧。记好安全带&#xff0c;准备发车咯&#xff01;&#x1f680;学习数论的意义&#x1f4e2;算法导论说&#xff1a;“数论曾经被视为一种虽然优美但却没什么用处…...

【电赛MSP430系列】GPIO、LED、按键、时钟、中断、串口、定时器、PWM、ADC

文章目录MSP430一、GPIO二、点亮LED三、按键控制LED四、更改主时钟五、串口通信六、串口中断七、外部中断八、定时器九、定时器中断十、PWM十一、ADCMSP430 MSP430 是德州仪器&#xff08;TI&#xff09;一款性能卓越的超低功耗 16 位单片机&#xff0c;自问世以来&#xff0c…...

【Linux】进程理解与学习(Ⅱ)

环境&#xff1a;centos7.6&#xff0c;腾讯云服务器Linux文章都放在了专栏&#xff1a;【Linux】欢迎支持订阅&#x1f339;相关文章推荐&#xff1a;【Linux】冯.诺依曼体系结构与操作系统【Linux】进程理解与学习&#xff08;Ⅰ&#xff09;浅谈Linux下的shell--BASH前言章节…...

vscode 爽到起飞的快捷键

这里写目录标题1. 窗口操作2. 代码编辑3. 批量操作4. 错误处理1. 窗口操作 文件之间切换: CtrlTab 切出一个新的编辑器窗口&#xff08;最多3个): Ctrl\ 切换左中右3个编辑器窗口的快捷键: Ctrl1 Ctrl2 Ctrl3 2. 代码编辑 代码格式化: ShiftAltF 向上或向下移动一行: Alt…...

vs +qt 打包.cpp和.h为DLL文件

文章目录一 编译成库1 创建一个Qt library 项目2&#xff0c;将已有的文件拷贝到项目目录下3 在项目中添加现有项4&#xff0c;拷贝头文件到需要暴露给外面使用的类的头文件中5 拷贝xxx_EXPORT的宏到需要被暴露的类的名前面6 然后点击编译 就完成了。得到的dll文件在debug里面二…...

echarts有滑块

vue下使用echarts折线图及其横坐标拖拽功能 drawLine() {let that this,lineDate [],dispatchCount [],finishCount [],newCount [];let param {// 参数};axios.post(url, param).then(function(response) {let rs response.data.data;if (rs ! undefined && rs…...

MATLAB绘制ROC曲线

ROC曲线(Receiver Operating Characteristic Curve) 1 简介 ROC曲线是用于评估二元分类模型&#xff08;如Logistic回归&#xff09;表现优劣的一种工具&#xff0c;其横轴表示假阳性率&#xff08;false positive rate&#xff0c;FPR&#xff09;&#xff0c;即实际为负例但…...

ChatGPT前传

文章目录前言GPT概述GPT-1代GPT-1 学习目标和概念介绍GPT-1 训练数据集GPT-1 模型结构和应用细节GPT-1 效果性能和总结GPT-2代GPT-2 学习目标和概念介绍GPT-2 训练数据集GPT-2 模型结构和应用细节GPT-2 性能效果和总结GPT-3代GPT-3 学习目标和概念介绍GPT-3 训练数据集GPT-3 模…...

我的十年编程路 2020年篇

我出生在1990年&#xff0c;2020年到来的时候&#xff0c;我完成了一项成就&#xff1a;奔三。同时&#xff0c;也开启了新的征程&#xff1a;奔四。 2020年的春节是在广州的丈母娘家度过的&#xff0c;春节后大概是初五&#xff0c;或者是初六&#xff0c;我和媳妇就返回天津…...

力扣-SQL【入门】

https://leetcode.cn/study-plan/sql/?progressxhqm4sjh 目录选择595. 大的国家1757. 可回收且低脂的产品584. 寻找用户推荐人183. 从不订购的客户排序 & 修改1873. 计算特殊奖金627. 变更性别196. 删除重复的电子邮箱选择 595. 大的国家 # Write your MySQL query state…...

Vue中组件到底是什么

1.先说结论&#xff1a; Vue中组件本质是一个名为VueComponent的构造函数&#xff0c;且不是程序员定义的&#xff0c;是Vue.extend生成的。 2.我们使用组件时发生了什么&#xff1f; 比如定义了一个school,然后在页面上使用它 我们只需要写 < school/ > 或< school &…...

不同时间间隔数据对统计结果的影响

目录摘要1. 实测数据来源2. 数据分析方法3 结果分析3.1 波况分析摘要 采用不同的波浪观测方法所获得的波浪数据的时间间隔不一致&#xff0c;其数据的准确性须进行分析。基于大埕湾逐时周年波浪观测数据&#xff0c;截取不同时间间隔的波浪数据&#xff0c;采用统计和相关分析…...

hudi系列-数据写入方式及使用场景

hudi支持多种数据写入方式:insert、bulk_insert、upsert、boostrap,我们可以根据数据本身属性(append-only或upsert)来选择insert和upsert方式,同时也支持对历史数据的高效同步并嫁接到实时流程。 这里的使用技术组合为flink + hudi-0.11 upsert 这是hudi默认的写入方式,…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...