xor

[编程题]xor

热度指数：1999 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

给出n个数字 a_1,...,a_n，问最多有多少不重叠的非空区间，使得每个区间内数字的xor都等于0。

输入描述:

第一行一个整数ｎ； 第二行ｎ个整数　a_1,...,a_n； 对于30%的数据，n<=20； 对于100%的数据，n<=100000, a_i<=100000；

输出描述:

一个整数表示最多的区间个数；

示例1

输入

4
3 0 2 2

输出

算法知识视频讲解

Java

Sen🍓🍀

区间和问题 (前缀和 + 哈希表)，需要注意区间非重叠，找到一个就要清空Set/Map

import java.util.*;

// 区间异或和： 前缀和 + Set
// 类似：求子数组区间和 = 定值K
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Set<Integer> set = new HashSet<>();
        set.add(0); // 初始0
        int xor = 0, res = 0;
        for (int i = 0; i < n; i++) {
            xor ^= in.nextInt();
            if (set.contains(xor)) {
                res++;
                set.clear();  // 非重叠区间：找到1个就清空前面的
            }
            set.add(xor);
        }
        System.out.println(res);
    }
}

发表于 2025-06-30 18:05:28 回复(0)

Java

loveeee

//设置一个start位置用来分隔前面已经找到的异或为0的最多的区间数，后面每个数字向前搜索只能到start位置，若搜索到start位置前区间数只会变少。num对区间数进行计数。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int arr[] = new int[n];
            for(int i=0;i<n;i++){
                arr[i] = sc.nextInt();
            }
            int num=0;
            int start =0;
            for(int i=0;i<n;i++){
                int tmp=0;
                for(int j=i;j>=start;j--){
                    tmp^=arr[j];
                    if(tmp==0){
                        num++;
                        start = i+1;
                        break;
                    }
                }
            }
            System.out.println(num);
        }
    }
}

发表于 2018-09-15 00:02:42 回复(0)