第十三届省赛——6选数异或（暴力枚举）

题目：

【问题描述】

给定一个长度为 n 的数列 A1, A2, · · · , An 和一个非负整数 x，给定 m 次查 询, 每次询

问能否从某个区间 [l,r] 中选择两个数使得他们的异或等于 x 。

【输入格式】

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

第二行包含 n 个整数 A1, A2, · · · , An 。

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

【输出格式】

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

【样例输入】

4 4 1

1 2 3 4

1 4

1 2

2 3

3 3

【样例输出】

yes

no

yes

no

【样例说明】

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

【评测用例规模与约定】

对于 20% 的评测用例，1 ≤ n, m ≤ 100；

对于 40% 的评测用例，1 ≤ n, m ≤ 1000；

对于所有评测用例，1 ≤ n, m ≤ 100000 ，0 ≤ x < 2^20 ，1 ≤ li ≤ ri ≤ n ， 0 ≤ Ai < 2^20。

分析

把这个区间所有的值的异或值进行两两比对，如果说有一项相等x就输出yes

步骤：

package 历届真题省赛阶段;

import java.util.Scanner;

public class 测试1 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m=sc.nextInt();
        int x=sc.nextInt();
        int zu[]=new int [n+1];
        for (int i = 1; i <= n; i++) {
            zu[i]=sc.nextInt();
        }
        for (int i = 0; i < m; i++) {
            int from=sc.nextInt();
            int end=sc.nextInt();
            f(zu,from,end,x);
    }
}
    private static void f(int[] zu, int from, int end, int x) {
        for (int j =from; j <=end; j++) {
            for (int j2 =from+1; j2 <=end; j2++) {
                if ((zu[j]^zu[j2])==x) {
                    System.out.println("yes");
                    return;
                }
            }
        }
            System.out.println("no");
        }
    
    }

题目： 【问题描述】 给定一个长度为 n 的数列 A1, A2, · · · , An 和一个非负整数 x，给定 m 次查 询, 每次询 问能否从某个区间 [l,r] 中选择两个数使得他们的异或等于 x 。 【输入格式】 输入的第一行包含三个整数 n, m, x 。 第二行包含 n 个整数 A1, A2, · · · , An 。 接下来 m 行，每行包含两个整数 li ,ri 表示询问区间 [li ,ri ] 。 【输出格式】 对于每个询问, 如果该区间内存在两个数的异或为 x 则输出 yes, 否则输出 no。 【样例输入】 4 4 1 1 2 3 4 1 4 1 2 2 3 3 3 【样例输出】 yes no yes no 【样例说明】 显然整个数列中只有 2, 3 的异或为 1。 【评测用例规模与约定】 对于 20% 的评测用例，1 ≤ n, m ≤ 100； 对于 40% 的评测用例，1 ≤ n, m ≤ 1000； 对于所有评测用例，1 ≤ n, m ≤ 100000 ，0 ≤ x < 2^20 ，1 ≤ li ≤ ri ≤ n ， 0 ≤ Ai < 2^20。 分析 把这个区间所有的值的异或值进行两两比对，如果说有一项相等x就输出yes 步骤： package 历届真题省赛阶段; import java.util.Scanner; public class 测试1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m=sc.nextInt(); int x=sc.nextInt(); int zu[]=new int [n+1]; for (int i = 1; i <= n; i++) { zu[i]=sc.nextInt(); } for (int i = 0; i < m; i++) { int from=sc.nextInt(); int end=sc.nextInt(); f(zu,from,end,x); } } private static void f(int[] zu, int from, int end, int x) { for (int j =from; j <=end; j++) { for (int j2 =from+1; j2 <=end; j2++) { if ((zu[j]^zu[j2])==x) { System.out.println("yes"); return; } } } System.out.println("no"); } }