最大异或值2

发表于   |   分类于   |  

数组最大前缀后缀异或

描述

给一个长度为n的整数序列，现在要你截取这个序列的一个前缀和一个后缀(前缀和后缀不能相交)，使得前缀和后缀的异或值最大。
给一个长度为n的整数序列，现在要你截取这个序列的一个前缀和一个后缀(前缀和后缀不能相交)，使得前缀和后缀的异或值最大。
前缀和后缀可以为空，为空时他们的值为0。

input

有多组测试数据，请处理到文件结束。
对于每组测试数据，第一行包含一个整数n(1<=n<=100 000)。
接下来一行有n个用空格隔开的整数a1, a2, a3, …, an (0 <= ai <= 1000 000 000 000)。

output

对于每组测试数据输出一行，保包含一个整数，表示异或的最大的值。

sample input

2
1 2
3
1 2 3
2
1000 1000

sample output

3
3
1000

分析

因为两个相同的值异或为0，那么以 1 2 4 8 16 为例
如果 1 2 4 8为前缀， 4 8 16为后缀，他们是有交叉的，但由于异或的性质，他与 前缀1 2和后缀 16等价，因为中间相同的部分异或为0.
即 1^2^4^8^4^8^16 =1^2^16 。
这样我们先对所有前缀插入字典树，然后对于每一个后缀来查找，求出最大值即可。
即使交叉也无所谓，不会影响最后的结果，只是计算的复杂度有所增加。
注意这里的search函数里求result的方法
为了预防多次测试trie树没有清空造成错误，可以每次在while循环内部实例化root

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<stdio.h>
#define N 100005
#define INT_MIN 0x80000000
long long num[N];
struct trie
{
	trie* next[2];
	trie()
	{
		next[0] = NULL;
		next[1] = NULL;
	}
};
trie* root;

void insert(long long num)
{
	trie* p = root;
	for (int i = 31; i>=0; i--)
	{
		int k = (num >> i) & 1;
		if (p->next[k] == NULL)
		{
			p->next[k] = new trie();
		}
		p = p->next[k];
	}
}

long long search(long long num)
{
	long long result = 0;
	num = ~num;
	trie* p = root;
	for (int i = 31; i >= 0; i--)
	{
	    result<<=1;
		int k = (num >> i) & 1;
		if (k == 1)
		{
			if (p->next[1] != NULL)
			{
				result ++;
				p = p->next[1];
			}
			else
			{
				p = p->next[0];
			}
		}
		else
		{
			if (p->next[0] != NULL)
			{
				result ++;
				p = p->next[0];
			}
			else
			{
				p = p->next[1];
			}
		}
	}
	return result;
}

int main()
{
	int n;
	while (scanf("%d", &n) != EOF)
	{
	    root=new trie();
		for (int i = 0; i<n; i++)
		{
			scanf("%lld", &num[i]);
		}
		long long temp=0;
		insert(temp);
		for (int i = 0; i<n; i++)
		{
			temp^=num[i];
			insert(temp);
		}
		temp=0;
		long long MAX=search(temp);
		for(int j=n-1;j>=0;j--)
		{
			temp^=num[j];
			long long cnt=search(temp);
			if(cnt>MAX)
			{
				MAX=cnt;
			}
		}
		printf("%lld\n", MAX);
	}
	return 0;
}