【AcWing】动态规划-线性DP -选数异或
目录
题目描述
解题思路
完整代码
举例
题目描述
4645. 选数异或 - AcWing题库
解题思路
本质问题：在
[l, r]区间是否能找到a[i] ^ a[j] = x的数对。核心思路：
- 通过异或性质快速定位潜在的匹配数。
- 使用
dp数组记录匹配状态。
3. 查询时只需判断
dp[r]是否大于等于l。
其实这个转移方程的逻辑就像在“找搭子”——
- 你在遍历数组，每遇到一个数
a，就会去问：“之前有没有一个数和我异或能等于x啊？” - 如果有（
last[x ^ a]找到了，每次遇到新元素a，只需要在last中用last[x ^ a]查找与之匹配的b是否出现过），就用它的位置来更新当前的“最远有效位置”； - 如果没有，那就接着用之前的最优答案（
dp[i-1]）呗。
完整代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010; // 定义数组的最大长度
int dp[N]; // dp[i] 表示在前 i 个元素中，能够与第 i 个元素构成异或为 x 的元素的最左位置
int n, m, x; // n：数组长度，m：查询次数，x：目标异或值
int main() {
cin >> n >> m >> x;
unordered_map<int, int> last; // 用于存储每个元素最后一次出现的位置，键为元素，值为位置索引
// 遍历输入数组
for (int i = 1; i <= n; i++) {
int a;
cin >> a; // 读取当前元素
/**
* 逻辑说明：
* - x ^ a：表示与当前元素 a 异或后等于 x 的目标元素。
* - last[x ^ a]：如果该目标元素之前出现过，返回它的索引，否则返回 0。
* - dp[i]：表示在前 i 个元素中，能找到与第 i 个元素异或为 x 的最近索引。
* - max(dp[i-1], last[x ^ a]) 确保 dp[i] 始终存储到当前位置为止的最优解。
*/
dp[i] = max(dp[i - 1], last[x ^ a]);
// 更新当前元素 a 最后一次出现的位置为 i
last[a] = i;
}
// 处理查询
while (m--) {
int l, r;
cin >> l >> r; // 读取查询区间 [l, r]
/**
* 判断区间内是否存在一对异或结果为 x 的元素：
* - dp[r] >= l：表示在 [l, r] 区间内，存在一对异或为 x 的元素对。
* 因为 dp[r] 表示能与位置 r 之前某元素组成异或为 x 的最远有效位置，
* 如果这个位置大于等于查询区间的左边界 l，则表示区间内有解。
*/
if (l <= dp[r])
cout << "yes" << endl; // 存在符合条件的元素对
else
cout << "no" << endl; // 不存在
}
return 0;
}
举例
数组： [1, 3, 1, 2, 3]
x = 2
查询：
1) [1, 3]
2) [2, 5]
3) [3, 4]
🔄 逐步分析数组
📌 第 1 步： i=1 (a=1)
- 想找
1 ^ ? = 2，所以? = 1 ^ 2 = 3。3还没出现过。dp[1] = max(dp[0], last[3]) = 0。last[1] = 1。📌 第 2 步： i=2 (a=3)
- 想找
3 ^ ? = 2，? = 3 ^ 2 = 1。1在位置 1 出现过。dp[2] = max(dp[1], 1) = 1，表示在第2个位置前找到了匹配。last[3] = 2。📌 第 3 步： i=3 (a=1)
- 想找
1 ^ ? = 2，? = 3。3最后出现在位置2。dp[3] = max(dp[2], 2) = 2，匹配成功。last[1] = 3。📌 第 4 步： i=4 (a=2)
- 想找
2 ^ ? = 2，? = 0，还没出现过。dp[4] = max(dp[3], 0) = 2。last[2] = 4。📌 第 5 步： i=5 (a=3)
- 想找
3 ^ ? = 2，? = 1。1最后在位置3。dp[5] = max(dp[4], 3) = 3。last[3] = 5。
📊 最终 dp 数组状态：
下标 (i)：1 2 3 4 5
数组 (a)：1 3 1 2 3
dp[i] ：0 1 2 2 3
🏹 查询解答
🟢 查询1： [1, 3]
dp[3] = 2 >= 1→ 存在匹配。- ✅ 输出：
yes🟡 查询2： [2, 5]
dp[5] = 3 >= 2→[2, 5]区间内存在匹配。- ✅ 输出：
yes🔴 查询3： [3, 4]
dp[4] = 2 >= 3？ ✖ 不成立（2 < 3）- ❌ 输出：
no