【脑筋急转弯, 动态规划】选数异或

题目

4645. 选数异或 - AcWing题库

---

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

输入格式

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

第二行包含 $n$ 个整数 $A_1, A_2, · · · , A_n$ 。

接下来 $m$ 行，每行包含两个整数 $l_i,r_i$ 表示询问区间 $[l_i,r_i]$ 。

输出格式

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

数据范围

对于 $20\%$ 的评测用例， $1 ≤ n, m ≤ 100$ ；
对于 $40\%$ 的评测用例， $1 ≤ n, m ≤ 1000$ ；
对于所有评测用例， $1 ≤ n, m ≤ 100000$ ， $0 ≤ x < 2^{20}$ ， $1 ≤ l_i ≤ r_i ≤ n$ ， $0 ≤ A_i < 2^{20}$ 。

输入样例：

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

输出样例：

yes
no
yes
no

样例解释

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

解题

方法一：脑筋急转弯 动态规划

思路

首先，由异或运算的自反性我们可以得到 $a \oplus b = c \Rightarrow a \oplus c = b$。

那么对于每个 $i \in [l, r]$ ，如果存在 $A_j = A_i \oplus x$ 且 $j \in [l, r]$ 就说明在区间 $[l, r]$ 内存在一对异或为 $x$ 的数，我们自然可以在读入数组的同时预处理每个 $i$ 找到离它最近且小于它且满足以上条件的 $j$ 存入哈希表，然后对于每个查询枚举区间 $l \dots r$ 在哈希表中查询是否有满足条件的一对。但是这样的话每次查询的时间复杂度是 $O(r - l + 1)$ ，总时间复杂度是 $O(mn)$，会超时。

定义 $f(i)$：$f(i) < i$ 且 $A_{f(i)} \oplus a_i = x$ 且 $f(i)$ 为满足以上两个条件时离 $i$ 最近的下标（不存在则为 $0$），因为 $f(i) < i$ 所以 $f(i)$ 必定小于 $r$ 且如果 $i < l$ 那么 $f(i)$ 也一定小于 $l$，所以 $i$ 可以扩大范围从 $1 \dots r$ 中找（因为如果 $i$ 小于 $l$ 非法，那么找出的 $f(i)$ 一定也因为小于 $l$ 而非法，不会出现非法 $i$ 找出合法 $f(i)$ 的情况），维护 $g(i) = max(f(1) \dots f(i))$，如果 $g(r) \ge l$ 就说明区间 $l \dots r$ 有满足条件的一对。这样以来就把查询的时间复杂度降到了 $O(1)$，总时间复杂度为 $O(m)$ 。

以动态规划的角度理解：

• 状态定义：$dp[i]$ 表示 $1 \dots i$ 中一对异或为 $x$ 的数中较小的数的最大值。
• 状态转移方程：$dp[i] = \max(dp[i - 1], f(i))$ （$f(i)$ 定义如上）。
• 初始状态：$dp[1] = 0$。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        in.nextToken();
        int x = (int) in.nval;
        int[] dp = new int[n + 1];
        Map<Integer, Integer> latest = new HashMap<>();
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            int a = (int) in.nval;
            dp[i] = Math.max(dp[i - 1], latest.getOrDefault(a ^ x, 0));
            latest.put(a, i);
        }
        while (m-- > 0) {
            in.nextToken();
            int l = (int) in.nval;
            in.nextToken();
            int r = (int) in.nval;
            System.out.println(dp[r] >= l ? "yes" : "no");
        }
    }
}