GDOI T2 求证明 or 证伪

大致思路：做前缀异或和，记录

lst

为上一个区间异或

=0

的下标，如果遇到前缀异或和为

0

就将

[lst,i]

删去，遇到相同的数字就

[mp[pre[i]],i]

删去，最终答案为

n-

删去区间长度；

感觉很危/jk，但是手玩了几个小数据没问题（

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans,lst=1;
int now=0;
int a[100009];
map<int,int> mp;
signed main(){
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
	cin>>n;
	a[1]=0;
	for(int i=2;i<=n+1;i++) cin>>a[i];
	mp[0]=1;
	for(int i=2;i<=n+1;i++){
		now=now^a[i];
		if(now==0){
			ans+=(i-lst);
			lst=i;
		}
		if(mp[now]>0){
			if(lst<=mp[now]){
				ans+=(i-mp[now]);
				lst=i;
			}
		}
		mp[now]=i;
	}
	if(ans==n) cout<<"-1"<<endl;
	else cout<<n-ans<<endl;
	return 0;
}
/*
5
8 3 5 7 1
4
5 5 7 2
10
1 3 5 7 2 4 6 8 10 9
*/

GDOI T2 求证明 or 证伪

讨论操作

回复

相关推荐

GDOI T2 求证明 or 证伪