ACwing 142.前缀统计 143.最大异或对

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e6+10; int trie[maxn][26],tot = 1,End[maxn]; void insert(char *str) { int len = strlen(str), p = 1; for(int i=0;i<len;i++) { int ch = str[i]-'a'; if(trie[p][ch] == 0) trie[p][ch] = ++tot; p = trie[p][ch]; } End[p]++; } int search(char *str) { int len = strlen(str), p = 1, ans = 0; for(int i=0;i<len;i++) { p = trie[p][str[i]-'a']; if(!p) return ans; ans+=End[p]; } return ans; } int main() { int n,m; cin>>n>>m; char str[maxn]; for(int i=1;i<=n;i++) { scanf("%s",str); insert(str); } for(int i=1;i<=m;i++) { scanf("%s",str); cout<<search(str)<<endl; } }

Trie树

思路：

有插入和查找两个操作函数，字符串快速检索的多叉树。 从根节点往下遍历，选择满足条件的树枝方向继续往下，直至叶子节点或字符串结束节点。最大异或对则将整型转化为32位的二进制数插入Trie树，然后根据异或的性质遍历相反的枝，没有就往相同的方向，遍历所有数取max就能得到最大值。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e6+10; int trie[maxn*31][2],tot,a[maxn]; void insert(int x) { int p = 0; for(int i=30;i>=0;i--) { int u = x>>i&1; if(trie[p][u] == 0) trie[p][u] = ++tot; p = trie[p][u]; } } int search(int x) { int p = 0,res = 0; for(int i=30;i>=0;i--) { int u = x>>i&1; if(trie[p][!u]) {//如果有相反的 p = trie[p][!u]; res = res*2+1; } else {//没有继续走相同的 p = trie[p][u]; res = res*2; } } return res; } int main() { int n; cin>>n; for(int i=0;i<n;i++) { cin>>a[i]; insert(a[i]); } int ans = 0; for(int i=0;i<n;i++) { ans = max(ans,search(a[i])); } cout<<ans<<endl; }