侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2023-01-13 / 0 评论 / 0 点赞 / 21 阅读 / 1,220 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2023-01-13,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

4645. 选数异或 - AcWing题库


给定一个长度为 nn 的数列 A1,A2,,AnA_1, A_2, · · · , A_n 和一个非负整数 xx ,给定 mm 次查询,每次询问能否从某个区间 [l,r][l,r] 中选择两个下标不同的数使得他们的异或等于 xx

输入格式

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

第二行包含 nn 个整数 A1,A2,,AnA_1, A_2, · · · , A_n

接下来 mm 行,每行包含两个整数 li,ril_i,r_i 表示询问区间 [li,ri][l_i,r_i]

输出格式

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

数据范围

对于 20%20\% 的评测用例, 1n,m1001 ≤ n, m ≤ 100
对于 40%40\% 的评测用例, 1n,m10001 ≤ n, m ≤ 1000
对于所有评测用例, 1n,m1000001 ≤ n, m ≤ 1000000x<2200 ≤ x < 2^{20}1lirin1 ≤ l_i ≤ r_i ≤ n0Ai<2200 ≤ A_i < 2^{20}

输入样例:

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

输出样例:

yes
no
yes
no

样例解释

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

解题

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

思路

首先,由异或运算的自反性我们可以得到 ab=cac=ba \oplus b = c \Rightarrow a \oplus c = b

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

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

以动态规划的角度理解:

  • 状态定义:dp[i]dp[i] 表示 1i1 \dots i 中一对异或为 xx 的数中较小的数的最大值。
  • 状态转移方程:dp[i]=max(dp[i1],f(i))dp[i] = \max(dp[i - 1], f(i))f(i)f(i) 定义如上)。
  • 初始状态:dp[1]=0dp[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");
        }
    }
}
0

评论区