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

输出

算法知识视频讲解

Python

怪兽的靴子

#用一个set或者map更新一下。每重复出现一次就清空一下所有信息并且答案++，
#然后重新保存set或map。开始的时候要放一个map[0]为了考虑边界条件（也就是一开始就是0的情况）
a=[3,0,2,2]
num = set([0])
last = 0
ans = 0
for i in a:
    last ^= i
    if last in num: 
        print(last)
        ans += 1
        num = set([0])    #
        last = 0
    else:
        num.add(last)
print(ans)

发表于 2019-08-27 01:12:59 回复(0)

Python