前缀统计

思路

Trie模板

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,trie[100010][30],cnt[100010],idx;
void insert(string s)
{
	int p=0;
	for(int i=0;i<s.size();i++)
	{
		if(!trie[p][s[i]-'a']) trie[p][s[i]-'a']=++idx;
		p=trie[p][s[i]-'a'];
	}
	cnt[p]++;
	
}
int find(string s)
{
	int p=0,sum=0;
	for(int i=0;i<s.size();i++)
	{
		if(!trie[p][s[i]-'a']) return sum;
		p=trie[p][s[i]-'a'];
		sum+=cnt[p];
	}
	return sum;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		string s;
		cin>>s;
		insert(s);
	}
	for(int i=1;i<=m;i++)
	{
		string s;
		cin>>s;
		cout<<find(s)<<endl;
	}
}

最大异或对

思路

我们可以枚举第一个数，用Trie求出和它异或最大值的数， 求$max$

代码

#include<bits/stdc++.h>
using namespace std;
int n,trie[3000010][2],a[100010],idx;
void insert(int s)
{
	int p=0;
	for(int i=30;i>=0;i--)
	{
		int u=(s>>i)&1;
		if(!trie[p][u]) trie[p][u]=++idx;
		p=trie[p][u];
	}
}
int find(int s)
{
	int sum=0,p=0;
	for(int i=30;i>=0;i--)
	{
		int u=(s>>i)&1;
		if(trie[p][!u]) 
		{
			sum+=(1<<i);
			u=!u;
		}
		p=trie[p][u];
	}
	return sum;
}
int main()
{
	int maxx=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		insert(a[i]);
	}
	for(int i=1;i<=n;i++) maxx=max(maxx,find(a[i]));
	cout<<maxx;
}

最长异或值路径

思路

直接枚举两个点的异或路径，麻烦且超时.

看上面这张图，我们要求蓝色部分，可以看成红色部分，因为黄色部分会抵消.

这样我们可以求出从根节点到各个节点的异或路径,在从里面任选两个进行$xor$(异或)运算,得到最大.

这就是第二题

代码

#include<bits/stdc++.h>
using namespace std;
int n,trie[3000010][2],a[100010],idx;
vector<pair<int,int>> e[100010];
void dfs(int u,int sum,int father)
{
	a[u]=sum;
	for(int i=0;i<e[u].size();i++)
	{
		if(e[u][i].first==father) continue;
		dfs(e[u][i].first,sum^e[u][i].second,u);
	}
	return;
}
void insert(int s)
{
	int p=0;
	for(int i=30;i>=0;i--)
	{
		int u=(s>>i)&1;
		if(!trie[p][u]) trie[p][u]=++idx;
		p=trie[p][u];
	}
}
int find(int s)
{
	int sum=0,p=0;
	for(int i=30;i>=0;i--)
	{
		int u=(s>>i)&1;
		if(trie[p][!u]) 
		{
			sum+=(1<<i);
			u=!u;
		}
		p=trie[p][u];
	}
	return sum;
}
int main()
{
	int maxx=0;
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int x,y,w;
		cin>>x>>y>>w;
		e[x].push_back(make_pair(y,w));
		e[y].push_back(make_pair(x,w));
	}
	dfs(0,0,-1);
	for(int i=1;i<=n;i++) insert(a[i]);
	for(int i=1;i<=n;i++) maxx=max(maxx,find(a[i]));
	cout<<maxx;
}

电话列表

思路

将电话号码按字典序排序.在每次插入时,看有没有到一个电话号码的末尾

小贴士 要记得重置数组

代码

#include<bits/stdc++.h>
using namespace std;
int t,n,trie[100010][11],cnt[100010],idx;
int insert(string s)
{
	int p=0,flag2=0;
	for(int i=0;i<s.size();i++)
	{
		if(!trie[p][s[i]-'0']) trie[p][s[i]-'0']=++idx;
		p=trie[p][s[i]-'0'];
		if(cnt[p]) flag2=1;
	}
	cnt[p]++;
	return flag2;
}
int main()
{
	cin>>t;
	while(t--)
	{
		memset(trie,0,sizeof trie);
		memset(cnt,0,sizeof cnt);
		idx=0;
		int flag2=1;
		cin>>n;
		string s[100010];
		for(int i=1;i<=n;i++) cin>>s[i];
		sort(s+1,s+n+1);
		for(int i=1;i<=n;i++) if(insert(s[i])) flag2=0;
		if(flag2) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	
}