xor

绝地灬酷狼 2022-06-08 08:42 161阅读 0赞

给出n个数字a\_1,…a\_n,问最多有多少个不重叠的非空区间，使得每个区间内数字的xor都等于0，即得出最大的k，使得存在k个区间（l\[i\],r\[i\]），满足1<=l\[i\]<=r\[i\]<=n，(1<=i<=k)，r\[i\] < r\[i+1\]，(1<=i<=k),且a\[l\[i\]\] xor a\[l\[i\]+1\] xor … xor a\[r\[i\]\] = 0，(1<=i<=k)  
输入描述：第一行一个整数n，第二行n个整数a\_1,a\_2…a\_n,对于30%的数据，n<=20,对于100%的数,n<=100000,a\_i<=100000;  
输出描述：一个整数表示最多的区间个数

import java.util.Scanner;
    
    public class Kqujian {
        static int maxn = 1000000;
        static int[] a = new int[maxn];
        static int[] b = new int[maxn];
        static int[] c = new int[maxn];
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            while(in.hasNext()){
                int ans = 0;
                int pos = -1;
                for (int i = 0; i < n; i++) {
                    a[i] = in.nextInt();
                    if(a[i] == 0){
                        ans++;
                        pos = i+1;
                    }
                    b[a[i]]++;
                    if(b[a[i]] != 0 && b[a[i]] % 2 == 0){
                        int temp = c[a[i]];
                        if(temp < pos)
                            continue;
                        int temp2 = 0;
                        for (int j = temp + 1; j < i; j++) {
                            temp2 = temp2 ^ a[j];
                        }
                        if(temp2 == 0){
                            ans++;
                            pos = i+1;
                        }
    
                    }else
                        c[a[i]] = i;
                }
                System.out.println(ans);
            }
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，161人围观）

还没有评论，来说两句吧...

相关阅读

相关【区间DP】XOR-pyramid

[Problem - B - Codeforces][] 题意： ![ce934eda659b30bf3e5794265e2f9c3f.png][] 思路：考虑区间D

布满荆棘的人生/ 2024年03月26日 20:42/ 0 赞/ 80 阅读

相关【线段树应用】XOR的艺术

lazy tag的应用 [P2574 XOR的艺术 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P2574 XOR_ - _ _ _ _luogu.c

迷南。/ 2024年03月25日 21:13/ 0 赞/ 37 阅读

相关 HDU 5661 Claris and XOR

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=5661][http_acm.hdu.edu.cn_showproblem.ph

淩亂°似流年/ 2022年07月28日 10:50/ 0 赞/ 145 阅读

相关 GCD XOR UVA - 12716 ——筛法建立约数表+xor运算+数学规律

Think: 1埃式筛法思想建立约数表 2初始打表寻找运算的数学规律 3xor运算(不带进位的二进制加法) 运算法则 1. a ⊕ a = 0

短命女/ 2022年06月15日 06:37/ 0 赞/ 156 阅读

相关 UVa12716 - GCD XOR

输入一个整数，有多少对（a，b）满足1<=b<=a<=n，且 gcd（a，b） = a xor b gcd是最大公约数 xor 是异或运算，2进制 1001^10

谁践踏了优雅/ 2022年06月08日 10:10/ 0 赞/ 134 阅读

相关 xor

给出n个数字a\_1,…a\_n,问最多有多少个不重叠的非空区间，使得每个区间内数字的xor都等于0，即得出最大的k，使得存在k个区间（l\[i\],r\[i\]），满足1<=

绝地灬酷狼/ 2022年06月08日 08:42/ 0 赞/ 162 阅读

相关 BZOJ4269 再见xor

考前挣扎线性基裸题 mx直接求次大直接从低到高枚举第一个非0位然后次大就是异或上就行了【显然贪心呐qwq 不到800b可还行 //Love and Fr

ゝ一纸荒年。/ 2021年12月23日 06:19/ 0 赞/ 194 阅读

相关 HDU 3949 XOR——————线性基

[XOR][] Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Othe

以你之姓@/ 2021年11月23日 04:28/ 0 赞/ 260 阅读

相关基于Tensorflow轻松实现XOR运算

对于“XOR”大家应该都不陌生，我们在各种课程中都会遇到，它是一个数学逻辑运算符号，在计算机中表示为“XOR”，在数学中表示为“![\\bigoplus][bigoplus]”

偏执的太偏执、/ 2021年11月10日 09:40/ 0 赞/ 236 阅读

相关【2017西安】 XOR (线性基+思维）

Consider an array AA with n elements . Each of its element is A\[i\]A\[i\] (1 \\le i \\l

亦凉/ 2021年11月09日 11:42/ 0 赞/ 308 阅读