Acwing 4645. 选数异或

一道有点难的DP

分析题意设计dp思路：

根据异或运算的性质，移项得a[j] = a[i] ^ x，不妨设j < i

我们希望枚举每一个a[i]，并找到其左边最近的a[j]令 a[j] = a[i] ^ x，此时我们称a[i], a[j]为一个合法数对，j为该数对的下界

用dp[i]表示区间1~i内的合法数对的最大下界，则对于一次询问L，R可以判定如果dp[R] >= L则说明在该区间中存在合法数对

dp转移公式

dp[i] = max(dp[i - 1], last[a[i] ^ x])

其中last是哈希表，last[i]代表i出现的最后位置，没有出现过则为0

上述公式的含义是，dp[i]的贡献来源有两个，一个是区间1~i – 1，一个是a[i] ^ x，也就是说，取他前一个状态的值与a[i] ^ x，即上面的a[j]最后出现的位置的最大值

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int a[N], dp[N];

// dp[i] 表示 1~i 中合法数对的最大下界

int main()
{
    int n, m, x;
    cin >> n >> m >> x;

    unordered_map<int, int> last;   // last[i] 表示i出现的最后位置
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        dp[i] = max(dp[i - 1], last[a[i] ^ x]);
        last[a[i]] = i;
    }

    while (m--)
    {
        int l, r;
        cin >> l >> r;
        cout << (dp[r] >= l ? "yes" : "no")<< endl;
    }
    return 0;
}

算法复杂度O(m + n)