数学
判断素数
bool isprime(int x){
if(x<2) return false;
for(int i=2;i<=x/i;i++) if(x%i==0) return false;
return true;
}
找质因数
void divide(int x){
for(int i=2;i<=x/i;i++){
if(x%i==0){
int s = 0;
while(x%i==0) x/=i,s++;
//处理后i就是底数，s是指数
}
}
if(x>1) cout<<x<<' '<<1<<endl; //此时x是唯一大于根号x的质因数，他的指数是1
}
素数筛
bool st[N]; //标记是否为合数
int primes[N];
int cnt;
void get_primes(int x){
for(int i=2;i<=x;i++){
if(!st[i]) primes[cnt++] = i;
for(int j=0;primes[j]<=x/i;j++){
st[primes[j]*i]=true;
if(i%primes[j]==0) break;
}
}
}
图
邻接表
int h[N],e[N],ne[N],idx;
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
拓扑排序
int q[N],d[N]; //bfs实现，d是表示结点入度
bool toposort(){
int hh=0,tt=-1; //这里由于要把入度为0的点先压入队列，没有初始化对头，tt为-1
for(int i=1;i<=n;i++) //结点1~n中找入度为0的
if(!d[i]) q[++tt] = i;
while(hh<=tt){
int t = q[hh++];
for(int i=h[t];~i;i=ne[i]){
int j = e[i];
if(--d[i]==0) q[++tt] = j;
}
}
return tt==n-1; //如果都入队了，说明存在拓扑序，无环
}
Dijkstra
朴素
int dist[N],g[N][N]; //结点1~N，邻接矩阵实现
bool st[N],pre[N]; //判断是否在集合中，最短路的上一个节点
void dijkstra(int S){ //起点S
memset(dist,0x3f,sizeof dist);
memset(st,false,sizeof st);
dist[S] = 0;
for(int i=0;i<n;i++){
int t = -1;
for(int j=1;j<=n;j++){
if(!st[j]&&(t==-1||dist[j]<dist[t]))
t=j;
}
st[t]=true;
for(int j=1;j<=n;j++){
if(dist[j]>dist[t]+g[t][j]){
dist[j]=dist[t]+g[t][j];
pre[j] = t;
} else if(dist[j]==dist[t]+g[t][j] && ...){ //第二判优条件
...
}
}
}
}
堆优化
#include <queue>
typedef piar<int,int> PII; //节点距离和结点编号
priority_queue<PII,vector<PII>,greater<PII>> heap; //小根堆
int h[N],e[N],ne[N],w[N],idx; //邻接表实现图
int dist[N],pre[N];
bool st[N];
memset(h,-1,sizeof h);
void dijkstra(int S){
heap.clear();
memset(dist,0x3f,sizeof dist);
memset(st,false,sizeof st);
dist[S] = 0;
heap.push({0,S});
while(heap.size()){
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if(st[ver]) continue; //该结点已经在集合中了，直接看下一个
st[ver] = true; //把该结点加入集合
for(int i=h[ver];~i;i=ne[i]){
int j = e[i];
if(dist[j] > distance + w[i]){
dist[j] = distance + w[i];
heap.push({dist[j],j});
pre[j] = ver;
}else if(dist[j]==distance+w[i] && ...){ //第二判优条件
...
}
}
}
}
SPFA
求最短路
int h[N],w[N],e[N],ne[N],idx;
int dist[N],pre[N];
bool st[N]; //判断是否在队列中
memset(h,-1,sizeof h);
void spfa(int S){
queue<int> q; //借助队列实现
memset(dist,0x3f,sizeof dist);
memset(st,false,sizeof st);
dist[S] = 0;
q.push(S);
st[S] = true;
while(q.size()){
int t = q.front();
q.pop();
st[t] = false;
for(int i=h[t];~i;i=ne[i]){
int j = e[i];
if(dist[j]>dist[t]+w[i]){
dist[j]=dist[t]+w[i];
pre[j] = t;
if(!st[j]){ //若j未在队列中，将j插入队列
q.push();
st[j]=true;
}
}else if(dist[j]==dist[t]+w[i] && ...){ //第二判优条件
...
}
}
}
}
判负环
//原理：若某条最短路径上有n个点（不包括自己，包括自己是n+1个），则一定存在环
int dist[N],cnt[N]; //cnt是最短路中经过的点数
bool st[N];
bool spfa(){
queue<int> q;
//无需初始化dist
for(int i=1;i<=n;i++){ //插入1~n个结点
q.push();
st[i] = true;
}
while(q.size()){
int t = q.front();
q.pop();
st[t] = false;
for(int i=h[t];~i;i=ne[i]){
int j = e[i];
if(dist[j]>dist[t]+w[i]){
dist[j]=dist[t]+w[i];
cnt[j]=cnt[t]+1; //路上的点数+1
if(cnt>=n) return true; //若点数>=n,存在负环
if(!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
遍历pre生成路径
#include<vector>
vector<int> path;
for(int i=D;i!=S;i=pre[i]) path.push_back(i); //D终点，S起点
//打印路径
cout<<S; //打印起点
for(int i=path.size()-1;i>=0;i--) cout<<"->"path[i];
cout<<endl;
Floyd
#define INF 0x3f3f3f3f
int g[N][N]; //邻接矩阵，算法结束后，g[a][b]表示结点a到结点b的最短距离
for(int i=1;i<=n;i++) //结点1~n距离初始化
for(int j=1;j<=n;j++)
if(i==j) d[i][j]=0;
else d[i][j] = INF;
void floyd(){
for(int k=1;k<=n;k++) //找中介点k
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j] = min(d[i][j],d[i][k]+d[k][j]);
}
树
BST
插入
int l[N],r[N],v[N],idx; //编号为u的结点对应的左右孩子和值，idx分配结点(相当于地址)
int insert(int &u,int w){
if(!u) u=++idx,v[u]=w; //结点不存在(编号为0)，分配一个
else if(w<=v[u]) insert(l[u],w); //<=还是<根据题目判断
else insert(r[u],w);
}
建立
int root = 0; //根节点编号
for(int i=0;i<n;i++){
int w;
cin>>w;
insert(root,w);
}
删除
// 1、若是叶子结点，直接上
// 2、若只有单边子树，让子树替代删除结点的位置
// 3、若有左右子树，让删除结点的直接后继（右子树的最小值，左子树的最大值）替代自身，转为1、2的情况
AVL
建立
int l[N],r[N],v[N],h[N],idx; //编号u的左孩子，右孩子，结点值，高度，分配结点编号变量
void update(int u){ //调整结点高度,为左右两个孩子的高度的最大值+1
h[u] = max(h[l[u]],h[r[u]])+1;
}
int get_balance(int u) //获取结点平衡因子
{
return h[l[u]]-h[r[u]];
}
int root=0; //根结点编号0
while(n--){
int w;
cin>>w;
insert(root,w);
}
左旋
void L(int &u){
int p = r[u];
r[u]=l[p],l[p]=u;
update(u),update(p);
u=p;
}
右旋
void R(int &u){
int p = l[u];
l[u]=r[p],r[p]=u;
update(u),update(p);
u=p;
}
插入
void insert(int &u,int w){
if(!u) u=++idx,v[u]=w;
else if(w<v[u]){
insert(l[u],w);
//判断旋转
if(get_balance(u)==2){
if(get_balance(l[u])==1) R(u); //LL
else L(l[u]),R(u); //LR
}
}
else{
insert(r[u],w);
//判断旋转
if(get_balance(u)==-2){
if(get_balance(r[u])==-1) L(u);
else R(r[u]),L(u);
}
}
}
堆
基本操作
//上调
void up(int u){
while(u/2&&h[u/2]>h[u]) swap(h[u/2],h[u]),u/=2;
}
//下调
void down(int u){
int t = u;
if(t*2<size && h[u*2]<h[t]) t=u*2;
if(t*2+1<size && h[u*2+1]<h[t]) t=u*2+1;
if(u!=t){
swap(h[u],h[t]);
down(t);
}
}
建立
//O(n)
for(int i=n/2;i;i--) down(i);
插入
h[++size]=x; //插入到最后一个位置，up
up(size);
删除
heap[k] = heap[size--];
up(k),down(k);
若要存储第几个插入的情况：
int h[N],ph[N],hp[N],size; //ph表示第k个插入的位置，hp表示下标对应的点第几个插入
//交换操作
void hswap(int a,int b){
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a],hp[b]);
swap(h[a],h[b]);
}
//然后down和up里面的swap改hswap
并查集
int p[N];
int find(int x){ //路径压缩find
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
for(int i=1;i<=n;i++) p[i]=i; //初始化
int pa=find(a),pb=find(b); //合并a,b集合
if(pa!=pb) p[pa]=pb;
