【01trie】CF1851F

清疚 2024-03-22 21:07 81阅读 0赞

[Problem - F - Codeforces][]

题意：

![cc8869e75b7b4f14ad11f61c54146dfb.png][]

![821c4d9f94db4c94b486f9718b72b11f.png][]

![ce329efd055441b096e02df747b6ce39.png][]

思路：

首先最大异或对可以用01trie解决

[trie树入门\_lamentropetion的博客-CSDN博客][trie_lamentropetion_-CSDN]

ai xor x 和 aj xor x 都必须为1

因此可以转换为 ai 和 aj 最小异或对问题

改一下01trie的板子即可

主要修改部分在query上

p是 ai 的 01串 ，x应与 ai 相反

id\[p\] 表示 idx 为 p 的01串（数字）对应的下标值

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    
    int N,K;
    int idx=0;
    int a[mxn]; 
    int tr[mxn*30][2],id[mxn*30];
    
    void insert(int x){
    	int u=a[x];
    	int p=0;
    	for(int j=K-1;j>=0;j--){
    		int bit=((u>>j)&1);
    		if(!tr[p][bit]) tr[p][bit]=++idx;
    		p=tr[p][bit];
    	}
    	id[p]=x;//该idx对应的数的下标 
    }
    array<int,4> query(int x){
    	int u=a[x];
    	int p=0,val=0,t=0;
    	for(int j=K-1;j>=0;j--){
    		int bit=(u>>j)&1;
    		if(tr[p][bit]){
    			val|=(1<<j);
    			if(bit==0) t|=(1<<j);
    			p=tr[p][bit];
    		}else p=tr[p][bit^1];
    	}
    	return array<int,4>{val,id[p],x,t};
    }
    void init(){
    	for(int i=0;i<=idx;i++){
    		for(int j=1;j>=0;j--) tr[i][j]=0;
    		id[i]=0;
    	}
    	idx=0;
    }
    void solve(){
    	cin>>N>>K;
    	init();
    	for(int i=1;i<=N;i++) cin>>a[i];
    	array<int,4> ans{-1};
    	insert(1);
    	for(int i=2;i<=N;i++){
    		ans=max(ans,query(i));
    		insert(i);
    	}
    	cout<<ans[1]<<" "<<ans[2]<<" "<<ans[3]<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - F - Codeforces]: https://codeforces.com/contest/1851/problem/F
[cc8869e75b7b4f14ad11f61c54146dfb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/6e0702c644314f2aa526d321f087b964.png
[821c4d9f94db4c94b486f9718b72b11f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/c7727fcce1a14926b7587c2db8d71994.png
[ce329efd055441b096e02df747b6ce39.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/518223a170f0470b8b4076364f5d6f7c.png
[trie_lamentropetion_-CSDN]: https://blog.csdn.net/weixin_62528401/article/details/128623188