选数异或第十三届蓝桥杯大赛软件赛省赛C/C++ 大学 A 组

选数异或

题目来源

第十三届蓝桥杯大赛软件赛省赛C/C++ 大学 A 组

原题链接

第十三届蓝桥杯大赛软件赛省赛C/C++ 大学 A 组选数异或 https://www.lanqiao.cn/problems/2081/learning/

题目描述

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

输入格式

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

第二行包含 $n$ 个整数 $A_{1}, A_{2}, \cdots, A_{n}$ 。

接下来 $m$ 行，每行包含两个整数 $l_{i}, r_{i}$ 表示询问区间 $\left[l_{i}, r_{i}\right]$ 。

输出格式

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

输入输出样例 #1

输入 #1

输出 #1

yes
no
yes
no

说明/提示

【样例说明】

显然整个数列中只有 2,3 的异或为 1 。

【评测用例规模与约定】

对于 $\%$ 的评测用例, $\leq n, m \leq 100$ ;

对于 $\%$ 的评测用例, $\leq n, m \leq 1000$ ;

对于所有评测用例, $\leq n, m \leq 10^5,0 \leq x<2^{20}, 1 \leq l_{i} \leq r_{i} \leq n$ ， $\leq A_{i}<2^{20}$ 。

蓝桥杯 2022 省赛 A 组 D 题。

算法思路

该问题要求我们多次查询一个区间 [l, r]，判断是否存在两个不同的数 A[i] 和 A[j]，使得它们的异或等于给定的非负整数 x。为了高效处理多个查询，我们需要预处理一些信息，使得每次查询可以在常数时间内得到结果。

关键观察

异或的性质：如果 A[i] ^ A[j] = x，那么 A[j] = A[i] ^ x。因此，对于每个元素 A[i]，我们只需要检查在它之前是否存在 A[i] ^ x。
预处理：我们可以维护一个数组 f，其中 f[i] 表示在位置 i 之前（包括 i）满足 A[j] ^ A[k] = x 的最大 k（即最近的位置）。这样，对于查询 [l, r]，只需要检查 f[r] 是否大于等于 l。如果是，则存在这样的两个数；否则不存在。

具体步骤

初始化：使用一个哈希表 h 来记录每个数值最后一次出现的位置。
预处理数组 f：
- 遍历数组 A，对于每个元素 A[i]，计算 A[i] ^ x，并检查哈希表 h 中是否存在该值。
- 如果存在，则 f[i] 取 max(f[i-1], h[A[i] ^ x])，即当前位置 i 之前满足条件的最大位置。
- 如果不存在，则 f[i] = f[i-1]。
- 更新哈希表 h，将 A[i] 的最新位置记录为 i。
处理查询：对于每个查询 [l, r]，检查 f[r] 是否大于等于 l。如果是，则输出 “yes”；否则输出 “no”。

代码

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;const int N = 100010; // 定义最大数组长度
int n, m, x;         // n: 数组长度, m: 查询次数, x: 目标异或值
int f[N], e[N];      // f[i]: 预处理数组，e: 存储输入的数组
unordered_map<int, int> h; // 哈希表，记录数值最后一次出现的位置int main() {scanf("%d%d%d", &n, &m, &x); // 输入 n, m, xfor (int i = 1; i <= n; i++) {scanf("%d", &e[i]); // 输入数组元素// f[i] 表示在位置 i 之前（包括 i）满足 A[j] ^ A[k] = x 的最大 k// 即 f[i] = max(f[i-1], h[A[i] ^ x])f[i] = max(f[i - 1], h[e[i] ^ x]);// 更新哈希表，记录当前数值 e[i] 的最新位置为 ih[e[i]] = i;}for (int i = 0; i < m; i++) {int l, r;scanf("%d%d", &l, &r); // 输入查询区间 [l, r]// 如果 f[r] >= l，说明在 [1, r] 中存在一个位置 k >= l 满足 A[k] ^ A[j] = xif (f[r] >= l) puts("yes");else puts("no");}return 0;
}

代码解释

输入处理：读取数组长度 n、查询次数 m 和目标异或值 x，然后读取数组 e。
预处理数组 f：
- f[i] 表示在位置 i 之前（包括 i）满足 A[j] ^ A[k] = x 的最大 k。
- 通过哈希表 h 快速查找 A[i] ^ x 是否出现过，并记录其最新位置。
查询处理：对于每个查询 [l, r]，检查 f[r] 是否大于等于 l。如果是，则说明在区间 [l, r] 中存在两个数的异或等于 x。

这种方法通过预处理将每次查询的时间复杂度降为 O(1)，整体时间复杂度为 O(n + m)，非常高效。