全wa,样例已过,求调QAQ
查看原帖
全wa,样例已过,求调QAQ
1065103
Atri_Lobato楼主2024/8/4 17:32
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n;
bool num_2[30005];
int trie[20000005][3];
int total=1;

void tran(int num)
{
	memset(num_2,0,sizeof(num_2));
	int len=0;
	while(num)
	{
		len++;
		num_2[len]=num%2;
		num/=2;
	}
}
void insert()
{
	int len=31;
	int pointer=1;
	for(int i=len;i>=1;i--)
	{
		int t=num_2[i];
		if(trie[pointer][t]==0)
		{
			trie[pointer][t]=++total;
		}
		pointer=trie[pointer][t];
	}
}
int ans=0;
void choose()
{
	int tans=0;
	int pointer=1;
	for(int i=1;i<=31;i++)
	{
		if(trie[pointer][0]&&trie[pointer][1])
		{
			tans+=1<<(31-i);
			pointer=trie[pointer][!num_2[i]];
		}
		else if(trie[pointer][0])
		{
			pointer=trie[pointer][0];
		}
		else if(trie[pointer][1])
		{
			pointer=trie[pointer][1];
		}
	}
	ans=max(ans,tans);
}
void dfs(int pointer,int layer)
{
	if(layer==32)
	{
		choose();
		return;
	}
	if(trie[pointer][0])
	{
		num_2[layer]=0;
		dfs(trie[pointer][0],layer+1);
	}
	if(trie[pointer][1])
	{
		num_2[layer]=1;
		dfs(trie[pointer][1],layer+1);
	}
	return;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int num;
		scanf("%d",&num);
		tran(num);
		insert();
	}
	memset(num_2,0,sizeof(num_2));
	dfs(1,1);
	cout<<ans;
	return 0;
}
2024/8/4 17:32
加载中...