蓝桥杯常用模板-Toy模板网

这篇具有很好参考价值的文章主要介绍了蓝桥杯常用模板。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

蓝桥杯算法模板

最大公约数（GCD）

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

拓展欧几里得(EXGCD)

//用以解决ax+by=gcd(a,b)等式中整数解x和y的定理
int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1; 
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a/b) * x;
    return d;
}

最小公倍数（LCM）

int lcm(int a,int b){
    return a*b/gcd(a,b);
}

多个数的GCD和LCM

int gcds(int a[],int n){
    int g=a[0];
    for(int i=1;i<n;i++){
        g=gcd(g,a[i]);
    }
    return g;
}
int lcms(int a[],int n){
    int l=a[0];
    for(int i=1;i<n;i++){
        l=lcm(a[i],l);
    }
    return l;
}

判断闰年

bool islesf(int x){
    return x%400==0||(x%4==0&&x%100!=0);
}

整数快速幂（用于快速求幂）

int pow(int a,int b){
    int ans=1,base=a;//ans:幂的结果 base:底数
    while(b){
        if(b&1){
            ans=base*ans;
        }
        base=base*base;
        b=b>>1;
    }
    return ans;
}
/*
&运算：通常用于二进制取位操作，例如一个数x & 1 的结果就是取二进制的最末位的值。还可以判断这个数的奇偶性，如果x&1==0，则x为偶数；如果x&1==1，则x为奇数。
>>运算：在这里是作为除法来使用，例如一个数x，x >> 1就表示x右移一位，即x=x/2。
*/

快速幂取模

int pow_mod(int a,int b,int c){
    int ans=1,base=a;//ans:结果 base:底数
    base=base%c;
    if(b==0){
        return 1%c;
    }
    while(b){
        if(b&1){
            ans=(ans*base)%c;
        }
        base=(base*base)%c;
        b=b>>1;
    }
    return ans;
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tRe0KZkY-1649588388827)(C:\Users\20490\AppData\Roaming\Typora\typora-user-images\image-20220227124619141.png)]

快速乘(O(logn))

typedef long long ll;
ll ksc(ll x,ll y/*,ll p*/){//计算x乘y,将y作为二进制数处理运算
    ll res=0;//加法初始化
    while(y){
        if(y&1){
            //res=(res+x)%p;//模仿二进制
            res+=x;
        }
        //x=(x<<1)%p;//将x不断乘2达到二进制
        x=x<<1;
        y>>=1;//即将二进制移位获取最后一位
    }
    return res;
}

对于一个大数最后结果只需要部分结尾数字，则在过程中取模即可

//只要求最后四位数字，即对中途的结果进行取模10000 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	ll f1,f2,f3;
	ll temp;
	f1=f2=f3=1;
	for(int i=4;i<=20190324;i++){
		temp=(((f1+f2)%10000)+f3)%10000;
		f1=f2;
		f2=f3;
		f3=temp;
	}
	cout<<temp<<endl;
}

逆元

如果两个整数的乘积模m后等于1，那么就称它们互为m的逆元

求a模m的逆元，就是求解同余式a x ≡ 1 ( m o d m ) ,在实际使用中，一般把x的最小正整数解称为a模m的逆元

int inverse(int a,int m)
{
	int x, y;
	int g = EXGCD(a, m, x, y);   //求解ax+my=1
    return (x%m+m)%m;            //a模m的逆元为(x%m+m)%m
}

筛选素数

bool isprime(int n){
	if(n==1)return false;
	for(int i=2;i*i<=n;i++){
		if(n%i==0)return false;
	}
	return true;
}

01背包(每个物品只有一件)

1.采用二维数组

int main(){
    int m,n;//m为总背包大小，n为物品个数
    cin>>m>>n;
    int weight[n],value[n];
    for(int i=0;i<n;i++){
        cin>>weight[i]>>value[i];
    }
    int dp[n][m+1]={0};
    //初始化
    for(int i=weight[0];i<=m;i++){
        dp[0][i]=weight[0];
    }
    for(int i=1;i<n;i++){//遍历物品
        for(int j=0;j<m+1;j++){//遍历背包容量
            if(j<weight[i]){
                dp[i][j]=dp[i-1][j];
            }else{
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
            }
        }
    }
    cout<<dp[n-1][m]<<endl;
}

2.采用一维数组

int main(){
    int m,n;//m为总背包大小，n为物品个数
    cin>>m>>n;
    int weight[n],value[n];
    for(int i=0;i<n;i++){
        cin>>weight[i]>>value[i];
    }
    int dp[m+1]={0};
    for(int i=0;i<n;i++){//遍历物品
        for(int j=m;j>=weight[i];j--){
            dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
        }
    }
    cout<<dp[m]<<endl;
}

完全背包(每个物品有无数件)

int main(){
    int m,n;
    cin>>m>>n;
    int weight[n],value[n];
    for(int i=0;i<n;i++){
        cin>>weight[i]>>value[i];
    }
    int dp[m+1]={0};
    for(int i=0;i<n;i++){
        for(int j=weight[i];j<=m;j++){
            dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
        }
    }
    cout<<dp[m]<<endl;
}

组合数模板

long long C(int n,int m){
    if(m==0)return 1;
    long long ans=1;
    for(int i=n;i>n-m;i++)ans*=i;
    for(int i=1;i<=m;i++)ans/=i;
    return ans;
}

这个算法的缺点在于如果会溢出，long long类型的数字到(83,41)就不能用了，所以需要借助大数

前缀和与差分

(18条消息) 前缀和与差分图文并茂超详细整理（全网最通俗易懂）_林深不见鹿的博客-CSDN博客_前缀和与差分

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EQgqJkM2-1649588388828)(C:\Users\20490\AppData\Roaming\Typora\typora-user-images\image-20220307093359244.png)]

//一维前缀和
int main(){
    int n,m;
    cin>>n>>m;
    int arr[n+1],sum[n+1];
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+arr[i];
    }
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<sum[r]-sum[l]<<endl;
    }
    return 0;
}
//二维前缀和
int main(){
    int n,m,p;
    int arr[n+1][m+1],sum[n+1][m+1];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>arr[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i][j];
        }
    }
    while(p--){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]<<endl;
    }
}

时间复杂度从O(nm)降到O(n+m)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XWfZ3SDS-1649588388829)(C:\Users\20490\AppData\Roaming\Typora\typora-user-images\image-20220307090619445.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PEcNgGlN-1649588388830)(C:\Users\20490\AppData\Roaming\Typora\typora-user-images\image-20220307090908854.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jUrzzyTW-1649588388830)(C:\Users\20490\AppData\Roaming\Typora\typora-user-images\image-20220307153630426.png)]

//一维差分
int main(){
    int n,m;
    cin>>n>>m;
    int a[n+1],b[n+1]
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i]-a[i-1];//构造差分数组
    }
    while(m--){
        int r,l,c;
        cin>>r>>l>>c;
        b[l]+=c;
        b[r+1]-=c;
    }
    for(int i=1;i<=n;i++){
        b[i]+=b[i-1];
        cout<<b[i]<<" ";
    }
    return 0;
}
//二维差分
int main(){
    int n,m,p;
    cin>>n>>m>>p;
    int a[n+1][m+1],b[n+1][m+1];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<m;j++){
            b[i][j]+=a[i][j];
            b[i+1][j]-=a[i][j];
            b[i][j+1]-=a[i][j];
            b[i+1][j+1]+=a[i][j];//构造差分数组
        }
    }
    while(p--){
        int x1,y1,x2,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        b[x1][y1]+=c;
        b[x1+1][y1]-=c;
        b[x1][y1+1]-=c;
        b[x1+1][y1+1]+=c;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            b[i][j]=b[i][j]+b[i-1][y]+b[i][j-1]-b[i-1][j-1];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<b[i][j]<<" ";
        }
    }
    return 0;
}

全排列函数next_permutation(arr,arr+n)

在C++中有函数**next_permutation(arr,arr+n)**可以产生全排列的所有情况

注意next_permutation（）在使用前需要对欲排列数组按升序排序

此外，next_permutation（node,node+n,cmp）可以对结构体num按照自定义的排序方式cmp进行排序

在产生过程中，直到产生完毕返回false,其余情况都返回true

//使用方式
#include <iostream>  
#include <algorithm>  
using namespace std;  
int main()  
{  
    int num[3]={1,2,3};  
    do  
    {  
        cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;  
    }while(next_permutation(num,num+3));  
    return 0;  
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-viEAGdXt-1649588388831)(C:\Users\20490\AppData\Roaming\Typora\typora-user-images\image-20220308191209589.png)]文章来源地址https://www.toymoban.com/news/detail-416329.html

全排列（递归）

无重复元素

//数组实现
#include <iostream>
#include <cstring>
using namespace std;

template <class Type> inline void Swap(Type &a, Type &b) {
    Type temp = a; a = b; b = temp;
}
template <class Type>
void Perm(Type list[], int k, int n) {
    if(k == n) {
        for(int i = 0; i <= n; i++) cout << list[i];
        cout << endl;
    }
    else {
        for(int i = k; i <= n; i++) {
            Swap(list[k], list[i]);
            Perm(list, k+1, n);
            Swap(list[k], list[i]);
        }
    }
}
int main() {
    char s[] = "abcd";
    int len = strlen(s);
    Perm(s, 0, len-1);
    return 0;
}
//容器vector实现
class Solution {
public:
 vector<vector<int>> result;
 vector<int> path;
 void backtracking (vector<int>& nums, vector<bool>& used) {
 // 此时说明找到了⼀组
 if (path.size() == nums.size()) {
 result.push_back(path);
 return;
 }
 for (int i = 0; i < nums.size(); i++) {
 if (used[i] == true) continue; // path⾥已经收录的元素，直接跳过
 used[i] = true;
 path.push_back(nums[i]);
 backtracking(nums, used);
 path.pop_back();
 used[i] = false;}

有重复元素

class Solution {
private:
 vector<vector<int>> result;
 vector<int> path;
 void backtracking (vector<int>& nums, vector<bool>& used) {
 // 此时说明找到了⼀组
    if (path.size() == nums.size()) {
     	result.push_back(path);
     	return;
 	}
 	for (int i = 0; i < nums.size(); i++) {
 // used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
 // used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
 // 如果同⼀树层nums[i - 1]使⽤过则直接跳过
 		if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
 			continue;
 		}
 		if (used[i] == false) {
             used[i] = true;
             path.push_back(nums[i]);
             backtracking(nums, used);
             path.pop_back();
             used[i] = false;
 		}
 	}
 }
public:
     vector<vector<int>> permuteUnique(vector<int>& nums) {
         result.clear();
         path.clear();
         sort(nums.begin(), nums.end()); // 排序
         vector<bool> used(nums.size(), false);
         backtracking(nums, vec, used);
         return result;
 	}
};

并查集

int pre[1000 ];
int find(int x)                                       //查找根节点
{ 
    int r=x;
    while ( pre[r] != r )                           //返回根节点 r
          r=pre[r];
 
    int i=x , j ;
    while( i != r )                                   //路径压缩
    {
         j = pre[ i ]; 				// 在改变上级之前用临时变量  j 记录下他的值 
         pre[ i ]= r ; 				//把上级改为根节点
         i=j;
    }
    return r ;
}

void join(int x,int y)
{
    int fx=find(x),fy=find(y);
    if(fx!=fy)									 //判断x y是否连通，
        pre[fx ]=fy;							//如果已经连通，就不用管了 如果不连通，就把												     它们所在的连通分支合并起,
}

迪杰斯特拉算法

//迪杰斯特拉算法 
#include <iostream>
using namespace std;
void dijkstra();
int e[10][10];
int vis[10];
int dis[10];
int n, m;
int min1 = 99999999;
int u = 0;
int main()
{
    cin >> n >> m;
    // 初始化邻接表
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
            {
                e[i][j] = 0;
            }
            else
            {
                e[i][j] = 99999999;
            }
        }
    }
    // 填充数据
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        e[a][b] = c;
    }
    for (int i = 1; i <= n; i++)
    {
        dis[i] = e[1][i];
    }
    vis[1] = 1;

    dijkstra();

    for (int i = 1; i <= n; i++)
    {
        cout << "1-->"<<i<<":"<<dis[i]<<endl;
    }

    system("pause");
    return 0;
}
void dijkstra()
{
    for (int i = 1; i <= n - 1; i++)
    {
        min1 = 99999999;
        // 寻找权值最小的点u
        for (int j = 1; j <= n; j++)
        {
            if (vis[j] == 0 && dis[j] < min1)
            {
                min1 = dis[j];
                u = j;
            }
        }

        vis[u] = 1;

        for (int v = 1; v <= n; v++)
        {
            // 对于每个u可达的v来说
            if (e[u][v] < 99999999)
            {
                // 如果当前的dis[v]不满足三角形不等式，那么进行松弛操作
                if (dis[v] > dis[u] + e[u][v])
                {
                    dis[v] = dis[u] + e[u][v];
                }
            }
        }
    }
}

弗洛伊德算法

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

int arr[100][100];

int main(){
	int n,m,a,b,c;
	cin>>n>>m;
	//初始化 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j){
				arr[i][j]=0;
			}else{
				arr[i][j]=999999;
			}
		}
	}
	//填充数据
	while(m--){
		cin>>a>>b>>c;
		arr[a][b]=c;
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				arr[i][j]=min(arr[i][j],arr[i][k]+arr[k][j]);
			}
		}
	} 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<arr[i][j]<<" ";
		}
		cout<<endl;
	}
}

BFS

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

int n,m;
char mapp[505][505];//存储地图
int visited[505][505];//标记是否搜索过
int nextt[4][2]={{1,0},{0,-1},{0,1},{-1,0}};
char k[4]={'D','L','R','U'}; 

struct node{
	int x;
	int y;
	int step;
	string s;
};

void bfs(){
	node a,b;
	queue<node>q;
	memset(visited,0,sizeof(visited));
	visited[0][0]=1;
	a.x=0;
	a.y=0;
	a.step=0;
	a.s="";
	q.push(a);
	while(!q.empty()){
		a=q.front();
		q.pop();
		if(a.x==n-1&&a.y==m-1){
			cout<<a.step<<endl;
			cout<<a.s<<endl;
			return;
		}
		for(int i=0;i<4;i++){
			b.x=a.x+nextt[i][0];
			b.y=a.y+nextt[i][1];
			b.step=a.step+1;
			if(b.x<0||b.x>=n||b.y<0||b.y>=m){
				continue;
			}
			if(visited[b.x][b.y]==1||mapp[b.x][b.y]==1){
				continue;
			}
			b.s=a.s+k[i];
			visited[b.x][b.y]=1;
			q.push(b);
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>mapp[i][j];
		}
	}
	bfs();
}

DFS

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

int dx[4]={1,0,0,-1};
int dy[4]={0,-1,1,0};
char t[4]={'D','L','R','U'};
char res[100];
int vis[30][50]={0};
char ch[30][50];
int mmin=INT_MAX;

void dfs(int x,int y,int step){
	if(x==29&&y==49){
		mmin=min(mmin,step);
		for(int i=0;i<mmin;i++)
			cout<<res[i];//输出所走的最短路径
		return;
	}
	for(int i=0;i<4;i++){
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(xx<0||yy<0||xx>=30||yy>=50||step+1>=mmin){
			continue;
		}
		if(vis[xx][yy]==0&&ch[xx][yy]=='0'){
			vis[xx][yy]=1;
			mmin=step+1;
			res[step]=t[i];
			dfs(xx,yy,step+1);
			vis[xx][yy]=0;
		}
	}
}

int main(){
	for(int i=0;i<30;i++){
		for(int j=0;j<50;j++){
			cin>>ch[i][j];
		}
	}
	vis[0][0]=1;
	dfs(0,0,0);
}

合并区间

#include<bits/stdc++.h>
using namespace std;
int num=0; 
int n;
struct node{
	int l;
	int r;
};
bool cmp(node &a,node &b){
	return a.r<b.r||(a.r==b.r && a.l<b.l);
}

int main(){
	cin>>n;
	node p[n];
	for(int i=0;i<n;i++){
		cin>>p[i].l>>p[i].r;
	}
	sort(p,p+n,cmp);
	for(int i=0;i<n;){
		num++;
		int tmp=p[i].r;
		while(p[++i].l<tmp);
	}
	cout<<num<<endl;
	return 0;
}

平方数判断

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

int main(){
	int n;
	cin>>n;
	if(sqrt(n)*sqrt(n)==n){
		cout<<"平方数"<<endl;
	}else{
		cout<<"非平方数"<<endl;
	}
	return 0;
}

记忆化搜索

//非记忆化搜索方式，会增加很多此已知数据的计算
int sol(int x){
	if(x==1)return 1;
    int ans=0;
    for(int i=1;i<=x/2;i++){
		ans+=sol(i);
    }
    return ans;
}
//记忆化搜索方式，可以将之前算出的定值记录下来
int f[1010];
int sol(int x){
    if(x==1)return 1;
    if(f[x]!=-1)return f[x];
    int ans=0;
    for(int i=1;i<=x/2;i++){
        ans+=sol(i);
    }
    return f(x)=ans;
}
int main(){
    cin>>n;
    memset(f,-1,sizeof(f));
    f[1]=1;
    cout<<sol(n)<<endl;
}

二分查找

/*普通版：用于无重复元素情况*/
int find(int x){
    int l=1,r=n;
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid]==x)return mid;
        else if(a[mid]>x)r=mid-1;
        else l=mid+1;
    }
    return -1;
}
/*用于寻找有重复元素的最小下标情况*/
int find(int x){
    int l=1,r=n+1;
    while(l<r){
        int mid=(l+r)/2;
        if(a[mid]>=x)r=mid;
        else l=mid+1;
    }
    if(a[l]==x)return l;
    else return -1;
}
/*用于寻找有重复元素的最大下标情况*/
int find(int x){
	int l=1,r=n+1;
    while(l<r){
        int mid=(l+r)/2;
        if(a[mid]<=x)l=mid+1;
        else r=mid;
    }
    if(a[l]==x)return l-1;
    else return -1;
}

到了这里，关于蓝桥杯常用模板的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！