Trie板子复习

#include
using namespace std;
using ll = long long;
using pii = pair;
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;
in服务器托管t cnt = 1;
struct Trie{
	int x[70],num;
}tree[M];
char s[M];

void pre()
{
	for(int i=0;i='0'&&c='a'&&c>n>>q;
	pre();cnt = 1;
	while(n--){cin>>s+1;insert();}
	while(q--){cin>>s+1;cout>_;
	//_ = 1;
	while(_--)solve();
	return 0;
}

01trie

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

异或具有传递性

先看一道经典的板子

经典的O（n*31）

#include
#include

using namespace std;
using ll = long long;
using pii = pair;
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>n;
	for(int i=1;i>a[i];
		insert(a[i]);
	}
	
	int res = 0;
	for(int i=1;i>_;
	_ = 1;
	while(_--)solve();
	return 0;
}

P4551 最长异或路径

注意边权下放的手法

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

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg服务器托管.net

相关推荐: 【Kotlin】Kotlin流程控制

1 选择结构 Kotlin 中选择结构主要包含 if -else、when 语句，并且可以返回结果。 1.1 if-else 1.1.条件选择 fun main() { var score = 85 if (score >= 90) { println(…