滴滴xor
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
/*
题意：一个长度为n的序列，定义一个区间为[l,r](l<=r)
如果区间内的异或值为0，那么这个区间称为一个合法区间
输出序列中存在的多少个不相交区间。
4
3 0 2 2
区间[2,2]={0} [3,4]={2,2} [2,4]={0,2,2}是合法区间
答案是2
dp[i]表示以i为结尾的答案,那么可以选择第i个数，也可以不选
如果不选i的话，那么dp[i]=dp[i-1]
如果选的话，那么要找到最靠右的那么[l,i]使得区间是合法区间
怎么快速选，记录a[i]为前缀异或，也就是1-i的异或值,如果a[i]=x，
那么如果a[l-1]=x，那么[l,i]的合法区间,剩下的就简单了
复杂度O(n)，不过看到人O(n^2)都过了,n=1e5，一定是评测姬跑的太快了(数据太水了,可能n只有5e4)
*/
int a[maxn],n;
int dp[maxn];
map<int,int> vis;
int main(){
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
a[i]^=a[i-1];
dp[i]=dp[i-1];
int last=vis[a[i]];
if(last>0)dp[i]=max(dp[i],dp[last]+1);
else if(a[i]==0) dp[i]=1;
vis[a[i]]=i;
}
cout<<dp[n]<<endl;
return 0;
}
#网易##滴滴#
查看15道真题和解析
投递小米集团等公司10个岗位 >