蓝桥杯算法

目录

*表示该算法在蓝桥杯中的重要程度，最高5颗星，最低1颗星。

基础算法（这些不会就放弃蓝桥杯吧）

  1. 最大公约数(gcd)和最小公倍数(lcm)（*****）
  2. 日期是否合法（包含闰年和平年判断）(*****)
  3. 数的拆分 （*****）
  4. 判断质数（***）
  5. 组合排列（***）
  6. 排序 （**）

蓝桥杯必备算法(***以上必须掌握)

  1. 模拟 （*****）
  2. DFS(深度优先搜索) （*****）
  3. BFS(广度优先搜索)（****）
  4. 二分查找（****）
  5. 哈希数组（****）
  6. 前缀和（****）
  7. 简单DP（***）
  8. 贪心（***）
  9. 优先队列 （***）
  10. 双指针 （***）
  11. 差分（**）
  12. 树状数组 （*）

常用方法以及库函数

  1. 输入
  2. 输出
  3. 自动类型转换auto

算法实例

基础算法

1. 最大公约数(gcd)和最小公倍数(lcm)

  • 求a和b的最大公因数和最小公倍数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
using namespace std;

//求a和b的最大公因数 
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
//求a和b的最小公倍数 
int lcm(int a,int b)
{
	return a*b/gcd(a,b);
}

int main()
{
	int n,m;
	cin>>n>>m;
	cout<<"n和m的最大公因数是:"<<gcd(n,m)<<endl;
	cout<<"n和m的最小公倍数是:"<<lcm(n,m)<<endl;
}

2.日期是否合法（包含闰年和平年判断）

  • 给定一个年份,输出该年份每月有多少天
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
using namespace std;

/*
	闰年和平年的区别：在2月份，闰年比平年多一天 
	所以定义平年的每月份天数的数组，要是闰年在此基础上加一天即可 
*/
//平年每月的天数,为了下标和月份相同，在前面补了个0，补不补0无所谓，根据自己的习惯 ！！ 
int month[]={0,31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};//这个不需要记，因为蓝桥杯可以看本地电脑日历 

//判断是否为闰年 
bool isRunYear(int year)
{
	return (year%4==0&&year%100!=0 || year%400==0);
}
int main()
{
	int year;
	cin>>year;
	if(isRunYear(year))
	{
		month[2]++;
		//不补0就是month[1]++; 
	}
	for(int i=1;i<=12;i++)
	{
		cout<<month[i]<<endl;
	}
}

3.数的拆分

  • 给定一个整数n（范围1~1e9）,求各位数上的和。例n=123,则sum=1+2+3=6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;

int getSum(int n)
{
	int sum=0;
	while(n)
	{
		sum+=n%10;
		n/=10;	
	} 
	return sum;
}
int main()
{
	int n;
	cin>>n;
	cout<<getSum(n); 
}
  • 给定一个整数n（范围1~1e9）和某个位数m，输出该正整数n上的m位的值。如n=123，m=3，则num=1,n百位数上的值是1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
#include<cmath>
using namespace std;

int getNum(int n,int m)
{
	return (n/(int)pow(10,m-1))%10;
}
int main()
{
	int n,m;
	cin>>n>>m;
	cout<<getNum(n,m); 
}

4.判断质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cmath>
using namespace std;

bool isPrime(int n)
{
	if(n<=1)return false;
	for(int i=2;i<=sqrt(n);i++)
	{
		if(n%i==0)return false;	
	} 
	return true;
}
int main()
{
	int n;
	cin>>n;
	if(isPrime(n))cout<<n<<"是质数";
	else  cout<<n<<"不是质数";
}

5.组合排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<cmath>
using namespace std;

// 计算阶乘
long long factorial(int n)
{
    if (n == 0 || n == 1) return 1;
    long long result = 1;
    for (int i = 2; i <= n; ++i) {
        result *= i;
    }
    return result;
}

// 计算排列数 P(n, k)
long long permutation(int n, int k)
{
    if (k > n) return 0; // 如果 k > n，排列数为 0
    return factorial(n) / factorial(n - k);
}

// 计算组合数 C(n, k)
long long combination(int n, int k) {
    if (k > n) return 0; // 如果 k > n，组合数为 0
    return factorial(n) / (factorial(k) * factorial(n - k));
}

int main()
{
	int n,k;
	cin>>n>>k;
	cout<<permutation(n,k)<<endl;
    cout<<combination(n,k)<<endl;
}

6.排序

  • 如果仅需要排序的话，建议使用sort()
1
2
3
//函数原型
void sort(RandomIt first, RandomIt last, Compare comp); //第三个参数是排序规则
void sort(RandomIt first, RandomIt last);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<algorithm>
using namespace std;

bool temp(int n1,int n2)
{
	//排序规则，每两个元素比较，保证第一个元素大于第二个元素 
	return n1>n2;
}
int main()
{
	int arr[]={1,5,9,8,4,6,7,10};
	int size=sizeof(arr)/sizeof(arr[0]);
	
	//默认升序排序 
	sort(arr,arr+size);
	
	for(int i=0;i<size;i++)
	{
		cout<<arr[i]<<" ";	
	}	
	cout<<endl;
	
	//加入模板函数，自定义排序规则，降序排序 
	sort(arr,arr+size,temp);
	for(int i=0;i<size;i++)
	{
		cout<<arr[i]<<" ";	
	}
}
  • 特殊情况下需要使用某种排序，比如逆序对就要使用归并排序，这里冒泡和归并用得多。
  • 归并排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010;
int n;
int q[N],w[N];
void merge_sort(int l,int r)
{
    if(l>=r)return;
    int mid = l + r >> 1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r)
    {
        if(q[i]<q[j])
        {
            w[k++]=q[i++];
        }else
        {
            w[k++]=q[j++];
        }
    }
    while(i<=mid)
    {
        w[k++]=q[i++];
    }
    while(j<=r)
    {
        w[k++]=q[j++];
    }
    for(i = l,j=0;i<=r;i++,j++)q[i]=w[j];

}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&q[i]);
    }
    merge_sort(0,n-1);
    for(int i=0;i<n;i++)
    {
        printf("%d ",q[i]);
    }
    return 0;
}

  • 冒泡排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<algorithm>
using namespace std;
int n,arr[100]; 
void bubble_Sort(int arr[],int n)
{
	for(int i=0;i<n-1;i++)
	{
		for(int j=0;j<n-1-i;j++)
		{
			if(arr[j]>arr[j+1])
			{
				int t=arr[j];
				arr[j]=arr[j+1];
				arr[j+1]=t;
			}
		}
	}
}
int main()
{
	cin>>n;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }
    bubble_Sort(arr,n);
     for(int i=0;i<n;i++)
    {
        printf("%d ",arr[i]);
    }
}

蓝桥杯必备算法

1.模拟

没有具体的模板，模拟就是根据题意来还原场景，从而做出解答，多练即可。

2.DFS(深度优先搜索)

  • DFS模板，一般用于暴力枚举
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
using namespace std;
void dfs(递归参数)
{
    if(递归参数太离谱了)//剪枝[可选]
    {
        return;
	}
    
	if(终止条件)
	{
		//输出答案或者答案计数 
		return; 
	} 
	
	for(枚举每种方案)
	{
		状态记录
		dfs(下一个递归参数);//递归的下一个状态
		状态还原 
	}
	
}
int main()
{
	dfs(递归参数); 
}

3.BFS(广度优先搜索)

  • BFS模板，一般用于图论
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//-----------------------------------------------

一个迷宫由 R行 C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。
给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。
只能在水平方向或垂直方向走，不能斜着走。

5 5
..###
#....
#.#.#
#.#.#
#.#..
//-----------------------------------------------
#include<iostream>
#include<cstring>
#include<queue>
#define x first
#define y second
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
using namespace std;
typedef pair<int,int> PII;
const int N=45;
int r,c;
char g[N][N];
int a[N][N];
void bfs(int sx,int sy)
{
    queue<PII> q;
    memset(a,-1,sizeof a);
    a[sx][sy]=1;
    q.push({sx,sy});
    
    while(!q.empty())
    {
        auto t =q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int xx = dx[i]+t.x;
            int yy = dy[i]+t.y;
            if(xx<0||xx>r-1||yy<0||yy>c-1)continue;
            if(a[xx][yy]!=-1)continue;
            if(g[xx][yy]!='.')continue;
            
            q.push({xx,yy});
            a[xx][yy]=a[t.x][t.y]+1;
        }
        
        if(t.x==r-1&&t.y==c-1)
        {
            cout<<a[t.x][t.y];
        }
    }
}
int main()
{
    cin>>r>>c;
    for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
        {
            cin>>g[i][j];
        }
    }
    
    bfs(0,0);
    
}

4.二分查找

  • 已知条件，带入答案求最优解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
using namespace std;

bool check(int num)
{
	//把num作为条件带入 返回是true和false 
}
int main()
{
	int l=左边界-1;
	int r=右边界-1;
	while(l+1<r)
	{
		int mid = l+r>>1;
		if(check(mid))
		{
			//l=mid;
			//r=mid;
		}
		else
		{
			//l=mid;
			//r=mid;
		}	
	} 
	
	//这里最好带入判断一下（如果你确定答案在r或者l上，这个可以不用写）
	if(check(l)&&check(r))
	{
		//根据题意取最大值或者最小值 
		//cout<<max(l,r);
		//cout<<min(l,r);
	}
	else if(check(l)) 
	{
		//根据题意整理关于l的值 
		//cout<<l;
	}
	else if(check(r)) 
	{
		//根据题意整理关于r的值 
		//cout<<r;
	}
}

5.哈希数组

前置知识：输出某个字符的ASCII值。（所以ACSII值不需要记，考场直接输出即可）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
using namespace std;


int main()
{
	cout<<"A字符的ASCII"<<int('A')<<"\n"; 
	cout<<"1字符的ASCII"<<int('1')<<"\n"; 
	cout<<"?字符的ASCII"<<int('?')<<"\n"; 
}
/*
0~9的ASCII: 48~57
A~Z的ASCII: 65~90
a~z的ASCII: 97~122
*/
  • 哈希数组：用来标记或者统计某个值出现的次数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*---------------------------------------
给定一个字符串，可能保含0~9数字、a~z、A~Z字母，统计它们出现的次数 
input: 123456ABCZZZaaaccc
output:
1出现了1次 
2出现了1次
………………
c出现了3次 
------------------------------------------*/ 
#include<iostream>
#include<cstring> 
using namespace std;

//数组的下标必能够表示 0~9、a~z、A~Z的ascii值 ,所以数组的下标范围必须能取到48~122 
//所以数组开130就足够了 
int hash[130]={0};
int main()
{

	string s="123456ABCZZZaaaccc";
	for(int i=0;i<s.size();i++)
	{
		hash[s[i]]++;	
	} 
	for(int i=0;i<130;i++)
	{
		if(hash[i]!=0)
		{
			cout<<char(i)<<"出现了"<<hash[i]<<"次"<<endl; 
		}
	}
}

6.前缀和

  • 快速求某个区间段上的和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*---------------------------------------
给定一个数组里面有n个元素，以及l,r，求数组子区间[l,r]的元素和 

---------------------------------------*/
#include<iostream>
#include<cstring> 
using namespace std;
const int N =100;
int n,l,r; 
int arr[N];
long long int sum[N]; //注意数组的单个元素大小，最好使用long long int 
int main()
{
	cin>>n>>l>>r;
	for(int i=1;i<=n;i++)
	{
		cin>>arr[i];
	}
	for(int i=1;i<=n;i++)
	{
		sum[i]=sum[i-1]+arr[i];//前缀和 
	}
	cout<<sum[r]-sum[l-1];
}

7.简单DP

  • 通过当前状态和上个状态之间的某种关系，得出最优解。
  • 多做题，能够找到状态转移方程即可。
  • 无固定模板。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*---------------------------------------
解题步骤 
1.关于状态数组f[N],一般情况下，一个状态涉及到几个值变化，就定义几维数组，简单DP一般不超过二维
2.寻找最终答案和上个答案的关系，正向或者反向不断转移状态
3.输出最终状态 
---------------------------------------*/
#include<iostream>
#include<cstring> 
using namespace std;
int f[N][N];//状态数组,根据情况是定义一维还是二维 
int main()
{
	for(枚举第一个值i)
		for(枚举第二个值j)
			f[i][j] = (f[i][j]或者f[i-1][j]或者f[i][j-1].....进行状态转移)
			
	cout<<f[N-1][N-1];//正向
	cout<<f[0][0];//逆向 
}

8.贪心

  • 局部最优解就是全局最优解，每一步都要保证是最优的，因此需要证明。
  • DP可以替代弹性
  • 没有模板，多做题

9.优先队列

  • 一种堆的数据结构
  • 有序队列，并且插入和修改不改变原有的有序性
  • 不需要记，考试可以查看C++帮助手册
  • 注意包含头文件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<queue>
#include<vector>
using namespace std;

int main()
{
	priority_queue<int,vector<int>,greater<int> > q;//greater<int>是std里面的升序模板，如果想降序就使用less<int>
	q.push(3); 
	q.push(13); 
	q.push(4); 
	q.push(0); 
	q.push(8); 
	while(!q.empty())
	{
		cout<<q.top()<<endl;
		q.pop();
	}
}

10.双指针

  • 无固定模板，注意指针偏移即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
using namespace std;


int main()
{

	for(int i=0,j=0;i<n;i++)
	{
		while(j<i)
		{
			j++;
		}
		
	 } 
	
}

11.差分

  • 区间修改，在某个区间里面的所有元素增加或者减少某个值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/*-----------------------------------
给定一个n个元素的数组，接下来k次操作都会使该数组[l,r]区间里面所有的元素增加1个单位，最后输出该数组
第一行输入n和k
第二行输入数组
第3+k行输入l和r 
input:
10 3 

0 3
2 6
5 9
output:
1 1 2 2 1 2 2 1 1 1
------------------------------------*/
#include<iostream>

using namespace std;
const int N = 100;
int arr[N];
int n,k;
int d[N];//差分数组
int res[N];//用来保存最后结果的数组 
int main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++)cin>>arr[i];
	
	while(k--)
	{
		int l,r;
		cin>>l>>r;
		d[l]++;//等差数列左边界初始化 
		d[r+1]--; //等差数列右边界初始化 
	}
	for(int i=1;i<n;i++)//对等差数列求一次前缀和 
	{
		d[i]=d[i]+d[i-1];		
	}

	for(int i=0;i<n;i++)
	{
		res[i]=arr[i]+d[i]; //把增量保存到答案数组里面 
	}
	
	for(int i=0;i<n;i++)
	{
		cout<<res[i]<<" "; 
	}
}

12.树状数组

  • 单点修改、区间查询
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/*-----------------------------
给定n个数组成的一个数列，规定有两种操作，一是修改某个元素，二是求子数列 [a,b]的连续和。
输入格式
第一行包含两个整数n和m，分别表示数的个数和操作次数。
第二行包含n个整数，表示完整数列。
接下来m行，每行包含三个整数 k,a,b（k=0，表示求子数列[a,b]的和；k=1，表示第a个数加b）。
数列从1开始计数。
输出若干行数字，表示 k=0 时，对应的子数列 [a,b]的连续和。
input:
10 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8
output:
11
30
35
-----------------------------*/
#include<iostream>
using namespace std;
int n,m;
const int N=100005;
int a[N],tr[N];
int lowbit(int x)
{
    return x & -x;
}
void add(int x,int v)
{
    for(int i=x;i<=n;i+=lowbit(i))
    {
        tr[i]+=v;
    }
}
int query(int x)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i))
    {
        res+=tr[i];
    }
    return res;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        add(i,a[i]); //给第i个元素，加上a[i]
    }
    int k,x,y;
    while(m--)
    {
        scanf("%d%d%d",&k,&x,&y);
        if(k==0)
        {
            printf("%d\n",query(y)-query(x-1));
        }else
        {
            add(x,y);
        }
    }
}

常用方法以及库函数

1.输入

  • 把单行字符串保存到一个变量里(含空格)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*--------------
input:
abc 123 ABC ***
 
---------------*/
#include<iostream>
#include<string>

using namespace std;
int main()
{
	string s;  
	getline(cin,s);
	cout<<s;
}
  • 字符串按字符数组存储
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*--------------
input:
abc123ABC***
output:
c
---------------*/
#include<iostream>
#include<string>

char ch[15]; 
using namespace std;
int main()
{
	scanf("%s",&ch);//方法一 
	cin>>ch;//方法二 
	
	cout<<ch[2];
}
  • 格式化输入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*--------------
input:
2026-12-01
output:
2026年12月1日 
---------------*/
#include<iostream>

int year,month,day; 
using namespace std;
int main()
{
	scanf("%d-%d-%d",&year,&month,&day);

	cout<<year<<"年"<<month<<"月"<<day<<"日";
}
  • 输入若干数据(无n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*--------------
input:
1 2 3 4 5 6 7 8 9…… 
output:
共有n个数据 
---------------*/
#include<iostream>

int n=0;//用来计数 
int arr[100];//用来存储数据 
using namespace std;
int main()
{
	while(cin>>arr[n++]);//循环输入
	n--;//多加了一个，需要见一
	
	cout<<"共有"<<n<<"个数据";
}

2.输出

  • 前置补零
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*--------------
output:
01 02 03 04 05……09 10 
---------------*/
#include<iostream>


using namespace std;
int main()
{
	for(int i=1;i<=10;i++)
	{
		printf("%02d ",i);//表示输出2位，前置补0 
	}	
}
  • 保留小数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*--------------
output:(保留两位小数) 
1/3 2/3 2/3 4/3 5/3
---------------*/
#include<iostream>


using namespace std;
int main()
{
	for(float i=1;i<=5;i++)
	{
		printf("%.2f ",i/3);//保留两位小数 
	}	
}
  • 四舍五入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>


using namespace std;
int main()
{
//------------------------------------
	//正整数 
	
	int a=104;
	int b=96;
	//a和b分别四舍五入为整十数 
	
	cout<<((a+5)/10)*10<<endl;
	cout<<((b+5)/10)*10<<endl;
//-----------------------------------	
	//四舍五入保留两位小数
	
	float c=0.564;
	float d=0.595;

	printf("%.2f\n",c);//C语言默认四舍五入 
	printf("%.2f\n",d);
	
//-----------------------------------
	//从小数保留至整数
	float e = 9.99;
	float f = 5.49; 
	printf("%d\n",(int)(e+0.5));
	printf("%d\n",(int)(f+0.5));
}

3.自动类型转换auto

  • 遍历容器方便，可以不使用
  • 需要C++11以上
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
#include<vector>

using namespace std;
int main()
{
	vector<int> v;
	for(int i=0;i<10;i++) v.push_back(i);
	
	for(auto it=v.begin();it!=v.end();it++)
	{
		cout<<*it<<" ";
	} 
}