Lutece 2160 战争

题目链接: https://acm.uestc.edu.cn/problem/zhan-zheng/description

题目大意:可以增加一个数或者删去一个数,求给定数与拥有的数的异或的最大最小值

分析:

这道题刚看到时并没有什么思路,这又不是简单地比较大小。但是说到比较大小,我就想到了二叉搜索树。于是打开搜索引擎,输入“异或 树”,结果还真的查出来了一些东西。

对于两个数异或的结果,比如,100000是比011111大的,也就是说,只要尽可能的高位异或的结果为1,这个数就是最大值;反之,就是最小值。从某种层面上来说,这是一种贪心。

那么如何快速的确定最高位的1在哪呢?这里联想到Trie树。Trie树可以快速的确定一个字符串在集合中是否存在,同理,我们可以建一个类似的树,来找到最高位的1。

首先要建立合适的数据结构。这里因为有删除数的操作,所以要记录左子树和右子树里是否存在数,如果不存在则不能朝那个方向贪心。然后有两个指针指向左右子结点。

因为数据范围是2^30,所以并不能像线段树那样一开始就开好结点的数组,只能采取需要时再new一个新结点的方式。把一个数的二进制从高位往下遍历,通过指针传递下去,从而达到存储这个数的目的。

增加结点就是++left或者++right,删除结点无非是把++改为–。如果是正常的删除结点的话,需要delete。但是这里delete写起来很麻烦,父结点不能随便删。一个数的最坏情况是调用30次new,而N<=5e5,乘起来就是15M,但是因为不可能都是最坏情况,所以理论上内存空间是够的。

最大最小值思路前面已经说得比较清楚了,就是贪心,所以函数的代码重复率极高。

时间复杂度大概为O(30N)

代码:

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int childsum[2];
	node *child[2];
	node()
	{
		childsum[0] = 0; childsum[1] = 0;
		child[0] = NULL; child[1] = NULL;
	}
};
node *root;
void addnode(int num)
{
	node *p = root;
	int bit;
	for (int i = 30; i >= 0; --i)
	{
		bit = (num&(1<<i)) ? 1 : 0;
		if (p->child[bit]==NULL)
		{
			p->child[bit] = new node();
		}
		++p->childsum[bit];
		p = p->child[bit];
	}
}
void delnode(int num)
{
	node *p = root;
	int bit;
	for (int i = 30; i >= 0; --i)
	{
		bit = (num&(1 << i)) ? 1 : 0;
		--p->childsum[bit];
		p = p->child[bit];
	}
}
int solvemax(int num)
{
	node *p = root;
	int bit;
	bool is;
	int ans=0;
	for (int i = 30; i >= 0; --i)
	{
		bit = (num&(1 << i)) ? 1 : 0;
		if (p->child[bit ^ 1] != NULL && p->childsum[bit ^ 1] != 0)
		{
			p = p->child[bit ^ 1];
			is = true;
		}
		else
		{
			p = p->child[bit];
			is = false;
		}
		if (is)
		{
			ans += (1 << i);
		}
	}
	return ans;
}
int solvemin(int num)
{
	node *p = root;
	int bit;
	bool is;
	int ans = 0;
	for (int i = 30; i >= 0; --i)
	{
		bit = (num&(1 << i)) ? 1 : 0;
		if (p->child[bit] != NULL && p->childsum[bit] != 0)
		{
			p = p->child[bit];
			is = false;
		}
		else
		{
			p = p->child[bit ^ 1];
			is = true;
		}
		if (is)
		{
			ans += (1 << i);
		}
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	int n,o,v;
	root = new node();
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> o >> v;
		if (o == 1)
		{
			addnode(v);
		}
		else if (o == 2)
		{
			delnode(v);
		}
		else if (o == 3)
		{
			cout << solvemin(v) << " " << solvemax(v) << endl;
		}
	}
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注