滴滴出行2018校园招聘网申笔试-研发工程师-编程题一

发表于 | 分类于 ，

题目

描述

给出 n 个数字 a[i],,,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...xora[r[i]]=0 (1<=i<=k)

输入

第 1 行一个整数 n,第 2 行 n 个整数 a[i]...a[n]

输出

1 个整数表示最多区间的个数

Example

Input

4
3 0 2 2

Output

2

题解

贪心

  • 记开始处为 s=1,计数器 c=0
  • 寻找第一个满足条件的连续子序列,假设为 i~j (s<=i<=j=n)
  • 计数器 c=c+1
  • 从 j+1 处开始,即 s=j+1,继续 2,3 步
  • 最终计数器 c 即为所求
  • 时间复杂度 O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>

using namespace std;

int arr[1000010],n,c;
bool bef_ext[1000010];

int main(){
    c=0;
    scanf("%d",&n);
    int i=1,s;
    arr[0]=0;
    memset(bef_ext,0,sizeof bef_ext);
    bef_ext[0]=1;
    while(i<=n)
    {
        scanf("%d",arr+i);
        arr[i]^=arr[i-1];
        if(bef_ext[arr[i]])
        {
            ++c;
            memset(bef_ext,0,sizeof bef_ext);
            bef_ext[0]=1;
        }
        bef_ext[arr[i]]=1;
        ++i;
    }
    cout<<c;
}