算法知识补充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;
}