算法知识补充2

一部分：Tire树：高效地存储和查找字符串集合的数据结构acwing835

#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int son[N][26],cnt[N],idx;
char str[N];
void insert(char str[]){int p=0;for(int i=0;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[]){int p=0;for(int i=0;str[i];i++){int u=str[i]-'a';if(!son[p][u])return 0;p=son[p][u];}return cnt[p];
}
int main(){int n;cin>>n;while(n--){char op[2];cin>>op>>str;if(op[0]=='I')insert(str);else cout<<query(str)<<endl;}return 0;
}

acwing143

二部分：并查集：1合并集合 2询问两个元素是否在一个集合acwing836

#include<iostream>
using namespace std;
const int N=100010;
int f[N];
int n,m;
int find(int x){//返回x的祖宗节点+路径压缩优化 if(f[x]!=x) f[x]=find(f[x]);return f[x];
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++)f[i]=i;while(m--){char op[2];int a,b;cin>>op;cin>>a>>b;if(op[0]=='M')f[find(a)]=find(b);else{if(find(a)==find(b))cout<<"Yes"<<endl;else cout<<"No"<<endl;}}
}

acwing837

#include<iostream>
using namespace std;
const int N=100010;
int f[N],size[N];
int n,m;
int find(int x){//返回x的祖宗节点+路径压缩优化 if(f[x]!=x) f[x]=find(f[x]);return f[x];
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++){f[i]=i;size[i]=1;}while(m--){char op[5];int a,b;cin>>op;if(op[0]=='C'){cin>>a>>b;if(find(a)==find(b))continue;size[find(b)]+=size[find(a)];f[find(a)]=find(b);}else if(op[1]=='1'){cin>>a>>b;if(find(a)==find(b))cout<<"Yes"<<endl;else cout<<"No"<<endl;}else {cin>>a;cout<<size[find(a)]<<endl;}}return 0;
}

acwing240

#include<iostream>
using namespace std;
const int N=50010;
int n,m;
int f[N],d[N];
int find(int x){if(f[x]!=x){int t=find(f[x]);d[x]+=d[f[x]];f[x]=t;}return f[x];
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++)f[i]=i;int t,x,y;int res=0;while(m--){cin>>t>>x>>y;if(x>n||y>n)res++;else{int fx=find(x),fy=find(y);if(t==1){if(fx==fy&&(d[x]-d[y])%3)res++;else if(fx!=fy){f[fx]=fy;d[fx]=d[y]-d[x];}}else{if(fx==fy&&(d[x]-d[y]-1)%3)res++;else if(fx!=fy){f[fx]=fy;d[fx]=d[y]+1-d[x];}}}}cout<<res<<endl;return 0;
}

三部分：手写堆

#include<iostream>
using namespace std;
const int N=100010;
int n,m;
int h[N],size;
void down(int u){int t=u;if(u*2<=size&&h[u*2]<h[t])t=u*2;if(u*2+1<=size&&h[u*2+1]<h[t])t=u*2+1;if(u!=t){swap(h[u],h[t]);down(t);}
}
void up(int u){while(u/2&&h[u/2]>h[u]){swap(h[u/2],h[u]);u/=2;}
}
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>h[i];size=n;for(int i=n/2;i;i--)down(i);while(m--){cout<<h[1]<<" ";h[1]=h[size];size--;down(1);}return 0;
}

 acwing839

#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int n,m;
int h[N],hp[N],ph[N],size;//hp[k]表示k存的数组位置的下标i,ph[i]指这个下标在数组的位置 
void heap_swap(int a,int b){swap(ph[hp[a]],ph[hp[b]]);swap(hp[a],hp[b]);swap(h[a],h[b]);
}
void down(int u){int t=u;if(u*2<=size&&h[u*2]<h[t])t=u*2;if(u*2+1<=size&&h[u*2+1]<h[t])t=u*2+1;if(u!=t){heap_swap(u,t);down(t);}
}
void up(int u){while(u/2&&h[u/2]>h[u]){heap_swap(u/2,u);u/=2;}
}
int main(){cin>>n;while(n--){char op[10];int k,x;cin>>op;if(!strcmp(op,"I")){cin>>x;size++;m++;//记录第几次插入 ph[m]=size,hp[size]=m;//每次插入都是在堆尾插入 h[size]=x;//记录插入的值 up(size);}else if(!strcmp(op,"PM"))cout<<h[1]<<endl;else if(!strcmp(op,"DM")){heap_swap(1,size);size--;down(1);}else if(!strcmp(op,"D")){cin>>k;k=ph[k];//保存当前被删除节点的下标 heap_swap(k,size);//第m个插入的元素移到了堆尾，此时ph[m]指向堆尾 size--;//删除堆尾 down(k)；up(k);//k是之前记录被删除的节点的下标 }else {cin>>k>>x;k=ph[k];h[k]=x;down(k),up(k);}}return 0;
}