AcWing 4645. 选数异或
原题链接
中等
作者:
陈驰水
,
2024-03-29 14:10:20
,
所有人可见
,
阅读 4
蓝桥杯 不太好想的DP
// 此题如果模拟是 On2 会超时
// 用 dp 进行转化,同时辅助用哈希表找当前下标之前的最后出现 x 对应下标
// 这道 dp 其实很难想,要都找题目规律
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m ,x;
cin >> n >> m >> x;
vector<long long>array(n + 1);
for (int i = 1; i <= n; i++) {
cin >> array[i];
}
// 用哈希表记录当前 x 在当前数组中最后出现的位置
unordered_map<long long, int>hash;
// 用 dp 数组表示当前位置前最短能匹配上的下标
vector<int>dp(n + 1);
dp[0] = 0;
for (int i = 1; i < n + 1; i++) {
int target = (x ^ array[i]);
// 当前目标最后出现的位置和前一个下标的 dp 值
dp[i] = max(hash[target], dp[i - 1]);
hash[array[i]] = i;
}
while (m--) {
int l, r;
cin >> l >> r;
cout << ((dp[r] >= l) ? "yes" : "no") << endl;
}
return 0;
}