算法-板子

自己的算法总结

这里是自己的算法总结

基础知识

typedef 需要定义在using下面
#define 需要定义在头文件哪里
能使用全局变量，就使用全局变量

快速幂

long long fastPower(long long base, long long power) {
    long long result = 1;
    while (power > 0) {
        if (power & 1) {//此处等价于if(power%2==1)
            result = result * base % 1000;
        }
        power >>= 1;//此处等价于power=power/2
        base = (base * base) % 1000;
    }
    return result;
}

线性筛

//p是bool数组，如果是0表示是质数
//q用来存放质数
void init(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!p[i]) q[++tot] = i;
        for (int j = 1; q[j] <= n / i; j ++ )
        {
            p[i * q[j]] = true;
            if (i % q[j] == 0) break;
        }
    }
}

欧拉筛

int cnt;
int primes[N];
bool st[N];
//分解质数
void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!st[i])primes[cnt++]=i;
        for(int j=0;primes[j]*i<=n;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0)break;
        }
    }
}

欧几里得算法

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

KMP算法

for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && str[i] != str[j + 1]) j = nxt[j];
    if (str[i] == str[j + 1]) j ++ ;
    nxt[i] = j;
}

safa 算法模板

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 2510,M=6200*2+10;//点数 边数

int n,m,S,T;
//邻接表存储树  存储元素 存储列表的next值 单链表指针
int h[N], e[M], w[M], ne[M], idx;
int q[N], dist[N];//循环队列 距离
bool st[N];//判重数组

void add(int a,int b,int c){//a 指向 b 权重是 c

    //被指的边   权重   多少条出口    边数
    //h[a]=idx++ 代表当前第idx个节点是被a指向的
    //ne[idx]=h[a]  代表 当a指向新节点时，上一个节点是h[a]，然后再更新一下h[a]
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
    
}

void spfa(){
    memset(dist, 0x3f, sizeof dist);//初始化正无穷
    dist[S]=0;//起点处长度是0
    
    int hh=0,tt=1;//循环队列下标
    
    //记录起点   标记
    q[0]=S,st[S]=true;
    
    while(hh!=tt){//循环队列  头部跟尾部不相等即可
        
        int t=q[hh++];//取出来一个
        if(hh==N)hh=0;//如果到末尾了 则置为0
        
        st[t]=false;//取出来了 咱就标记一下
        
        //~i 的意思是i!=-1 
        //i=t的出口数
        for(int i=h[t];~i;i=ne[i]){
            
            int j=e[i];//得到i指向的边
            if(dist[j]>dist[t]+w[i]){//边权判断
                dist[j]=dist[t]+w[i];
                if(!st[j]){
                    q[tt++]=j;
                    if(tt==N)tt=0;
                    st[j]=true;
                }
            }
        }
    }
    
}

int main(){
    
    cin>>n>>m>>S>>T;
    memset(h, -1, sizeof h);
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    
    spfa();
    
    cout<<dist[T]<<endl;
    
    return 0;
}

prim算法模板

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 110;
int w[N][N];
bool st[N];
int dist[N];
int n;
//T. 1140
//连接光纤
int prim(){
    int res=0;
    memset(dist, 0x3f, sizeof dist);
    dist[1]=0;
    
    for (int i = 0; i < n; i ++ ){
        int t=-1;
        //挨个找最小值
        for (int j = 1; j <= n; j ++ )
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
                t=j;
        
        st[t]=true;
        res+=dist[t];
        
        //把t->j这条路全部改为最小值
        for(int j=1;j<=n;j++)    dist[j]=min(dist[j],w[t][j]);
        
    }
    return res;
}

int main(){
    cin>>n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            cin>>w[i][j];
            
    cout<<prim()<<endl;
    
    return 0;
}

线段树

int lowbit(int x){
    return x&-x;//求最低位
}
//第a个数加b
void add(int a,int b){
    for(int i=a;i<=n;i+=lowbit(i))tr[i]+=b;
}
//0~x区间和
int query(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i))res+=tr[i];
    return res;
}

快速排序算法模板

 - 模板题 AcWing 785. 快速排序
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

图论

void add(int a,int b,int c){
    //a 指向b价值是w
    w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

// 遍历邻接表
for(int i=h[u];i!=-1;i=ne[i])

单调队列

# include <iostream>
using namespace std;
const int N = 1000010;
int a[N], q[N], hh, tt = -1;

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; ++ i)
    {
        scanf("%d", &a[i]);
        if (i - k + 1 > q[hh]) ++ hh;                  // 若队首出窗口，hh加1
        while (hh <= tt && a[i] <= a[q[tt]]) -- tt;    // 若队尾不单调，tt减1
        q[++ tt] = i;                                  // 下标加到队尾
        if (i + 1 >= k) printf("%d ", a[q[hh]]);       // 输出结果
    }
    cout << endl;
    hh = 0; tt = -1;                                   // 重置！
    for (int i = 0; i < n; ++ i)
    {
        if (i - k + 1 > q[hh]) ++ hh;
        while (hh <= tt && a[i] >= a[q[tt]]) -- tt;
        q[++ tt] = i;
        if (i + 1 >= k) printf("%d ", a[q[hh]]);
    }
    return 0;
}

二分

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e5+10;
int a[N];
int n,q,tar;

int main(){
    cin>>n>>q;
    for (int i = 0; i < n; i ++ )
        cin>>a[i];

    for(int i=0;i<q;i++){
        cin>>tar;
        int l=0,r=n-1,mid=0;
        //右边二分
        while(l<r){
            mid=(r+l)>>1;
            if(a[mid]>=tar)r=mid;//r不动  l往右边来
            else l=mid+1;
        }
        if(a[l]!=tar){
            printf("-1 -1\n");
            continue;
        }
        int c=l;
        r=n-1;
        mid=0;
        //左边二分
        while(l<r){
            mid=(r+l+1)>>1;
            if(a[mid]<=tar)l=mid;//l不动,r往左边来
            else r=mid-1;
        }
        cout<<c<<' '<<l<<endl;
    }
    return 0;
}

求组合数

LL C(int a,int b){
    LL res=1;
    for(int j=1,i=a;j<=b;i--,j++){
        res=res*i/j;
        if(res>n)return res;
    }
    return res;
}

拓扑排序

void topo_sort() {
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (!in[i]) q.push(i);

    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        L.push_back(t);

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (!--in[j]) q.push(j);
        }
    }
}

完全背包问题每种物品无限使用

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3+10,MOD=1e9;
int f[N];
int n,V;
int main(){
    cin>>n>>V;     //背包容量是V
    f[0]=0;
    while(n--){
        int v,w;
        cin>>v>>w;
        //for(int i=1;i<=n;i*=2)
            for(int j=v;j<=V;j++)
                f[j]=max(f[j],f[j-v]+w);
    }
    cout<<f[V]<<endl;
    return 0;
}

01背包

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1010;
int f[N];
int n,V;
int v,w;

int main(){
    cin>>n>>V;
    for(int i=0;i<n;i++){
        cin>>v>>w;
        for(int j=V;j>=v;j--){
            f[j]=max(f[j],f[j-v]+w);
        }
    }
    
    cout<<f[V]<<endl;
    return 0;
}

例题1模板 - while循环下就是对应着它的性质

#include <bits/stdc++.h>
using namespace std;

const int N = 4e5+10;

int primes[N];

int main(){
	int n;
	cin >> n;
	for(int i = 2; i <= n; i++){
		int t = i, j = 2;
		while(t > 1)
			if(t % j == 0) t /= j, primes[j]++;
			else j++;
	}
	for(int i = 1; i <= 1e4; i++)
		if(primes[i]) cout << i << " " << primes[i] << endl;
	return 0;
}

欧拉线性筛质数

#include <bits/stdc++.h>
using namespace std;

const int N = 110, M = 1e5+10;

int n, cnt;
int nums[N], primes[M];
bool st[M*N];

int main(){
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> nums[i];
	
	for(int i = 2; i <= M; i++){
		if(!st[i]) primes[cnt++] = i;
		for(int j = 0; primes[j] <= M/i; j++){	// 从小到大枚举所有质数
			st[primes[j] * i] = true;			// 只用最小质因子去筛掉合数
			// 说明primes[j]一定是i的最小质因子，则primes[j]页一定是primes[j]*i的最小质因子
			// 如果i%primes[j] != 0 的话，说明primes[j]一定小于i的所有质因子
			if(i % primes[j] == 0) break;
		}
	}
			
	
	for(int i = 1; i <= n; i++)
		if(!st[nums[i]] && nums[i] != 1) cout << nums[i] << " ";
	
	return 0;
}

读取一行

getline(cin,s);

题目介绍：有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。
给出每个人的孩子的信息。
输出一个序列，使得每个人的孩子都比那个人后列出。

拓扑排序

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
const int N = 110,M=N*N/2;
int in[N];
int a[N];
int n;
vector<int>L;

//e 表示的是边  ne表示的是下一个指针    idx表示的是边个数
int h[N],e[M],ne[M],idx;
//使用邻接表存储图
void add(int a,int b){//无权图
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void top_sort(){
    queue<int>q;//使用队列
    //先进行一次遍历，把所有父辈塞进队列
    for (int i = 1; i <= n; i ++ )
        if(!in[i])
            q.push(i);
    //普通的入队出队
    while(q.size()){
        int t=q.front();
        q.pop();
        L.push_back(t);
        //访问邻接表即可
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(!--in[j])q.push(j);
        }
    }
}

int main(){
    cin>>n;
    memset(h, -1, sizeof h);
    
    for (int i = 1; i <= n; i ++ ){
        int x;
        while(cin>>x,x){
            add(i,x);//i与x之间进行连边
            in[x]++;//使用in数组记录x节点的父亲个数
        }
    }
    
    top_sort();//拓扑排序
    
    for(int &i:L)// L数组用于记录结果
        cout<<i<<" ";
    
    return 0;
}

单源最短路 spfa算法

需要注意的：如果起点是任意一个，那么这个点的dist[Start]=0;

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 2510,M=6200*2+10;//点数 边数

int n,m,S,T;
int h[N], e[M], w[M], ne[M], idx;
int q[N], dist[N];//循环队列 距离
bool st[N];//判重数组

void add(int a,int b,int c){//a 指向 b 权重是 c
    //边      权重       多少条出口    出口+1
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

void spfa(){
    memset(dist, 0x3f, sizeof dist);//初始化正无穷
    dist[S]=0;//起点处长度是0
    int hh=0,tt=1;//循环队列下标
    //记录起点   标记
    q[0]=S,st[S]=true;
    while(hh!=tt){//循环队列  头部跟尾部不相等即可
        int t=q[hh++];//取出来一个
        if(hh==N)hh=0;//如果到末尾了 则置为0
        st[t]=false;//标记一下
        //~i 的意思是i!=-1 
        //i=t的出口数    
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];//得到i指向的边
            if(dist[j]>dist[t]+w[i]){//边权判断
                dist[j]=dist[t]+w[i];
                if(!st[j]){
                    q[tt++]=j;
                    if(tt==N)tt=0;
                    st[j]=true;
                }
            }
        }
    }
}

int main(){
    
    cin>>n>>m>>S>>T;
    memset(h, -1, sizeof h);
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    
    spfa();
    
    cout<<dist[T]<<endl;
    
    return 0;
}

自己的算法总结

快速幂

线性筛

欧拉筛

欧几里得算法

KMP算法

safa 算法模板

prim算法模板

线段树

快速排序算法模板

图论

单调队列

二分

求组合数

拓扑排序

完全背包问题 每种物品无限使用

01背包

读取一行

拓扑排序

单源最短路 spfa算法

完全背包问题每种物品无限使用