算法备赛模板（临时）

墨蓝 2024-04-20 07:20 2阅读 0赞

⭐**简单说两句**⭐

> **作者：****后端小知识**
> 
> **CSDN**个人主页：[后端小知识][Link 1]
> 
> 🔎**GZH**：`后端小知识`
> 
> 🎉欢迎关注🔎点赞👍收藏⭐️留言📝

#### 文章目录 ####

*   *  基础算法
     *   *  前缀和
         *  差分
     *  字符串
     *   *  回文字符串
     *  数学
     *   *  快速幂模板
         *  矩阵快速幂
         *  gcd与lcm
         *  闰年判断
         *  质数
         *  组合
         *  卡特兰数
         *  杨辉三角
     *  搜索
     *   *  全排列
         *  组合
         *  迷宫
     *  并查集
     *  图
     *   *  spfa求最短路
     *  动态规划
     *   *  01背包
         *  完全背包
         *  多重背包
         *  分组背包

### 基础算法 ###

**一些技巧算法**

#### 前缀和 ####

#include<bits/stdc++.h>
    #define ll long long 
    #define maxn 1000010
    using namespace std; 
    int sum[maxn]; 
    int main(){
        
    	int n,m;	cin>>n>>m;
    	for(int i=1;i<=n;i++){
        
    		int x;	cin>>x;
    		sum[i]=sum[i-1]+x; 
    	}
    	while(m--){
        
    		int l,r;	cin>>l>>r;
    		cout<<sum[r]-sum[l-1]<<"\n"; 
    	}
    	return 0; 
    }

#### 差分 ####

#include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+10;
    int a[N],b[N];//b数组为差分数组  a 数组是 b 数组的前缀和
    int n,m;
    int main(){
        
        cin.tie(0);
        ios::sync_with_stdio(false);
        cin>>n>>m;
        for(int i=1;i<=n;i++) {
         cin>>a[i]; b[i]=a[i]-a[i-1]; }
        while(m--){
        
            int l,r,c;  cin>>l>>r>>c;
            b[l]+=c; b[r+1]-=c;  //这里一定要记住 要给 b[r+1]减去 c ,
        }
        for(int i=1;i<=n;i++){
        
            a[i]=a[i-1]+b[i]; //求前缀和
            cout<<a[i]<<" ";
        }
        return 0;
    }

### 字符串 ###

#### 回文字符串 ####

#include <bits/stdc++.h>
    using namespace std; 
    int main() {
        
        //freopen("in.txt", "r", stdin);
        //freopen("out.txt", "w", stdout);
        string s;
        cin >> s;
        int n = s.length();
        bool is = true; //bool 类型的值只有 true 和 false
        for (int i = 0; i < n / 2; i++) {
        
            if (s[i] != s[n - 1 - i]) {
        
                is = false;
            }
        }
        cout << (is ? "Yes" : "No") << "\n";
        return 0;
    }

### 数学 ###

前言：

> 求n的因子：从 1到 sqrt(n) 循环判断即可，不需要从 1 到 n

#### 快速幂模板 ####

#include<bits/stdc++.h>
    #define ll long long 
    using namespace std; 
    int ans;//存结果 
    //求  a的b次方 对 mode 求余的结果  即  (a^b)%mod 
    //思路是将 b 转成二进制 
    // 2^16次方  就是 2^8 * 2^8   ,2^8 就是 2^4 * 2^4  ... 
    int quickPow(int a,int b,int mod){
        
    	int res=1;
    	while(b){
        
    		if(b&1) res=res*a%mod;
    		b>>=1;
    		a=a*a%mod; 
    	}
    	return res; 
    } 
    int main(){
        
    	int a,b,mod;
    	cin>>a>>b>>mod;
    	ans = quickPow(a,b,mod);
    	cout<<ans; 
    	return 0; 
    }

#### 矩阵快速幂 ####

`看不懂就不看`

struct Mat
    {
        
        LL m[101][101];
    };//存储结构体
    Mat a,e; //a是输入的矩阵，e是输出的矩阵
    Mat Mul(Mat x,Mat y)
    {
        
        Mat c;
        for(int i=1;i<=n;++i){
        
            for(int j=1;j<=n;++j){
        
                c.m[i][j] = 0;
            }
        }
        for(int i=1;i<=n;++i){
        
            for(int j=1;j<=n;++j){
        
                for(int k=1;k<=n;++k){
        
                    c.m[i][j] = c.m[i][j]%mod + x.m[i][k]*y.m[k][j]%mod;
                }
            }
        }
        return c;
    }
    Mat pow(Mat x,LL y)//矩阵快速幂
    {
        
        Mat ans = e;
        while(y){
        
            if(y&1) ans = Mul(ans,x);
            x = Mul(x,x);
            y>>=1;
        }
        return ans;
    }

#### gcd与lcm ####

#include<bits/stdc++.h>
    #define ll long long 
    using namespace std; 
    // 定理  gcd(a,b)*lcm(a,b) = a*b  
    //最大公约数  求 a 与 b 的最大公约数 
    int gcd(int a,int b){
        
    	if(b==0) return a;
    	return gcd(b,a%b);
    }
    //最小公倍数 
    int lcm(int a,int b){
        
    	return a*b/gcd(a,b); // 
    } 
    int main(){
        
    	int a,b;
    	cin>>a>>b;
    	int ans1=gcd(a,b);
    	int ans2=lcm(a,b);
    	cout<<ans1; 
    	cout<<"\n"; 
    	cout<<ans2;
    	return 0; 
    }

#### 闰年判断 ####

#include<bits/stdc++.h>
    using namespace std;
    int main(){
        
    	ios::sync_with_stdio(false);
    	int n;	cin>>n;
    	if( (n%4==0&&n%100!=0) || n%400==0) cout<<"yes";
      	else cout<<"no";
    	return 0; 
    }

#### 质数 ####

`判断是不是质数`

int f(int x){
         //判断 x 是不是质数  
    	if(x==1) return 0;
    	for(int i=2;i<=sqrt(x);i++) if(x%i==0) return 0;
    	return 1;
    }

**质因数分解**

#include<bits/stdc++.h>
    using namespace std;
    int a,b;
    int prime[1000010];//存储质数
    int ht[1000010];
    struct tx{
        
    	int x,y;
    }c[20];
    int ans[100];
    int ct1=0;
    int main(){
        
    	ios::sync_with_stdio(false);
    	cin>>a>>b;
    	int ct=0;
    	for(int i=2;i<=b;i++){
        //预处理质数
    		if(!ht[i]){
        
    			prime[ct++]=i;// 将质数加入到 数组中
    			for(int j=i*i;j<b;j=j+i) ht[j]=true;  //将 改质数的倍数全部 标记为合数
    		}
    	}
    	//分解质因数 
    	for(int i=a;i<=b;i++){
         //对 a  到 b 的每一数进行分解
    		int t=i;
    		int len=0;
    		for(int j=0;j<ct;j++){
         //这里是核心
    			if(t%prime[j]==0){
        
    				c[len].x=prime[j];
    				c[len].y=0;
    				while(t%prime[j]==0){
        
    					c[len].y++;
    					t/=prime[j];
    				}
    				len++;
    			}
    		}
    		cout<<i<<"=";
    		for(int j=0;j<len;j++){
        
    			int t2 = c[j].y;
    			for(int k=0;k<t2;k++){
        
    				ans[ct1++]=c[j].x;
    			}
    		}
    		for(int j=0;j<ct1;j++){
        
    			if(j!=0) cout<<"*"; cout<<ans[j];
    		}
    		ct1=0;
    		cout<<"\n";
    //		memset(c,0,sizeof(c));
    		memset(ans,0,sizeof(ans));
    	}
        return 0;
    }

#### 组合 ####

![image-20220408231820834][]

图片来自acwing

https://www.acwing.com/problem/content/887/

`普通版的递推求法，还没有优化`

#include<bits/stdc++.h>
    #define ll long long 
    #define maxn 2010 
    using namespace std; 
    int n;
    int mod = 1e9+7;
    int c[maxn][maxn];//和数学中的求组合一样， 表示几个中选几个的结果 
    void init(){
        
    	for(int i=0;i<=2000;i++){
        
    		for(int j=0;j<=i;j++){
        
    			if(!j) c[i][j]=1;
    			else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    		}
    	}
    } 
    int main(){
        
    	init(); 
    	cin>>n;
    	while(n--){
        
    		int a,b;	cin>>a>>b;
    		cout<<c[a][b]<<"\n";
    	}
    	return 0; 
    }

#### 卡特兰数 ####

![image-20220409073253643][]

1 2 5 14 42 132 429

class Solution {
        
    public:
        int numTrees(int n) {
        
            long long C = 1;
            for (int i = 0; i < n; ++i) {
        
                C = C * 2 * (2 * i + 1) / (i + 2);
            }
            return (int)C;
        }
    };

#### 杨辉三角 ####

普通法

#include<bits/stdc++.h>
    using namespace std;
    int n;
    int a[100][100];//存储杨辉三角每一行的内容
    int main(){
        
    	cin>>n;
    	for(int i=1;i<=n;i++){
        //控制行
    		for(int j=1;j<=i;j++){
        
    			if(i==j||j==1) a[i][j]=1;//根据观察得出的
    			else a[i][j]=a[i-1][j]+a[i-1][j-1]; //根据观察易得
    		}
    	}
    	for(int i=1;i<=n;i++){
        
    		for(int j=1;j<=i;j++){
        
    			cout<<a[i][j]<<" ";
    		}
    		cout<<"\n";
    	}
    	return 0;
    }

### 搜索 ###

#### 全排列 ####

#include<bits/stdc++.h>
    using namespace std;
    int n;
    int a[10];
    bool b[10];
    int dfs(int x){
        
        if(x==n){
        
            for(int i=0;i<n;i++) cout<<a[i]<<" ";
            cout<<"\n";
            return 0;
        }
        for(int i=1;i<=n;i++){
        
            if(!b[i]){
        
                a[x]=i;
                b[i]=true;
                dfs(x+1);
                b[i]=false;
            }
        }
    }
    int main(){
        
        cin>>n;
        dfs(0);
        return 0;
    }

#### 组合 ####

#include<bits/stdc++.h>
    using namespace std;
    int a[10],b[10];
    int n;
    void dfs(int x,int st){
        
        if(x>=3){
        
            for(int i=0;i<3;i++) cout<<a[i];
            cout<<"\n";
            return ;
        }
        for(int i=st;i<=n;i++){
        
            if(!b[i]){
        
                a[x]=i;
                b[i]=true;
                dfs(x+1,st+1);
                b[i]=false;
            }
        }
    }
    int main(){
        
        cin>>n;
        dfs(0,1);
        return 0;
    }

#### 迷宫 ####

#include<bits/stdc++.h>
    using namespace std;
    int n,m;
    typedef pair<int,int> PII; //用来存点，用pair方便点点
    const int N=110; //数据范围
    int g[N][N],d[N][N];// g数组装整个图，  d数组表示某点到原点的距离
    int bfs(){
        
        queue<PII> q;
        q.push({
        0,0});//首先起点入队
        memset(d,-1,sizeof d);//将最开始的所有点到起点的距离都设置为-1
        d[0][0]=0;//起点到起点的距离设置为0,
        int dx[4]={
        0,1,0,-1},dy[4]={
        1,0,-1,0}; /*方向数组，随便向那个方向扩展都得行，
        我的是上(x不变，y会加1)右（x会加1，y不变）下（x不变，y会减1）左（x会减1，y不变）*/
        while(!q.empty()){
        
            auto t = q.front();//取出队首元素
            q.pop();//队首出队
            for(int i=0;i<4;i++){
        //向4个方向扩展
                // x,y 为扩展后的， t装的是拓展前的坐标
                int x=t.first+dx[i];
                int y=t.second+dy[i];
                //满足边界条件，拓展的点的位置没有障碍，在之前没有被访问过（距离为-1就表示没访问过）
                if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1){
        
                    d[x][y]=d[t.first][t.second]+1;//更新距离
                    q.push({
        x,y});//将成功扩展的点入队
                }
            }
        }
        return d[n-1][m-1];//最终 d[n-1][m-1] 就是右下角到左上角的需要移动的最短距离
    }
    int main(){
        
        cin>>n>>m;
        //读入图的信息
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                cin>>g[i][j];
        cout<<bfs()<<"\n";//输出结果
    }

### 并查集 ###

#include<bits/stdc++.h>
    using namespace std;
    // const int n=1000010;
    int m,n;
    int p[1000010];//存储节点的父亲
    int findX(int x){
        //采用了路径压缩
        if(x!=p[x]) p[x]=findX(p[x]);
        return p[x];
    }
    int main(){
        
    //    cin.tie(0);
    //    ios::sync_with_stdio(false);
        cin>>n>>m;
        for(int i=1;i<=n;i++) p[i]=i;
        while(m--){
        
            string x;
            int a,b;
            cin>>x>>a>>b;
            if(x=="M") p[findX(a)] = findX(b);
            else{
        
                if(findX(a)==findX(b)) cout<<"Yes\n";
                else cout<<"No\n";
            }
        }
    
        return 0;
    }

### 图 ###

#### spfa求最短路 ####

#include<bits/stdc++.h>
    using namespace std;
    #define maxn 1000010
    int n,m;
    //dist表示某点到起点的距离  
    //st表示某个点是否加入队列 true表示没加入,反之则加入 
    int dist[maxn],st[maxn];  
    // h:头结点  w:权重  e:边  ne:下一个点   idx就表示节点 
    int h[maxn],w[maxn],e[maxn],ne[maxn],idx;
    void add(int a,int b,int c){
        //邻接表  模板，背到就可以   
    	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
    }
    int spfa(){
        
    	memset(dist,0x3f,sizeof(dist));//将初始距离设为很大的数 
    	queue<int> q;
    	dist[1]=0;// 初始化第一个点到第一个点的距离为 0 ,方便后面的计算 
    	q.push(1);// 先将第一个点加入队列 
    	st[1]=true;//第一个点加入了队列，所以 st[1] = true 
    	while(!q.empty()){
        //广搜的模板 
    		int t = q.front();//取出第一个节点 
    		q.pop();//取出了后，就要出队列 
    		st[t]=false;//取出后，没在队列了，设置为 false 
    		for(int i=h[t];i!=-1;i=ne[i]){
        //更新t的出边 
    			int j = e[i];//获得和t相连的点
    			if(dist[j]>dist[t]+w[i]){
        //如果可以距离变得更短，则更新距离
    				dist[j]=dist[t]+w[i];
    				if(!st[j]){
        //如果没在队列中,可以入队 
    					q.push(j);
    					st[j]=true;//入队了，设置为false 
    				} 
    			}
    		}
    	}
    	return dist[n]==0x3f3f3f3f?-2:dist[n];
    }
    int main(){
        
    	cin>>n>>m;
    	memset(h,-1,sizeof(h));//这一步不能忘记 
    	while(m--){
        
    		int x,y,z;	cin>>x>>y>>z;
    		add(x,y,z);
    	}
    	int ans=spfa();
    	if(ans!=-2) cout<<dist[n];
    	else cout<<"impossible"; 
    	
    	return 0;
    }

参考了博客：https://www.acwing.com/solution/content/105508/

### 动态规划 ###

#### 01背包 ####

https://www.acwing.com/problem/content/2/

#include<bits/stdc++.h>
    #define ll long long 
    using namespace std; 
    #define maxn 10010
    int N,V;// N件物品，V为背包体积 
    int v[maxn],w[maxn];// v数组装物品的体积 , w数组装物品的价值 
    int dp[10010];
    int main(){
        
    	cin>>N>>V;
    	for(int i=1;i<=N;i++) cin>>v[i]>>w[i];
    	for(int i=1;i<=N;i++){
        
    		for(int j=V;j>=v[i];j--){
        //dp[j]为 容量为j的背包所背的最大价值 
    			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);	
    		}
    	} 
    	cout<<dp[V]; 
    	return 0; 
    }

#### 完全背包 ####

https://www.acwing.com/problem/content/description/3/

#include<bits/stdc++.h>
    #define ll long long 
    using namespace std; 
    #define maxn 10010
    int N,V;// N件物品，V为背包体积 
    int v[maxn],w[maxn];// v数组装物品的体积 , w数组装物品的价值 
    int dp[10010];
    int main(){
        
    	cin>>N>>V;
    	for(int i=1;i<=N;i++) cin>>v[i]>>w[i];
    	for(int i=1;i<=N;i++){
        
    		for(int j=v[i];j<=V;j++){
        //dp[j]为 容量为j的背包所背的最大价值 
    			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);	
    		}
    	} 
    	cout<<dp[V]; 
    	return 0; 
    }

#### 多重背包 ####

https://www.acwing.com/problem/content/description/4/

强制拆分成 01 背包来做

#include<bits/stdc++.h>
    #define ll long long 
    using namespace std; 
    #define maxn 100010
    int N,V;// N件物品，V为背包体积 
    int v[maxn],w[maxn];// v数组装物品的体积 , w数组装物品的价值 
    int dp[10010];
    int len=0;//用来记录 v 与 w 数组的长度 
    int main(){
        
    	cin>>N>>V;
    	for(int i=1;i<=N;i++){
        
    		int vi,wi,s;	cin>>vi>>wi>>s;
    		while(s--){
        //拆成 01 背包来做
    			v[++len]=vi;
    			w[len]=wi; 
    		} 
    	} 
    	for(int i=1;i<=len;i++){
        //这里就是有 len 个物品了
    		for(int j=V;j>=v[i];j--){
        //dp[j]为 容量为j的背包所背的最大价值 
    			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);	
    		}
    	} 
    	cout<<dp[V]; 
    	return 0; 
    }

#### 分组背包 ####

#include<bits/stdc++.h>
    #define ll long long 
    using namespace std; 
    #define maxn 150
    int N,V;// N件物品，V为背包体积 
    int v[maxn][maxn],w[maxn][maxn],s[maxn];// v数组装物品的体积 ,w数组装物品的价值 ,s数组表示第每组物品的个数 
    int dp[10010];
    int len=0;//用来记录 v 与 w 数组的长度 
    int main(){
        
    	cin>>N>>V;
    	for(int i=1;i<=N;i++){
        
    		cin>>s[i];
    		for(int j=0;j<s[i];j++){
        
    			cin>>v[i][j]>>w[i][j];
    		}
    	} 
    	for(int i=1;i<=N;i++){
        // n组 
    		for(int j=V;j>=0;j--){
        
    			for(int k=0;k<s[i];k++){
        
    				if(v[i][k]<=j) dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]);
    			}
    		}
    	} 
    	cout<<dp[V]; 
    	return 0; 
    }

【都看到这了，点点赞点点关注呗，爱你们】😚😚

![抽象工厂  引导关注][be51b5ae72be315fffbfe46c72e6d7b1.png]

**结语**

`谢谢你的阅读`，由于作者水平有限，难免有不足之处，若读者发现问题，还请批评，在留言区留言或者私信告知，我一定会尽快修改的。若各位大佬有什么好的解法，或者有意义的解法都可以在评论区展示额，万分谢谢。  
写作不易，望各位老板点点赞，加个关注!😘😘😘

💬

**作者：****后端小知识**

**CSDN**个人主页：[后端小知识][Link 1]

🔎**GZH**：`后端小知识`

🎉欢迎关注🔎点赞👍收藏⭐️留言📝

[Link 1]: https://blog.csdn.net/m0_46833224
[image-20220408231820834]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/60f3e9db1d17486e9d0047fce6aff5a3.png
[image-20220409073253643]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/dfe835992d7e40a3b83667c3e4a332d7.png
[be51b5ae72be315fffbfe46c72e6d7b1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/ab69f1ef827043b7b058f6ab38a61af4.png