第十三届蓝桥杯省赛C++A组 D 题、C++C组 F 题、Java C 组 F 题——选数异或 （AC）

1.选数异或

1.题目描述

给定一个长度为 $n$ 的数列 $A_1,A_2,\cdots ,A_n$​和一个非负整数 $x$, 给定 $m$ 次查 询, 每次询问能否从某个区间 $[l,r]$ 中选择两个数使得他们的异或等于 $x$ 。

2.输入格式

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

第二行包含 $n$ 个整数 $A_1,A_2,\cdots ,A_n$ 。接下来 $m$ 行，每行包含两个整数 $l_i,r_i$表示询问区间 $\left[l_i,r_i\right]$。

3.输出格式

对于每个询问, 如果该区间内存在两个数的异或为 $x$ 则输出 yes, 否则输出 no。

4.样例输入

4 4 1
1 2 3 4
1 4
1 2
2 3
3 3

5.样例输出

yes
no
yes
no

6.数据范围

$1\le n,m\le 100000,0\le x<2^{20},1\le li\le ri\le n,0\le A_i<2^{20}$。

7.原题链接

选数异或

2.解题思路

对于异或的性质不过多在这讲解，利用的也是非常简单的公式：如果存在a^b=x，那么一定满足a^x=b，b^x=a。也就是说，对于一个整数 a ,有且只存在一个数b使得其和a异或得到x，我们可以通过a^x来得到这个数的值。

对此，我们可以处理得到数组中所有符合的数对 $(a,b)$，其中 $a$ 是数组中靠左的数，$b$是靠右边的。我们可以枚举 $b$ , 然后判断在数组前面是否出现过数 $a$ ，这一步我们可以使用哈希表记录维护每个数最后出现的位置，如果存在则说明找到一对符合的数对。那我们该如何记录答案呢？

我们定义$f[i]$为前 $i$ 个数出现数对中 $a$ 的最大下标。为什么要这么设计呢？
考虑查询时需要确保$(a,b)$都在查询区间$[l,r]$中，由于只需要考虑是否存在任意一对，那我们只需要维护最有可能的一对。当我们查询$f[r]$ 时，可以保证查询到的所有 $b$ 下标 一定不超过 $r$。那么此时就只需要保证是否存在一个 $a$ 满足它的下标大于 $l$ 即可。那么这样我们对于每个查询$[l,r]$，只需要去判断$f[r]>=l$ 即可，符合则输出yes，否则输出no。

当然我们需要考虑如何转移，对于当前的值 $v$ ,下标为 $i$。如果哈希表中不存在数 x^v，则$f[i]=f[i-1]$，如果存在则为$f[i]=max(f[i-1],m[vˆx])$。因为 C++ 的map对不存在的数默认输出0，所以不影响我们的答案，即转移方程为：
$$f[i]=max(f[i-1],m[vˆx])$$

3.Ac_code

#include
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200010;

int n, q, x;
map<int, int> m;
int f[N];
void solve()
{
	cin >> n >> q >> x;
	for (int i = 1; i <= n; ++i) {
		int v;
		cin >> v;
		f[i] = max(f[i - 1], m[x ^ v]);
		m[v] = i;
	}
	while (q--) {
		int l, r;
		cin >> l >> r;
		if (f[r] >= l) cout << "yes" << '\n';
		else cout << "no" << '\n';
	}
}
int main()
{
	ios_base :: sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1;
	while (t--)
	{
		solve();
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43