Trie 树是一种多叉树的结构，每个节点保存一个字符，一条路径表示一个字符串。
Trie字符串统计
维护一个字符串集合，支持两种操作：
I x向集合中插入一个字符串 x；Q x询问一个字符串在集合中出现了多少次。
共有 N 个操作，所有输入的字符串总长度不超过 10^5，字符串仅包含小写英文字母。
输入格式
第一行包含整数 N，表示操作数。
接下来 N 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。
输出格式
对于每个询问指令 Q x，都要输出一个整数作为结果，表示 x 在集合中出现的次数。
每个结果占一行。
数据范围
1≤N≤2∗10^4
输入样例：
5
I abc
Q abc
Q ab
I ab
Q ab
输出样例：
1
0
1#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int son[N][26];//Tire 树本身
int cnt[N];//cnt[x] 表示：以 编号为 x 为结尾的字符串的个数
int idx;//各个节点的编号 根节点的编号为0
int n;
void insert(string s)
{
int p=0;//从根节点开始寻找
for(int i=0;i<s.size();i++)
{
int t=s[i]-'a';
//判断这个结点是否存在这个字母，如果不存在的话，新创一个结点存储该字母
//p表示的是第几个结点，u表示的是哪个字母，如果s[p][u]不为空就证明有以这个字母为值的子结点
//它代表的值就是指向了该子结点，即说明了第几个结点是它的子结点
//如s[2][1]=3，表示结点2有一个值为b（第二个数字代表的是a～z）的子结点，是结点3
if(!son[p][t])
{
idx++;
son[p][t]=idx;
}
//令p指向子结点
p=son[p][t];
}
//以这个结点为末尾的字符串次数加1
cnt[p]++;//每个节点都对应一个唯一的idx,然后通过那个idx来统计次数
}
int query(string s)
{
int p=0;
for(int i=0;i<s.size();i++)
{
int t=s[i]-'a';
//如果走不通了，即树中没有保存当前字符
//则说明树中不存在该字符串
if(!son[p][t]) return 0;
//指向下一个节点
p=son[p][t];
}
//循环结束的时候，p 等于字符串 s 的尾字符所对应的 idx
// cnt[p] 就是字符串 s 出现的次数
return cnt[p];
}
int main()
{
cin>>n;
while(n--)
{
char op;cin>>op;
string s;cin>>s;
if(op=='I') insert(s);
else cout<<query(s)<<endl;
}
return 0;
}最大异或对
在给定的 N 个整数 A1，A2……AN 中选出两个进行 xor（异或）运算，得到的结果最大是多少？
输入格式
第一行输入一个整数 N。
第二行输入 N 个整数 A1～AN。
输出格式
输出一个整数表示答案。
数据范围
1≤N≤10^5
0≤Ai<2^31
输入样例：
3
1 2 3
输出样例：
3
查询函数做的是对A[i]在A[1]-A[i-1] 题解里是先插入A[i]所以实际上是A[1]到A[i]，但A[i]肯定不会走
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10,M=31*N;
int son[M][2];
int a[N];
int idx;
void insert(int x)
{
int p=0;//初始化指向根节点
//从最高位开始，依次取出每一位
for(int i=31;i>=0;i--)
{
int u=(x>>i)&1;//取X的第i位的二进制数是什么
//如果树中不能走到当前数字
//为当前数字创建新的节点，保存该数字
if(!son[p][u])
{
idx++;
son[p][u]=idx;
}
p=son[p][u];//指针指向下一层
}
}
int query(int x)
{
int res=0; // 保存与 x 异或结果最大的那个数
int p=0;//指向根节点
for(int i=31;i>=0;i--) ///从最高位开始找
{
int u=(x>>i)&1;
//如果树中能走到 !u，就走到!u
if(son[p][!u])
{
p=son[p][!u];
res=res*2+1;
}
//没有!u，就只能走到u了
else
{
p=son[p][u];
res=res*2+0;
}
}
return res;
}
int main()
{
int n;cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int res=0;
/*
相当于
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
{
两层循环的感觉
}
}
先插入后查找 后面查找的数会更新如果当前这个数最合适的数在后面
*/
for(int i=1;i<=n;i++)
{
insert(a[i]);
int num=query(a[i]);
res=max(res,num);
}
cout<<res<<endl;
return 0;
}异或和之差(蓝桥杯)
题目描述
给定一个含有 n 个元素的数组 Ai，你可以选择两个不相交的子段。求出这两个子段内的数的异或和的差值的最大值。
输入格式
输入的第一行包含一个整数 n 。
第二行包含 n 个整数 Ai ，相邻整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
样例输入
6
1 2 4 9 2 7
样例输出
14
提示
两个子段可以分别选 1 和 4，9，2，差值为 15 − 1 = 14 。
对于 40% 的评测用例，n ≤ 5000 ；
对于所有评测用例，2 ≤ n ≤ 2 × 10^5，0 ≤ Ai ≤ 2^20 。
#include<iostream>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int N=2e5+10,M=N*21;
int son[M][2];//Tire树本身
int a[N],s[N];
//这四个数组的作用：因为题目中限制了 必须是两个不相交的字集 所以用来限制你所选的最大区间和最小区间没有交叉
int lmx[N],lmi[N];//[l,n]区间内异或的最大值或最小值
int rmx[N],rmi[N];//[1,r]区间内的最大值或最小值
int idx;
void insert(int x)
{
int p=0;
for(int i=20;i>=0;i--)
{
int u=(x>>i)&1;
if(!son[p][u])
{
idx++;
son[p][u]=idx;
}
p=son[p][u];
}
}
int query_max(int x)
{
int p=0;
int res=0;
for(int i=20;i>=0;i--)
{
int u=(x>>i)&1;
if(son[p][!u])
{
res=res*2+1;
p=son[p][!u];
}
else
{
res=res*2+0;
p=son[p][u];
}
}
return res;
}
int query_min(int x)
{
int p=0;
int res=0;
for(int i=20;i>=0;i--)
{
int u=(x>>i)&1;
if(son[p][u])
{
res=res*2+0;
p=son[p][u];
}
else
{
res=res*2+1;
p=son[p][!u];
}
}
return res;
}
signed main()
{
int n;cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
s[i]=a[i]^s[i-1];
}
memset(rmx,0,sizeof rmx);
memset(rmi,0x3f,sizeof rmi);
insert(0);//前缀和 s0^s1=s1
//不能先插入在查询 那样的话本来应该查询(1~i-1)这样就变成了(1-i)那么此时最大肯定不会走i的那条完整的路 但是最小可以
//最小一直沿着i的那条路走 可以得到0
//从左往右构造子树
for(int i=1;i<=n;i++)
{
rmx[i]=max(rmx[i-1],query_max(s[i]));
rmi[i]=min(rmi[i-1],query_min(s[i]));
insert(s[i]);
}
//重新构造子树 从右往左构造
memset(son,0,sizeof son);
idx=0;
memset(lmx,0,sizeof lmx);
memset(lmi,0x3f,sizeof lmi);
insert(0);
for(int i=n;i>=1;i--)
{
lmx[i]=max(lmx[i+1],query_max(s[i]));
lmi[i]=min(lmi[i+1],query_min(s[i]));
insert(s[i]);
}
int ans=0;
for(int i=1;i<=n;i++)
{
ans=max(ans,rmx[i]-lmi[i+1]);
ans=max(ans,lmx[i]-rmi[i-1]);
}
cout<<ans<<endl;
return 0;
}
