NC213985. ColorSequence
描述
You are given a integer sequence c of length n, ci denotes the ith color in the sequence c.
We define a color sequence is legal only if it merely contains colors that appear even number of times.
For example, sequence {0,1,0,1} is legal because both color 1 and 0 appear 2 times, and 2 is an even number. And sequence {0,1,0} is illegal because color 1 only appear 1 time, and 1 is not an even number.
Now, you need to figure out how many consecutive subsequence of c that is a legal color sequence.输入描述
The first line contains one integern(1≤n≤106), the length of the sequence c.
The second line contains n integer, the ith integer denotes the ith color, ci(0≤ci≤20).
输出描述
Print one integer as the answer.
示例1
输入:
3 1 1 1
输出:
2
Python3 解法, 执行用时: 1574ms, 内存消耗: 121672K, 提交时间: 2022-04-11 19:48:47
import collections
n=int(input())
ls=list(map(int,input().split()))
pre=0
f=[0]*n
res=0
dic=collections.defaultdict(int)
dic[0]=1
for i in range(n):
pre^=1<<ls[i]
f[i]=pre
res+=dic[f[i]]
dic[f[i]]+=1
# print(f)
print(res)
C++ 解法, 执行用时: 174ms, 内存消耗: 16936K, 提交时间: 2021-09-26 20:18:15
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[1<<21+5],n,ans,y,x;
int main() {
cin>>n;
a[0]=1;
for(int i = 1; i <= n; ++i) {
cin>>x;
y^=(1<<x);
ans+=a[y]++;
}
cout<<ans;
}