青岛建站公司推荐,怎么创建公众号赚钱,旺店通erp系统,centos7.2做网站题目描述#xff1a;
[蓝桥杯 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 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 x2^{20}, 1 \leq l_{i} \leq r_{i} \leq n 1≤n,m≤105,0≤x220,1≤li≤ri≤n 0 ≤ A i 2 20 0 \leq A_{i}2^{20} 0≤Ai220 。
蓝桥杯 2022 省赛 A 组 D 题。 分析
对于异或我们有如下性质 a x o r b c − a x o r c b a\ xor\ bc-a\ xor\ cb a xor bc−a xor cb
于是问题就转化成 ∃ 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
#includebits/stdc.h
using namespace std;const int N 1e510;
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 (lr)1;if (po Mid) Insert(x1,l,Mid,po,v);else Insert(x1|1,Mid1,r,po,v);tr[x] max(tr[x1],tr[x1|1]);return ;}int Ask(int x,int l,int r,int L,int R){if (L l r R) return tr[x];int Mid lr1;int Max 0;if (L Mid) Max max(Max,Ask(x1,l,Mid,L,R));if (R Mid) Max max(Max,Ask(x1|1,Mid1,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;
}
