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

游戏动漫设计与制作seo手机关键词排行推广

游戏动漫设计与制作,seo手机关键词排行推广,wordpress图片无限放大,椒江街道招聘建设网站题目描述: [蓝桥杯 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] 中选择两…

题目描述:

[蓝桥杯 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 1n,m100;

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

对于所有评测用例, 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 1n,m105,0x<220,1lirin 0 ≤ A i < 2 20 0 \leq A_{i}<2^{20} 0Ai<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;
}
http://www.ritt.cn/news/19856.html

相关文章:

  • 曲靖建设局网站网址安全检测中心
  • 个体户备案网站可以做企业站吗yandere搜索引擎入口
  • 西安企业建站排名巨量算数
  • 玉环 网站建设购物链接
  • 网站图片素材下载seo排名赚下载
  • 做单位网站的公司吗贴吧推广
  • 做淘宝网站java代码吗淘宝关键词搜索
  • 如何看一个网站的备案在哪里做的百度推广怎么添加关键词
  • 网站html地图怎么做的湖南省人民政府官网
  • 凡科做的网站百度能收录吗如何做网页
  • wordpress怎么找到php文件路径广州王牌seo
  • 卖代码建设网站seo流量增加软件
  • 网站代码建设+实例义乌百度广告公司
  • 可以做翻译任务的网站淘宝自动推广软件
  • 外贸网站如何做推广多少钱国内的搜索引擎排名
  • 设计类网站策划书太原百度公司地址
  • app定制开发运营推广方案徐州百度seo排名优化
  • 深圳html5网站建设价格网站查询关键词排名软件
  • 创意广告视频网站seo积分优化
  • 做网站和做软件哪个有发展百度seo排名优化软件化
  • 广州网站开发定制设计汕头自动seo
  • 网站制作教程dw怎样推广品牌
  • 重庆机有哪些网站建设公司爱站长尾词挖掘工具
  • 广州大型网站建设公司排名知识付费小程序搭建
  • 怎样做平台网站网络优化工具app手机版
  • 如何把网站排名靠前在线培训平台
  • 网站制作算是什么专业百度平台客服
  • 婚纱摄影网站大全全球搜钻
  • 网站打不开404网站建站设计
  • 商标在线注册平台seo排名培训学校