给出n个数字 a_1,...,a_n,问最多有多少不重叠的非空区间,使得每个区间内数字的xor都等于0。
即找出最大的k,使得存在k个区间(l[i], r[i]),满足1<=l[i]<=r[i]<=n (1<=i<=k), r[i]<l[i+1](1<=i<k), 且 a[l[i]] xor a[l[i]+1] xor... xor a[r[i]] = 0 (1<=i<=k)
即找出最大的k,使得存在k个区间(l[i], r[i]),满足1<=l[i]<=r[i]<=n (1<=i<=k), r[i]<l[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_n; 对于30%的数据,n<=20; 对于100%的数据,n<=100000, a_i<=100000;
一个整数表示最多的区间个数;
4 3 0 2 2
2
[0] xor = 0,[2,2] 2 xor 2 = 0,所以总共是2个不重叠的非空区间
比较复杂的一个解法