一、字典树835. Trie字符串统计以每个字母为节点根节点为空在最后一个字母做标记表示到这结束有一个单词。//每次都从第一个结点开始遍历 int p0; for(int i0;str[i];i){ //用数字025代表az int usrt[i]-a; //判断这个结点是否存在这个字母如果不存在的话新创一个结点存储该字母 //p表示的是第几个结点u表示的是哪个字母如果s[p][u]不为空就证明有以这个字母为值的子结点 //它代表的值就是指向了该子结点即说明了第几个结点是它的子结点 //如s[2][1]3表示结点2有一个值为b第二个数字代表的是az的子结点是结点3 if(!son[p][u]) son[p][u]idx; //令p指向子结点 pson[p][u]; } //以这个结点为末尾的字符串次数加1 cnt[p];#include bits/stdc.h using namespace std; const int N 100010; //son 用来记录每个节点最多有26个英文字母分支。 //cnt[N]表示p节点结尾的单词数量idx记录插入的第几个 //0为根节点和空节点一定要idx; int son[N][26], cnt[N], idx; char str[N]; void insert(char str[N]){ int p0; for(int i0; str[i]; i){ int u str[i] -a; if(!son[p][u]) son[p][u] idx; p son[p][u]; } cnt[p]; } int query(char str[N]){ int p 0; for(int i0; str[i]; i){ int u str[i] - a; if(!son[p][u]) return 0; p son[p][u]; } return cnt[p];//没有以p结尾的节点输出0 } int main(){ ios::sync_with_stdio(false); // nullptr空指针 cin.tie(nullptr); int n; cin n; while(n--){ char op; cin op str; if(op I) insert(str); else cout query endl; } return 0; }143. 最大异或对需要从最高位开始异或最高位为1时数是最大的#include bits/stdc.h using namespace std; const int N 100010, M31*N; int a[N], son[M][2], idx; //这次不需要cnt[N],因为这次是从最高位开始一直走到最低为 void insert(int b){ int p 0; for(int i30; i0; i--){ int u b i 1; //int u a[i] i 1 ,求出a的二进制第i 位 if(!son[p][u]) son[p][u] idx; p son[p][u]; } } int query(int b){ int p 0, res 0; for(int i 30; i0; i--){ int u b i 1; if(son[p][!u]){ p son[p][!u]; res res*2 !u; //res res*2 !u;因这是高位相当于左移一位低位补上刚加的 }else{ p son[p][u]; //没有每位都完全不同的 但走到这高位已经是最优解可以直接往下走 res res*2 u; } } return res; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; for(int i0; in; i) cin a[i]; int res 0; for(int i0; in; i){ insert(a[i]); int tem query(a[i]); //query 返回的是找到的是与当前数组异或的最大数需要^异或 res max(tem^a[i], res); } cout res; return 0; }二、并查集、路径压缩836. 合并集合#include bits/stdc.h using namespace std; const int N 100010; int p[N]; int find(int x){//返回集合的祖宗节点并进行路径压缩 if(p[x] ! x) p[x]find(p[x]); return p[x]; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; for(int i1; in; i) p[i] i; // n个数编号是 1n,最开始每个数各自在一个集合中 while(m--){ char op; int a, b; cin op a b; if(op M) p[find(a)] p[find(b)]; else if(op Q){ if(find(a) ! find(b)) puts(No); else puts(Yes); } } return 0; }240. 食物链解题思路题中所给的所有数字都只被归为3类只存在三种关系。可以将这些节点都放入一棵树中用这些节点与根节点之间的距离%3来表示关系。//用并查集来维护额外信息d[] //此外在运用“并查集”解题时要注意并查集中每个集合时一个树的形式 #includeiostream using namespace std; const int N5*1e410; int n,m; //father数组辅助数组-维护i节点到根节点的距离因为初始每个节点都为根节点所以距离初始都为0 int p[N],d[N]; //路径的长度高度是需要自上而下加起来的从根节点往下走,所以要先调用递归 int find(int x){ if(p[x]!x){ int tfind(p[x]);//t暂时存p[x]“根”节点 d[x]d[p[x]]; //find之后p[x]存放p[x]到根节点之间的距离了原d[x]为x到父节点之间的距离 //路劲压缩优化 p[x]t; } return p[x]; } //此题 //不管是否为同类还是异类都把他放在同一集合中 即只要知道了两个动物的关系就把他们放在集合里面去。这样就可以间接得出各动物之间的关系 //核心如何确定每个点之间的关系》如何确定每个点与根节点之间的关系 //通过到根节点模上3的距离来判断1表示可以吃根节点2表示被根节点吃3表示与根节点是同类 int main(){ cinnm; for(int i1;in;i) p[i]i; int res0; while(m--){ int r,x,y; //r标识说法的种类 cinrxy; if(xn||yn) //三大“假条件”之二 res; else{ int pxfind(x),pyfind(y); //px和py都是根节点 //r1表示x和y是同类 if(r1){ //pxpy说明x和y已经在同一颗树上了 //x和y若是同一种类则他们到根节点的距离模3应该相等 if(pxpy (d[x]-d[y])%3) res; else if(px!py){ //让x的祖宗节点指向y的祖宗节点 p[px]py; //定义px到py之间的距离因为x和y是同类所以x合并到y的集合中后(d[x]?)%3d[y]%3 d[y]-d[x]?,其中为x的祖宗节点px到y的祖宗节点的距离 d[px]d[y]-d[x]; } //r2表示x吃y // 》x到根节点的距离比y到根节点的距离多1 》(d[x]-d[y]-1)%30 }else if(r2){ if(pxpy (d[x]-d[y]-1)%3) res; else if(px!py){ //x和y不在同一集合中 p[px]py; //因为x吃y所以d[x]?-d[y]-10 ?d[y]1-d[x],其中为d[px] d[px]d[y]1-d[x];//d[x]数组存入数据 } } } } coutres; return 0; }三、堆839. 模拟堆这题可以利用map映射的红黑数排出有序时间复杂度很低来做暴力也只是用来复习一下map数组map数据用来将插入的数据排序cnt[x]val用来记录插入x的顺序#include bits/stdc.h using namespace std; const int N100010; mapint, int cnt; vectorint val; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; while(n--){ string op; int k, x; cin op; if(op I){ cin x; cnt[x]; val.push_back(x); } else if(op PM){ cout cnt.begin()-first endl; }else if(op DM){ auto it cnt.begin(); if(--it-second 0) cnt.erase(it); //-- 的优先级比it-second 低所以是先找出数据后 “--” }else if(op D){ cin k; k--; x val[k]; if(--cnt[x] 0) cnt.erase(x); }else if(op C){ cin k x; k--; int tem val[k]; if(--cnt[tem] 0) cnt.erase(tem); val[k] x; cnt[x]; } } return 0; }堆的做法#include bits/stdc.h using namespace std; const int N100010; int h[N], ph[N], hp[N], siz; //ph[m]siz; //hp[siz]m; void heap_swap(int a, int b) { //printf(------9\n); swap(ph[hp[a]], ph[hp[b]]); swap(hp[a], hp[b]);//不能先交换 swap(h[a], h[b]); } void down(int u) { int tu; { //printf(------9\n); if(u*2 siz h[u*2] h[t] ) tu*2; if(u*21 siz h[u*21] h[t]) tu*21; if(u ! t) { heap_swap(u, t); down(t); } } } void up(int u) { while(u/2 0 h[u] h[u/2]) { heap_swap(u, u/2); u/2; } } int main() { int n, m; cin n; m0;//第 k 个数 siz0; while(n--) { string op; cin op; if(op I) { int x; cin x; m; siz; ph[m]siz; hp[siz]m; h[siz]x; up(siz); } else if (op PM) { cout h[1] endl; } else if (op DM) { heap_swap(1, siz); siz--; down(1); } else if (op D) { //printf(1\n); int k; cin k; kph[k]; heap_swap(k, siz); siz--; down(k); up(k); } else { int k; int x; cin k x; kph[k]; h[k]x; down(k); up(k); } } return 0; }堆排序#include bits/stdc.h using namespace std; const int N100010; int q[N]; int main() { int n, m; cin n m; for(int i0; in; i) cin q[i]; //scanf(%d, q[i]); sort(q, qn); for(int i0; im; i) cout q[i] ; //printf(%d , q[i]); return 0; }四、哈希表AcWing 840. 模拟散列表使用哈希表时N取值范围是两到三倍还要设置一个取不到的数作为判定 h[k]是否为空nullmemset(h, 0x3f, sizeof(h));memset 必须有sizeof因为memset是按照字节填充的#include bits/stdc.h using namespace std; const int N 300010, null 0x3f3f3f3f;//刚好比1e9大一些防止相加溢出 //使用哈希表时N要是取值范围的两到三倍 //还要设置一个取不到的数作为判定 h[k]是否为空 int h[N]; int find(int x){ int k (x%N N)%N;//防止 x 为负数 while(h[k] ! null h[k] ! x){ k; if(k N) k0; } return k; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; // cout 1; // memset(h, 0x3f, sizeof(h)); //memset 必须有sizeof因为memset是按照字节填充的 for(int i0; iN ; i) h[i] null;//不能写n,这样哈希表的还有最少一半还是0 while(n--){ char op; int x; cin op x; int k find(x); if(op I) { h[k] x; }else if(op Q){ if(h[k] null) puts(No); else puts(Yes); } } return 0; }841. 字符串哈希字符串哈希可以将字符设置成一串p进制的数字。哈希的过程字符不能映射为p进制的0因为如果A是0AA、AAA、的十进制都会变成0。求两个字符串之间是否先相等只需要求哈希值即可区间求哈希值的公式是h[R]- h[L-1]*p^(R-L1)。#include bits/stdc.h using namespace std; typedef unsigned long long ULL; //这里相当于将Q 2^64, 每一次定义取模因为64位二进制最大2^64-1; const int N100010, P 131;// p 131 ||13331 ULL h[N], p[N]; char str[N]; ULL get(int l, int r){ return h[r]- h[l-1]*p[r-l1]; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m str1; p[0] 1; //存储的是每一位i的P就进制权重 for(int i1; in; i){ p[i] p[i-1]*P; h[i] h[i-1]*P str[i];//将字符串数字化 //这个时候哈希数组就已经%了 } // coutstr1; while(m--){ int l1, r1, l2, r2; cin l1 r1 l2 r2; if(get(l1, r1) get(l2, r2)) puts(Yes); else puts(No); } return 0; }