Trie板子复习

时间：2024-04-01 18:06:55

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int N = 3e6+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int qmi(int a,int b,int mod){int res=1;while(b){if(b&1)res=res*a%mod;b>>=1;a=a*a%mod;}return res;}


int n,q,m;
const int M = 3e6+10;
int cnt = 1;
struct Trie{
	int x[70],num;
}tree[M];
char s[M];

void pre()
{
	for(int i=0;i<=cnt;++i){
	 	for(int j=0;j<=69;++j){
	 		tree[i].x[j] = 0;
	 	}	
	 	tree[i].num = 0;
	}
}


int getnum(char c)
{
	if(c>='0'&&c<='9')return c-'0';
	if(c>='a'&&c<='z')return c-'a'+10;
	return c-'A'+37;
}


void insert()
{
	int pos=1,len = strlen(s+1);
	for(int i=1;i<=len;++i){
		int num = getnum(s[i]);
		if(!tree[pos].x[num])tree[pos].x[num] = ++cnt;
		pos = tree[pos].x[num];
		tree[pos].num++;
	}
}

int find()
{
	int pos = 1,len = strlen(s+1);
	for(int i=1;i<=len;++i){
		int num = getnum(s[i]);
		if(!tree[pos].x[num])return 0;
		pos = tree[pos].x[num];
	}
	return tree[pos].num;
}






void solve()
{
	cin>>n>>q;
	pre();cnt = 1;
	while(n--){cin>>s+1;insert();}
	while(q--){cin>>s+1;cout<<find()<<"\n";}
}
signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _;
	cin>>_;
	//_ = 1;
	while(_--)solve();
	return 0;
}

01trie

解决树上异或问题，维护根节点到每一个点的异或值，转化成O(n)*31 的查询问题

异或具有传递性

先看一道经典的板子

经典的O（n*31）

#include<iostream>
#include<cstring>

using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int N = 1e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int qmi(int a,int b,int mod){int res=1;while(b){if(b&1)res=res*a%mod;b>>=1;a=a*a%mod;}return res;}


int n,q,m;
const int M = 2e6+10;
struct Trie{
	int x[2],num;
}tree[M];
int cnt = 1;

// int e[N],ne[N],w[N],h[N],idx;
// void add(int a,int b,int c){
	// e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
// }

void insert(int x){
	int pos = 1;
	for(int i=30;i>=0;--i){
		int t = x>>i&1;
		if(!tree[pos].x[t])tree[pos].x[t] = ++cnt;
		pos = tree[pos].x[t];
		tree[pos].num++;
	}
}

int find(int x){
	int pos = 1;
	int res = 0;
	for(int i=30;i>=0;--i){
		int t = x>>i&1;
		if(tree[pos].x[!t]){res+=(1<<i);pos = tree[pos].x[!t];}
		else pos = tree[pos].x[t];
	}
	return res;
}


int a[N];
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		insert(a[i]);
	}
	
	int res = 0;
	for(int i=1;i<=n;i++)res = max(res,find(a[i]));
	
	cout<<res;
	

}

signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _;
	//cin>>_;
	_ = 1;
	while(_--)solve();
	return 0;
}

P4551 最长异或路径

注意边权下放的手法

再看一道经典的树上 其实就是上面的套个皮

相关文章