异或数组

也许更好的阅读体验

D e s c r i p t i o n \mathcal{Description} Description

给你两个长度为 n n n的数组 a , b a,b a,b
你需要把 a , b a,b a,b两个数组分别按某种方式排序
然后令 c i = a i <mtext>   </mtext> x o r <mtext>   </mtext> b i c_i=a_i\ xor\ b_i ci=ai xor bi,你要使 c c c的字典序最小
请输出 c c c这个数组
n 200000 <mtext>   </mtext> a i , b i 2 30 n\leq200000\ a_i,b_i\leq 2^{30} n200000 ai,bi230

S o l u t i o n \mathcal{Solution} Solution

a , b a,b a,b这两个数组的数分别放到一个 01 T r i e 01Trie 01Trie树里面
并记下每个点的位置有多少串经过
然后考虑构造 c c c
两个 T r i e Trie Trie树一起开始跑,从 2 30 2^{30} 230开始考虑
先考虑两边异或起来为 0 0 0的情况,再考虑两边异或起来为 1 1 1
这样跑完 2 0 2^0 20的点后就可以得到一个 c c c,并且一定是最优的

接下来则是技巧的问题
如果对 c c c的每个元素单独算,即每次都重新匹配一次,尽管我将其改为 b f s bfs bfs并且进行了些优化,但仍然会 T ( 50 p t s ) T(50pts) T(50pts)

考虑一遍 d f s dfs dfs处理所有的答案
在每个位置都先考虑异或起来为 0 0 0,再考虑异或起来为 1 1 1的情况
然后每次将改点经过的串的个数减 1 1 1
这样就可以过了

C o d e \mathcal{Code} Code

50分代码

/******************************* Author:Morning_Glory LANG:C++ Created Time:2019年09月16日 星期一 09时45分46秒 *******************************/
#include <cstdio>
#include <fstream>
#include <algorithm>
using namespace std;
const int len = 30;
const int maxn = 3000006;
//{{{cin
struct IO{
	template<typename T>
	IO & operator>>(T&res){
		res=0;
		bool flag=false;
		char ch;
		while((ch=getchar())>'9'||ch<'0')	flag|=ch=='-';
		while(ch>='0'&&ch<='9')	res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar();
		if (flag)	res=~res+1;
		return *this;
	}
}cin;
//}}}
int n,a,b,h,t,k,cnt;
int mi[len+1],res[maxn];
int q[3][maxn];//q[0] -> 哪一位 q[1] -> na q[2] -> nb
struct Trie{
	int tot=1;
	int num[maxn];
	int ch[maxn][2];
	//{{{insert
	void insert (int s)
	{
		int now=1;
		for (int i=len;i>=0;--i){
			bool to=s&mi[i];
			if (!ch[now][to]) ch[now][to]=++tot;
			now=ch[now][to];
			++num[now];
		}
	}
	//}}}
}A,B;
//{{{dfs
void dfs(int x,int y,int S,int k)
{
	if(x) --A.num[x],--B.num[y];
	if(k<0) {	res[++cnt]=S;return;}
	while(A.num[A.ch[x][0]]&&B.num[B.ch[y][0]])  dfs(A.ch[x][0],B.ch[y][0],S,k-1);
	while(A.num[A.ch[x][1]]&&B.num[B.ch[y][1]])  dfs(A.ch[x][1],B.ch[y][1],S,k-1);
	while(A.num[A.ch[x][0]]&&B.num[B.ch[y][1]])  dfs(A.ch[x][0],B.ch[y][1],S|mi[k],k-1);
	while(A.num[A.ch[x][1]]&&B.num[B.ch[y][0]])  dfs(A.ch[x][1],B.ch[y][0],S|mi[k],k-1);
}
//}}}
int main()
{
	mi[0]=1;
	for (int i=1;i<=len;++i)	mi[i]=mi[i-1]<<1;
	cin>>n;
	for (int i=1;i<=n;++i)	cin>>a,A.insert(a);
	for (int i=1;i<=n;++i)	cin>>b,B.insert(b);
	dfs(1,1,0,30);
	sort(res+1,res+n+1);
	for (int i=1;i<=n;++i)	printf("%d ",res[i]);
	return 0;
}

100分代码

/******************************* Author:Morning_Glory LANG:C++ Created Time:2019年09月16日 星期一 09时45分46秒 *******************************/
#include <cstdio>
#include <fstream>
#include <algorithm>
using namespace std;
const int len = 30;
const int maxn = 3000006;
//{{{cin
struct IO{
	template<typename T>
	IO & operator>>(T&res){
		res=0;
		bool flag=false;
		char ch;
		while((ch=getchar())>'9'||ch<'0')	flag|=ch=='-';
		while(ch>='0'&&ch<='9')	res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar();
		if (flag)	res=~res+1;
		return *this;
	}
}cin;
//}}}
int n,a,b,h,t,k,cnt;
int mi[len+1],res[maxn];
int q[3][maxn];//q[0] -> 哪一位 q[1] -> na q[2] -> nb
struct Trie{
	int tot=1;
	int num[maxn];
	int ch[maxn][2];
	//{{{insert
	void insert (int s)
	{
		int now=1;
		for (int i=len;i>=0;--i){
			bool to=s&mi[i];
			if (!ch[now][to]) ch[now][to]=++tot;
			now=ch[now][to];
			++num[now];
		}
	}
	//}}}
}A,B;
//{{{dfs
void dfs(int x,int y,int S,int k)
{
	if(x) --A.num[x],--B.num[y];
	if(k<0) {	res[++cnt]=S;return;}
	while(A.num[A.ch[x][0]]&&B.num[B.ch[y][0]])  dfs(A.ch[x][0],B.ch[y][0],S,k-1);
	while(A.num[A.ch[x][1]]&&B.num[B.ch[y][1]])  dfs(A.ch[x][1],B.ch[y][1],S,k-1);
	while(A.num[A.ch[x][0]]&&B.num[B.ch[y][1]])  dfs(A.ch[x][0],B.ch[y][1],S|mi[k],k-1);
	while(A.num[A.ch[x][1]]&&B.num[B.ch[y][0]])  dfs(A.ch[x][1],B.ch[y][0],S|mi[k],k-1);
}
//}}}
int main()
{
	mi[0]=1;
	for (int i=1;i<=len;++i)	mi[i]=mi[i-1]<<1;
	cin>>n;
	for (int i=1;i<=n;++i)	cin>>a,A.insert(a);
	for (int i=1;i<=n;++i)	cin>>b,B.insert(b);
	dfs(1,1,0,30);
	sort(res+1,res+n+1);
	for (int i=1;i<=n;++i)	printf("%d ",res[i]);
	return 0;
}


如有哪里讲得不是很明白或是有错误,欢迎指正
如您喜欢的话不妨点个赞收藏一下吧

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务