Usaco Training Section 6.1 Cow XOR

Cow XOR 奶牛异或
农民约翰在喂奶牛的时候被另一个问题卡住了.他的所有N(1 <= N <= 100,000)个奶牛在他面前排
成一行(按序号1..N 的顺序),按照它们的社会等级排序.奶牛#1 由最高的社会等级,奶牛#N 最低.
每个奶牛同时被赋予了一个唯一的数在0..2^21 - 1 的范围内.
帮助农民约翰找出应该从那一头奶牛开始喂,使得从它开始的某一个连续的自序列上的奶牛的数的
异或最大.如果有多个这样的子序列,选择结尾的奶牛社会等级最高的.如果还不唯一,选择最短的.
PROGRAM NAME: cowxor
INPUT FORMAT
• 第1 行:一个单独的整数N.
• 第2 到N + 1 行:N 个0..2^21 – 1 之间的整数,代表每头奶牛的被赋予的数.第j 行描述了社
会等级j – 1 的奶牛.
SAMPLE INPUT (file cowxor.in)
5
1
0
5
4
2
OUTPUT FORMAT
• 第 1 行: 3 个空格隔开的整数,分别为:最大的异或值,序列的起始位置、终止位置.
SAMPLE OUTPUT (file cowxor.out)
6 4 5

分析：求一个区间的异或和，我们可以用前缀和，即sum[r]^sum[l-1]。不过在这题中，我们不能枚举每个区间，否则会超时。于是我们可以考虑优化这一算法：依次将sum[i]放到一棵01二叉树上（类似trie树），以每个sum作为右端点在之前的sum构成的trie树上用贪心法找最大值。若第j步存在(sum[i]的第j位^1)的边，就走这条边，否则走另一条边。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define inf 2147483647
#define mp make_pair
#define pii pair<int,int>
#define pb push_back
#define r1 rt<<1
#define r2 rt<<1|1
#define ld long double
using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
	return x*f;
}

const int N=800000;
const int M=22;
int i,cnt,tree[N][2],a[M],num[N],sum[100005];

void insert(int k,int s){
	if(s==M){num[k]=i;return;}
	int x=a[s];
	if(tree[k][x]) insert(tree[k][x],s+1);
	else{
		tree[k][x]=++cnt;
		insert(cnt,s+1);
	}
}

int find(int k,int s){
	int x=a[s];
	if(tree[k][x^1]) return find(tree[k][x^1],s+1);
	if(tree[k][x]) return find(tree[k][x],s+1);
	return num[k];
}

int main()
{
	freopen("cowxor.in","r",stdin);
	freopen("cowxor.out","w",stdout);
	int n=read(),ans=-1,ansl,ansr;cnt=0;
	for(i=1;i<=n;++i){
		int x=read(),p=0;
		sum[i]=sum[i-1]^x;
		x=sum[i];
		while(p<M-1) a[++p]=x&1,x>>=1;
		for(int j=1;j<=(p>>1);++j) swap(a[j],a[p+1-j]);
		int y=find(0,1);
		if((sum[i]^sum[y])>ans){
			ansl=y+1;
			ansr=i;
			ans=sum[i]^sum[y];
		}
		insert(0,1);
	}
	printf("%d %d %d\n",ans,ansl,ansr);
	return 0;
}

Usaco Training Section 6.1 Cow XOR

相关推荐