Trie查询与插入
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;struct Trie{int c[26];//孩子int co;//对应字母为结尾的计数器
} T[100100];int idx = 0;void init(){T[idx].co = 0;for (int i = 0; i < 26; i ++ ){T[idx].c[i]=-1;}idx++;//初始化头节点
}void insert(string s){int p = 0;int now = 0;for(char x:s){now = x -'a';if(T[p].c[now]==-1){//如果不存在for (int i = 0; i < 26; i ++ ){T[idx].c[i]=-1;}//初始化新的节点 T[idx].co = 0;//清零新的coT[p].c[now] = idx++;//记录新节点}p = T[p].c[now];//移动到下一个节点}T[p].co++;//记录增加的
}void query(string s){int p = 0;int now = 0;for(char x:s){now = x - 'a';p = T[p].c[now];if(p==-1){cout << 0 << endl;return;};}cout << T[p].co << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);int n;char op;string work;cin >> n;init();while (n -- ){cin >> op >> work;if(op=='I'){insert(work);}else if(op=='Q'){query(work);}}return 0;
}最大xor对
这个和上一个类似，只不过先是插入，然后查找。查找是查找1-bit比如我是0就找1,这样保证最大化xor。然后需要一些位运算，(x>>i)&1就是获取第i位，1>>i就是加上i是1其他是0的。然后获取最大值即可。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;struct Trie{int c[2];//0或者1
} T[4000000];//这个要很大不然会错误int idx = 0;
int res = 0;void init(){T[idx].c[0] = T[idx].c[1] = -1;idx++;
}void insert(int x){int now = 0;int p = 0;for (int i = 30; i >= 0; i -- ){now = (x >> i) & 1;//提取对应的位的bit//先计入if(T[p].c[now]==-1){T[idx].c[0] = T[idx].c[1] = -1;T[p].c[now] = idx++;}p = T[p].c[now];}
}void query(int x){int now = 0;int h = 0;int p =0;int tres = 0;for (int i = 30; i >= 0; i-- ){now = (x >> i) & 1;//提取对应的位的bit//获得期望的另一个h = 1-now;if(T[p].c[h]==-1){p = T[p].c[now];}else{p = T[p].c[h];tres += 1 << i;}} res = max(res,tres);
}int main()
{ios::sync_with_stdio(false);cin.tie(0);init();int n;cin >> n;int x;for (int i = 0; i < n; i ++ ){cin >> x;insert(x);//插入query(x);//查找最大异或}cout << res << endl;return 0;
}