01trie板子题目多组数据求助优化常数和卡常
查看原帖
01trie板子题目多组数据求助优化常数和卡常
567739
Sellaris楼主2022/5/26 00:01

RT。常数写大了。CF机子1s这个做法是可以过的。球球大佬帮忙优化常数。

///*****Sellaris*****///
//#pragma once
#pragma GCC optimize(2)
#pragma GCC optimize(3)

#include <bits/stdc++.h>
//#include <bits/extc++.h>

#define ll long long

using namespace std;
//using namespace __gnu_pbds;

const int maxn=1e6+10;
const int logn=20;

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){ret=ret*10+ch-'0';ch=getchar();}
    return ret*f; //x=(x<<1)+(x<<3)+(ch^48);
}

int a[maxn]={0};
int trie[2][maxn*logn];
int cnt=1;

inline void insert(int x){
	int p=1;
	for(int i=17;i>=0;i--){
		int reg=(x>>i)&1;
		if(trie[reg][p]==0) trie[reg][p]=++cnt;
		p=trie[reg][p];
	}
}
inline int MIN(int x){
	int p=1,ans=0;
	for(int i=17;i>=0;i--){
		int reg=(x>>i)&1;
		if(trie[reg][p]) p=trie[reg][p];
		else p=trie[1-reg][p],ans+=1<<i;
	}
	return ans;
}
inline int MAX(int x){
	int p=1,ans=0;
	for(int i=17;i>=0;i--){
		int reg=(x>>i)&1;
		if(trie[1-reg][p]) p=trie[1-reg][p],ans+=1<<i;
		else p=trie[reg][p];
	}
	return ans;
}

inline void solve(){
	int l=read();int r=read();
	for(int i=0;i<=cnt;i++) 
	    trie[0][i]=trie[1][i]=0;
	int cnt=1;
	bool flag=false;
	
	for(int i=l;i<=r;i++) a[i]=read(),insert(a[i]);
	for(int i=l;i<=r;i++) {
		register int x=l^a[i];
		if(MIN(x)==l && MAX(x)==r) {
			printf("%d\n",x);
			flag=true;
			break;
		}
	}
	
	if(flag==0) puts("0");
}
signed main(){
    //std::ios::sync_with_stdio(false);std::cin.tie(NULL);std::cout.tie(NULL);
    //freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	int t=read();
	while(t--){solve();}
    return 0;
}

2022/5/26 00:01
加载中...