求助简单题
  • 板块学术版
  • 楼主A_Bit_Coldwinner?
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/6/28 17:50
  • 上次更新2024/6/28 20:29:59
查看原帖
求助简单题
623291
A_Bit_Coldwinner?楼主2024/6/28 17:50

给定 nn 个数,请选出两个数让它们的异或值最大,n≤106n\le10^6。

已知这道题是 Trie 树,思路没问题,但是后面 66 个点老是 RE 啊啊啊!求求了,悬关。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct Node{long long c; map <long long,int> p;} trie[N];
long long cnt=1,a[N]; string s[N];
void change(long long x,long long y) {
	long long len=0;
	while(x) {
		a[++len]=x%2; x/=2;
	}
	for(int i=1;i<=len/2;i++) swap(a[i],a[len-i+1]);
	for(int i=1;i<=32-len;i++) s[y]+='0';
	for(int i=32-len+1;i<=32;i++) s[y]+=(a[i-(32-len)]+'0');
	return;
}
void insert(string s) {
    long long i=0,u=1;
    while(s[i]) {
        if(trie[u].p.count(s[i]))
            u=trie[u].p[s[i++]];
        else
            trie[u].p[s[i++]]=++cnt,u=cnt;
        ++trie[u].c;
    }
	return;
}
long long ask(string s) {
	long long i=0,u=1,sum=0,k=31;
    while(s[i]) {
    	char op;
    	if(s[i]=='0') op='1';
    	else op='0';
        if(trie[u].p.count(op))
            u=trie[u].p[op],sum+=1<<k;
        else
		    u=trie[u].p[s[i]];
        i++,k--;
    }
    return sum;
}
int main() {
	freopen("xor.in","r",stdin);
	freopen("xor.out","w",stdout);
	long long n,m,ans=0; cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		change(a[i],i),insert(s[i]);
	}
	for(int i=1;i<=n;i++) {
		ans=max(ans,ask(s[i]));
	}
	cout<<ans;
	return 0;
}
2024/6/28 17:50
加载中...