基础算法模板

数据结构

单链表的插入删除

const int N=1e6+10;
int head,e[N],ne[N],idx;
//head 存储头节点的下标
//idx  存储当前已经用到的那个点
void init()
{head=-1;idx=0;
}
void add_to_head(int x)//插入头节点操作
{e[idx]=x;ne[idx]=head;head=idx;idx++;
}
void add(int k)//将x插入到下表是k的点后面
{e[idx]=k;ne[idx]=ne[k];ne[k]=idx;idx++;
}//删除操作
//将下标k后面的一个点删掉
void remove(int x)
{ne[k]=ne[ne[k]];
}

模拟栈

const int N=100010;
int n,m;
int stv[N],tt;
int main()
{scanf("%d",&m);while(m--){string op;int x;cin>>op;if(op=="push"){scanf("%d",&x);stv[++tt]=x;}else if(op=="pop")tt--;else if(op=="empty"){if(tt==0)printf("YES\n");else printf("NO\n");}else printf("%d\n",stv[tt]);}return 0;
}

模拟队列

const int N = 100010;int m;
int q[N], hh, tt = -1;int main()
{cin >> m;while (m -- ){string op;int x;cin >> op;if (op == "push"){cin >> x;q[ ++ tt] = x;}else if (op == "pop") hh ++ ;else if (op == "empty") cout << (hh <= tt ? "NO" : "YES") << endl;else cout << q[hh] << endl;}return 0;
}

trie字符串统计

#include<iostream>
using namespace std;
const int N=1e6+10;
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;else p=son[p][u];}return cnt[p];
}
int main()
{int n;cin>>n;while(n--){char op[2];cin>>op>>str;if(*op=='I')insert(str);else printf("%d\n",query(str));}return 0;
}

并查集

1.将两个集合合并

2.询问两个元素是否在一个集合中

基本原理：每个集合用一个树来表示，树根的编号就是在整个集合的编号。每个节点存储它的父节点，p[x]表示x的父节点

问题一：如何判断树根if（p[x]==x)

问题二：如何求x的集合编号while(p[x]!=x)x=p[x];

问题三：如何合并两个集合:p[x]是x的集合编号p[y]是y的集合编号，p[x]=y；

优化 路径压缩

#include<iostream>
using namespace std;
const int N=100100;
int p[N];
int n,m;
int find(int x)//返回X的祖宗节点+路径压缩 
{if(p[x]!=x)p[x]=find(p[x]);return p[x];
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){p[i]=i;}while(m--){char op[2];int a,b;scanf("%s%d%d",op,&a,&b);if(op[0]=='M')p[find(a)]=find(b);//a的祖宗节点插入到B的父节点else{if(find(a)==find(b))puts("Yes");else puts("No");}}
}

堆

1.插入一个数

2.求集合的最小值

3.删除最小值

4.删除任意一个元素

5.修改任意一个元素

堆的一个基本结构：一棵二叉树（完全（除了最后一层节点，上面所有节点都是满的，最后一层从左到右排列））

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e6+10;
int n,m;
int h[N],cnt;
void down(int u)
{int t=u;if(u*2<=cnt && h[u*2]<h[t])t=u*2;if(u*2+1<=cnt&&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],h[u/2]);u/=2;}
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)cin>>h[i];cnt=n;for(int i=n/2;i>=1;i--){down(i);}while(m--){printf("%d ",h[1]);h[1]=h[cnt];cnt--;down(1);}return 0;
}

hash表 哈希表

存储结构和字符串哈希的方式

存储结构：开放寻值法 拉链法

作用：把一个庞大的空间映射到比较小的空间

（1）拉链法，开一个一维数组

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100003;
int h[N],e[N],ne[N],idx;
void insert(int x)
{int k=(x%N+N)%N;e[idx]=x;ne[idx]=h[k];h[k]=idx++;}
bool find(int x)
{int k=(x%N+N)%N;for(int i=h[k];i!=-1;i=ne[i])if(e[i]==x)return true;return false;
}
int main()
{int n;cin>>n;memset(h, -1, sizeof h);while(n--){char op[2];int x;scanf("%s%d",op,&x);if(*op=='I')insert(x);else {if(find(x))printf("Yes\n");else printf("No\n");}}return 0;
}

2.开放寻值法

#include <cstring>
#include <iostream>using namespace std;const int N = 200003, null = 0x3f3f3f3f;int h[N];int find(int x)
{int t = (x % N + N) % N;while (h[t] != null && h[t] != x){t ++ ;if (t == N) t = 0;}return t;
}int main()
{memset(h, 0x3f, sizeof h);int n;scanf("%d", &n);while (n -- ){char op[2];int x;scanf("%s%d", op, &x);if (*op == 'I') h[find(x)] = x;else{if (h[find(x)] == null) puts("No");else puts("Yes");}}return 0;
}

3.字符串哈希

#include <iostream>
#include <algorithm>using namespace std;typedef unsigned long long ULL;const int N = 100010, P = 131;int n, m;
char str[N];
ULL h[N], p[N];ULL get(int l, int r)
{return h[r] - h[l - 1] * p[r - l + 1];
}int main()
{scanf("%d%d", &n, &m);scanf("%s", str + 1);p[0] = 1;for (int i = 1; i <= n; i ++ ){h[i] = h[i - 1] * P + str[i];p[i] = p[i - 1] * P;}while (m -- ){int l1, r1, l2, r2;scanf("%d%d%d%d", &l1, &r1, &l2, &r2);if (get(l1, r1) == get(l2, r2)) puts("Yes");else puts("No");}return 0;
}

---

C++STL

vector, 变长数组，倍增的思想size()  返回元素个数empty()  返回是否为空clear()  清空       front()/back()push_back()/pop_back()begin()/end()[] 支持比较运算，按字典序pair<int, int>first, 第一个元素second, 第二个元素支持比