【代码源】#51. 最大异或和(trie字典树 + 贪心)

发布于 2022-10-18  324 次阅读


题目传送门:最大异或和 - Problem - Daimayuan Online Judge

分析

不难发现用可以先预处理出异或前缀和,然后一段区间[l, r]的异或和可以用prefix[r] ^ prefix[l - 1]来表示。

现在问题就转化为对于一个r,在[1, r]的区间内找到一个l(当l == r说明区间内只有一个点),使得prefix[r]^prefix[l - 1]最大,那么l - 1的取值范围就是[0, r - 1]。

现在建立一颗trie树,一边插入一边查询,因为数据范围是(2^30)-1,所以我们可以建一颗30层的树,从上往下表示从第30位到第0位,然后将数字插入到树中,每个点有一个标记,表示是prefix中的下标,另外还有两个指针指向0儿子和1儿子。经过的边表示这个数字的值。

那么现在我们贪心地想,假如现在prefix[r] = x,那么我们找一个y,从高位到低位,尽量地使得y的高位的x的高位不同,可以使得异或结果尽可能大,如果没办法不同,那就只能相同咯。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 9;
struct Node
{
	int id, son[2];
}t[maxn * 31];

int N, a[maxn], prefix[maxn], tidx = 1;//1 is the root of tree

void insert(int x, int id)
{
	for(int i = 30, o = 1;i >= 0; -- i)
	{
		int k = x >> i & 1;//k is the val of x[i]
		if(!t[o].son[k])t[o].son[k] = ++ tidx;
		o = t[o].son[k];
		
		if(i == 0)t[o].id = id;
	}
}

int findMaxId(int x)//返回l - 1 
{
	int res = 0;
	for(int i = 30, o = 1;i >= 0; -- i)
	{
		int k = x >> i & 1;
		if(t[o].son[k ^ 1])o = t[o].son[k ^ 1];
		else o = t[o].son[k];
		
		if(i == 0)res = t[o].id;
	}
	return res + 1;
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N;
	for(int i = 1;i <= N; ++ i)cin >> a[i];
	for(int i = 1;i <= N; ++ i)prefix[i] = prefix[i - 1] ^ a[i];
	insert(0, 0);
	for(int i = 1;i <= N; ++ i)
	{
		int l = findMaxId(prefix[i]);
		cout << (prefix[i] ^ prefix[l - 1]) << ' ' << l << '\n';
		
		insert(prefix[i], i);
	}
	
	return 0;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-10-18