蓝桥杯真题练习-1

2023-10-18

Word count: 8.3k | Reading time≈ 38 min

蓝桥杯真题练习

第一天

【真题练习】成绩统计

问题描述

这题思路简单，但是对于细节考的很细，最初示例输入之后输出的优秀率始终为42%，原因是因为count_excellent*100/n中的/是整除，要想除之后保留小数必须定义分母或分子中至少一个变量为浮点型（float或double）。

解决代码：

#include<bits/stdc++.h>
using namespace std;
//自定义的round函数，不过cmath库中有封装好的round函数 
double round(double x){
	return (int)(x+0.5);
}

int main() {
	int n,grade;
	cin>>n;
	int pass_rate=0,excellent_rate=0;
	double count_pass=0,count_excellent=0;
	for(int i=0;i<n;++i){
		cin>>grade;
		if(grade>=85){
			count_pass++;
			count_excellent++;
		}else if(grade>=60){
			count_pass++;
		}
	}
	pass_rate=round((double)(count_pass*100/n));
	excellent_rate=round((double)(count_excellent*100/n));
//	cout<<count_pass<<endl;
//	cout<<count_excellent<<endl;
	cout<<pass_rate<<"%"<<endl;
	cout<<excellent_rate<<"%";
	return 0;
}

【真题练习】排列字母

问题描述

思路分析：

暴力解决，手算之后直接输出

利用set的有序性？（set会对key进行升序排序，但set会自动去重，可以考虑multiset，multiset可以有重复元素，但直接修改multiset的元素会破坏其自动有序性，只能删除一个元素再insert一个元素来达到修改的目的）

利用sort进行排序（需要重写comp？）

解决代码：

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

int main() {
	string s;
	cin>>s;
	multiset<char>myset;
	for(const char&c:s){
		myset.emplace(c);
	}
	for(const auto&p:myset){
		cout<<p;
	}
	return 0;
}
//sort实现
#include<bits/stdc++.h>
using namespace std;

int main() {
	string s;	
	cin>>s;
	sort(s.begin(),s.end());
	for(const char&c:s){
		cout<<c;
	}
	return 0;
}

【真题练习】纸张尺寸

问题描述

思路分析：

判断将长边作为对折边，width>length,swap(length,width).

pair类型存储长短边，固定first为长边，second为短边。

解决代码：

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

int main() {
	string s;
	cin>>s;
	pair<int,int>paper[10];
	paper[0].first=1189,paper[0].second=841;
	for(int i=1;i<10;++i){
		paper[i].second=paper[i-1].first/2;
		paper[i].first=paper[i-1].second;
	}
	int flag=s[1]-'0';//将字符型转换为整型 
//	cout<<flag<<endl;
	cout<<paper[flag].first<<endl;
	cout<<paper[flag].second;
	return 0;
}

第二天

【真题练习】特殊时间

问题描述

思路分析：

3个四位数字组成特殊时间。

可看成3个三位数（9个数都一样），之后在每个三位数中再插入一个数字（向3个三位数中插入的数字都相同）

（这里我直接手算算出来，暂时没有想到什么好的方法）

解决代码：

【真题练习】卡片

问题描述

思路分析：

根据题目给出的提示信息可以知道数字1是最先被消耗完的。

暴力遍历求和看什么时候会消耗完数字1。

利用while循环以及取余%和整除/操作判断组成当前数字是否会超出给定数字的个数。

若刚好超出则将数字减1即可得到最大可以拼到的数字（最终结果）。

参考：(103条消息) 第十二届蓝桥杯试题 B: 卡片题解_蓝桥杯卡片问题_Veyne_的博客-CSDN博客

解决代码：

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

const int N=2021;
int sum[10];

bool check(int num){
	while(num){
		int remainder=num%10;
		if(!sum[remainder])return false;
		--sum[remainder];
		num/=10;
	}
	return true;
}

int main() {
	int k=1;	//定义在外面，方便最后输出 
	for(int i=0;i<10;++i)sum[i]=N;
	for(;check(k);++k);
	cout<<k-1;
	return 0;
}

//网上参考代码：
#include <iostream>
using namespace std;

int N = 2021;
int n = 10;
int a[10];//存储0-9数字的个数

bool check(int num) {//判断组成当前数字是否会超出给定数字的个数
    while (num) {
        int t = num % 10;
        if (!a[t]) return false;
        -- a[t];
        num /= 10;
    }
    return true;
}
int main() {
    int i = 1;
    for (int i = 0; i < n; i ++) a[i] = N;
    for (;check(i); i ++) ;
    cout << i - 1 << endl;
}

【真题练习】约数个数

问题描述

思路分析：

约数，又称因数。这里是求1200000有多少个因数。

注意1200000以0结尾，那么证明它只能被5或10整除（以此条件可以简化循环结构）。

一个数的约数必然包括1及其本身。

约数之间必然是成对出现的：1和1200000，2和600000……，所以我们可以限定遍历到sqrt(1200000)即可。

解决代码：

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

const int n=1200000;

int main() {
	int ans=0;
	int d=sqrt(n);
	for(int i=n;i>=d;i-=5){
		if(n%i==0)ans+=2;//能被i整除，余数为0即为约数 
	}
	cout<<ans;
	return 0;
}

第三天

【真题练习】数的计算

问题描述

输入描述

输入一个正整数 n。

输出描述

输出一个整数，表示具有该性质数的个数。

思路分析：

这道题可以递归处理，由于在左边添加的自然数不能比右边大，因此我们有i<=n/2；

定义递归函数f(x)，再遍历可以在整数n左边可添加的自然数，继续递归：f(i)，并再每次递归之前统计数+1；

重复操作。

解决代码：

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

int ans=1;//为什么要初始化为1？

void f(int x){
	if(x==1)return;//递归终止条件 
	for(int i=1;i<=x/2;++i){
		ans++;
		f(i);
	}
}

int main() {
	int n;
	cin>>n;
	f(n);
	cout<<ans;
	return 0;
}

【真题练习】数的划分

问题描述

输入描述

输入一行，2 个整数n*,k (6≤n≤200，2≤k*≤6)。

输出描述

输出一个整数，即不同的分法。

思路分析：

这是一个经典的组合问题，可以使用递归或者动态规划来解决。

假设 $f(n, k)$ 表示将整数 $n$ 分成 $k$ 份的方案总数。

首先，如果 $n < k$ 或者 $k = 0$ ，显然无法分配，此时 $f(n, k) = 0$ 。

其次，当 $n = k$ 或者 $k = 1$ 时，只有一种分配方案，即全放在一起，此时 $f(n, k) = 1$ 。

最后，考虑一般情况。我们可以钦定其中一份为 $1$ ，然后对剩下的 $n-1$ 进行 $k-1$ 的分配，此时方案数为 $f(n-1, k-1)$ 。另外，我们也可以不选择 $1$ ，而是将 $n$ 中的某个数 $m$ 作为钦定的数，然后对剩下的 $n-m$ 进行 $k-1$ 的分配，此时方案数为 $f(n-m, k-1)$ 。因此，我们可以列出如下的递推式：

$f(n, k) = \begin{cases} 1 & n = k \text{ or } k = 1 \\ 0 & n < k \text{ or } k = 0 \\ f(n-1, k-1) + f(n-2, k-1) + \cdots + f(n-k+1, k-1) & \text{otherwise} \end{cases}$

这个式子的含义是：将 $n$ 分成 $k$ 份的方案总数，等于钦定一份为 $1$ ，然后将剩下的 $n-1$ 分成 $k-1$ 份的方案数，以及钦定一份为 $m$ ，并将剩下的 $n-m$ 分成 $k-1$ 份的方案数，由于 $m$ 的取值范围是 $[1,n-k+1]$ ，因此需要将这些情况累加起来。

最终的答案就是 $f(n, k)$ 。实现时可以使用递归或者动态规划，时间复杂度均为 $O(nk)$ 。

将以上分析转换为代码思路：

划分：此题可以划分为在满足k个数组合等于n时两种情况：包含1、不包含1

状态： dp[i][j]含义为数字i划分为j部分的划分数

当包含1时：划分结果中至少有一个1 = 将n-1分成k-1份的结果（一定存在1，那么我就先划分出一个1，剩下的值无论怎么划分，最终结果中一定存在至少一个1）所以：dp[i][j]=dp[i-1][j-1]+不包含1的划分数

当不包含1时：划分结果中不存在1 = 将n-k划分为k份的结果（序列中不存在1，则划分结果序列中的数一定都大于等于2，所以等价于对于每一个数都减去1，则剩下的结果一定是n-k划分成k份的结果）不包含1的划分数 = dp[i-j][j]

状态转移方程： dp[i][j] = dp[i-1][j-1] + dp[i-j][j]

参考：(103条消息) 蓝桥杯数的划分(动态规划分析)_蓝桥杯数的划分_一个很懒的人的博客-CSDN博客

解决代码：

//解法一：递归(存在大量的重复计算，效率较低，容易超时)
#include<bits/stdc++.h>
using namespace std;
//递归涉及到过多的重复计算，容易超时 
int f(int n,int k){
	if(n<k)return 0;
	if(n==k||k==1)return 1;
	return f(n-k,k)+f(n-1,k-1);
}

int main() {
	int n,k;
	cin>>n>>k;
	cout<<f(n,k);
	return 0;
}

//解法二：动态规划（减少了重复计算过程，提升时间效率）
#include<bits/stdc++.h>
using namespace std;

int main() {
	int n,k;
	cin>>n>>k;
	int dp[n+1][k+1];//初始化的数组元素没有自动初始化为0，需要使用memset进行初始化值
	memset(dp,0,sizeof(dp));//将数组的所有元素都赋初值为0 
	dp[1][1]=1;
	for(int i=2;i<=n;++i){
		for(int j=1;j<=min(i,k);++j){
			dp[i][j]=dp[i-1][j-1]+dp[i-j][j];//dp[i-1][j-1]必定包含至少一个1的情况，dp[i-j][j]必定不包含1的情况 
		}
	} 
	cout<<dp[n][k];
	return 0;
}

【真题练习】耐摔指数

问题描述

输入描述

一个整数 n（3<n<10000）,表示测试塔的高度。

输出描述

输出一个整数，表示最多测试多少次。

思路分析：

这里的最佳策略应该是“动态规划”而不是“二分法”，因为每测试一次就有可能损失一部手机，手机的数量是有限的；

最坏的情况就是朝着测试次数最多的方向发展，也就是max(上楼测试的次数，下楼测试的次数)；

最佳策略就是要取当前测试次数最少的；

每个厂家只抽样 3 部手机参加测试

参考：

最优策略就是每次扔手机都从后续测试最少的层数扔出去，扔出去后手机摔坏与否总是往测试最多的方向发展即是最差运气。

至于这个最好的层数只能遍历出来才知道，也是for循环遍历然后找出min(min, max(扔出去被摔坏，扔出去没被摔坏))。

至于最差运气就是指每次扔出去手机的是否被摔坏总是指向要测试最多的方向发展。所以是 max(扔出去被摔坏，扔出去没被摔坏)

参考：(104条消息) 第九届蓝桥杯——耐摔指数_蓝桥杯摔手机算法_业余算法学徒的博客-CSDN博客

解决代码：

#include<bits/stdc++.h>
using namespace std;
//手机个数有限，不能采用二分法 
//最佳策略：动态规划；最坏运气：一直朝着测试次数最多的方向发展 
int main() {
	int n;
	cin>>n;
	int dp[4][n+1];
	for(int i=1;i<=3;++i){
		for(int j=1;j<=n;++j){
			dp[i][j]=j;//最坏测试次数永远是当前测试层数(从最高层往下到第一层都摔不坏)
		}
	}
	for(int i=2;i<=3;++i){			//每个厂家抽样 3 部手机参加测试。
		for(int j=1;j<=n;++j){		//最高层 
			for(int k=1;k<j;++k){	//k为当前层 
				dp[i][j]=min(dp[i][j],max(dp[i-1][k-1]+1,dp[i][j-k]+1));
			}
		}
	}
	cout<<dp[3][n];
	return 0;
}

另一种解法：

代码：

#include<bits/stdc++.h>
using namespace std;
// 耐摔测试 - lanqiao-177

int b[10005], c[10005];

int main() {
	int n;
	cin>>n;// 表示测试塔的高度
	int i = 0;
	while(c[i]<n){
		i++;// 1部手机的情况
		b[i] = b[i-1] + i;// 2部手机的情况
		c[i] = c[i-1] + b[i-1] + 1;// 3部手机的情况 
	}
	cout<<i;
	return 0;
}

第四天

【真题练习】迷宫

$\textcolor{red}{分析：}$

本题采用广度优先搜索；

根据题目中四个方向的优先级（D<L<R<U）定义方向数组dy,dx；

定义存储各点到终点的最短距离；

定义存储四个方向D，L，R，U的char数组，方便后面输出；

使用bfs时应该从终点往起点遍历，这样能够得到可以从起点到终点的路径，不能从起点到终点的路线在反向遍历的过程中就断了；

最后从起点开始遍历，找到能够到达终点且字典序最小的最短路径。

$\textcolor{red}{值得注意的是：}$

本题数据输入并不是单个单个的输入，而是一行一行的输入，因此我们如果采用int类型的话不方便处理，而使用char类型则可以将每一行的数据视为一个string字符串，方便将每一个字符输入到矩阵中。

计算代码：

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

int dy[4]={1,0,0,-1},dx[4]={0,-1,1,0};//根据四个方向的优先级（D<L<R<U）定义控制方向的行数组dy与列数组dx 
char m[40][60];//数组大小要比输入矩阵大 
int dist[40][60];
char dir[4]={'D','L','R','U'};

bool check(int y,int x){
	return y>=1&&y<=30&&x>=1&&x<=50&&m[y][x]=='0'&&dist[y][x]==-1;
}

//广度优先搜索 
void bfs(){
	queue<pair<int,int>>q;//用队列实现广度优先搜索 
	memset(dist,-1,sizeof(dist));//初始化数组为全-1 
	dist[30][50]=0;//{30,50}就是终点 
	q.push({30,50});
	while(!q.empty()){
		pair<int,int>p=q.front();
		q.pop();
		for(int i=0;i<4;++i){
			int y=p.first+dy[i];
			int x=p.second+dx[i];
			if(check(y,x)){//判断是否符合向前搜索条件 
				dist[y][x]=dist[p.first][p.second]+1;//离终点的距离+1 
				q.push({y,x});
			}
		} 
	} 
}

int main() {
	for(int i=1;i<=30;++i){
		for(int j=1;j<=50;++j){
			cin>>m[i][j];
		}
	}
	
	bfs();
	int y=1,x=1;
	string res;
	while(y!=30||x!=50){//保证到达{30,50}即终点才结束循环
		for(int i=0;i<4;++i){
			int _y=y+dy[i];
			int _x=x+dx[i];
			if(_y>=1&&_y<=30&&_x>=1&&_x<=50&&m[_y][_x]=='0'&&dist[_y][_x]==dist[y][x]-1){
				y=_y;
				x=_x;
				res+=dir[i];
				break;
			}
		} 
	}
	cout<<res;
	return 0;
}

解决代码：

#include <iostream>
using namespace std;
int main()
{ cout<<"DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR";
  return 0;
}

【真题练习】跳蚱蜢

$\textcolor{red}{分析：}$

采用queue队列实现bfs遍历，由初始态012345678到目标087654321；

因为蚱蜢很多，跳蚱蜢很复杂，因此建议跳空盘，更好理解；

注意根据题意知，应该有4中跳法：顺时针跳1步、顺时针跳2步、逆时针跳1步、逆时针跳2步；

可以采用set和map进行去重以及判断是否达到了最后的目标。

$\textcolor{red}{注意：}$

将反方向的-2到达的位置，转换为正方向下的位置坐标7。int k=(j+9)%9;

计算代码：

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

struct node{
	node(string ss,int tt){//构造函数 
		s=ss;
		t=tt;
	}
	string s;//当前状态,比如：012345678 
	int t;//跳跃次数 
};

queue<node>q;//辅助完成bfs 
map<string,bool>h;//去重并判断是否达到目标结果 

//处理函数 
void solve(){//采用广度优先搜索 
	while(!q.empty()){
		node now=q.front();
		q.pop();
		string s=now.s;
		int step=now.t;
		if(s=="087654321"){//找到最终结果 
			cout<<s<<endl;
			cout<<step;//最终结果 
			break;
		}
		//i是源位置，k是目标位置 
		int i;
		for(i=0;i<9;++i){//找到空盘的位置i
			if(s[i]=='0')break;
		}
		for(int j=i-2;j<=i+2;++j){//四种跳法 
			int k=(j+9)%9;	//将反方向的-2到达的位置，转换为正方向下的位置坐标7
			if(k==i)continue;	//避免重复计算 
			string news=s;
			//交换位置i与位置k的值 
			swap(news[i],news[k]);
			if(!h[news]){//不存在此种情况，则添加到h中 
				h[news]=true;
				q.push(node(news,step+1));
			}
		} 
	}
} 

int main() {
	string s="012345678";
	q.push(node(s,0));
	h[s]=true;
	solve();
	return 0;
}

解决代码：

#include <iostream>
using namespace std;
int main()
{
  cout<<20;
  return 0;
}

【真题练习】七段码

$\textcolor{red}{分析：}$

经典七段码问题，用到邻接矩阵以及回溯法

计算代码：

#include<bits/stdc++.h>
using namespace std;
// 经典七段码问题，用到邻接矩阵以及回溯法 
//int graph[7][7],visit[7];


int backTrack(int graph[][7], int visit[], int n, int i){// n:7, i:起始边 
	int count = 1;
	for(int x = 0;x < n;++x){
		if(graph[i][x] != 0&&visit[x] != 1){// 找到未遍历到的相邻边 
			visit[x] = 1;
			count += backTrack(graph, visit, n, x);// 递归
			visit[x] = 0;// 回溯 
		}
	}
	return count;
} 

int main() {
	int graph[7][7] = {
	{1, 1, 0, 0, 0, 1, 0},
	{1, 1, 1, 0, 0, 0, 1},
    {0, 1, 1, 1, 0, 0, 1},
    {0, 0, 1, 1, 1, 0, 0},
    {0, 0, 0, 1, 1, 1, 1},
    {1, 0, 0, 0, 1, 1, 1},
    {0, 1, 1, 0, 1, 1, 1}
	};
	int visit[7] = {0};
	cout<<backTrack(graph, visit, 7, 0)/2;// 除2是因为前面重复计算了
	return 0;
}

解决代码：

#include <iostream>
using namespace std;
int main()
{
  cout<<80;
  return 0;
}

【真题练习】N皇后问题

$\textcolor{red}{分析：}$

N皇后问题使用回溯法解决；

关键是要正确表示左右斜线；（左斜线：k=i+j；右斜线：k=i-j+N-1）

在每次放置皇后的时候必须保证当前位置的同一行（这里不用定义数组，直接根据递归回溯来限制同一行只能有一个皇后）、同一列（定义bool型的col[N]）以及左右斜线上（定义bool型R[2 * N],L[2 * N]）没有放置过皇后；

每放置一个位置M[i][j]就更新对应的col[j],R[i-j+N-1],L[i+j]。

解决代码：

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

int N;
int counts = 0;// 计数

int N_queens(int i, vector<vector<int>>&M, int col[], int L[], int R[]){
	for(int j = 0;j < N;++j){// 遍历每一行的位置 
		if(!col[j]&&!R[i-j+N-1]&&!L[i+j]){// 可放置 
			M[i][j] = i+1;// 放置皇后 
			col[j] = L[i+j] = R[i-j+N-1] = 1;
			if(i == N-1){
				counts++;// 放置方法加1 
			}else{
				N_queens(i+1, M, col, L, R);
			}
			M[i][j] = 0;// 回溯-去皇后 
			col[j] = L[i+j] = R[i-j+N-1] = 0;
		}
	} 
	return counts;
}

int main() {
	cin>>N;
	vector<vector<int>>M(N, vector<int>(N, 0));// 采用int M[N][N]，不方便给函数传参，这里要用vector动态数组 
	int col[N]={0}, L[2*N]={0}, R[2*N]={0};// 1则表明存储皇后 
//	count = 0;// 计数 
	int n = N_queens(0, M, col, L, R);
	cout<<n;// 可行解数量 
	return 0;
}

第五天

【真题练习】一元三次方程求解

$\textcolor{red}{分析：}$

本题由于范围和进度较小可以使用暴力求解的方式解决；

二分法，根据根与根之间差的绝对值大于等于1，因此可以简化问题：将[-100,100]划分为200个小区间，在小区间内进行二分搜索。

$\textcolor{red}{注意：}$

涉及到输出精度的问题，尽量使用C的标准输出printf("%.2lf ", (i+j)/2)，C++的setprecision有点问题；

解决代码：

1、暴力求解：

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

double a,b,c,d;

double y(double x){
	return a*x*x*x+b*x*x+c*x+d;
} 

int main() {
	scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
	for(double i = -100;i <= 100;i += 0.01){
		double j = i + 0.01;
		double y1 = y(i),y2 = y(j);
		if(y1*y2 <= 0){
			printf("%.2lf ", (i+j)/2);
		}
	}
	return 0;
}

2、二分法：

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

double a,b,c,d;

double y(double x){
	return a*x*x*x+b*x*x+c*x+d;
} 

int main() {
	cin>>a>>b>>c>>d;
//	scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
//-------------二分法----------------------
	for(int i =- 100;i <= 100;++i){
		double left = i,right = i+1;
		double y1 = y(left),y2 = y(right);
		if(y1 == 0)printf("%.2lf ", left);// 左端点 
		if(y1*y2<0){// <0表示小区间内存在根 
			for(int j=0;j<100;++j){// 将长度为1的区间划分为100份，也就是每一小份都是0.01 
				double mid = left + (right - left)/2;
				if(y(mid)*y(right)<=0){
					left = mid;
				}else{
					right = mid;
				}
			}
			printf("%.2lf ", right);
		}
	} 
	return 0;
}

【真题练习】解立方根

$\textcolor{red}{分析：}$

本题简单，使用pow理论上可以求出所有的N次根。

解决代码：

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

double Three_sqrt(double N){
	return pow(N, 1.0/3.0);// 使用pow实现 
}

int main() {
	int T, N;
	cin>>T;
	for(int i=0;i<T;++i){
		cin>>N;
		printf("%.3lf\n", Three_sqrt(N));
	}
	return 0;
}

【真题练习】分巧克力

$\textcolor{red}{分析：}$

定义切出的巧克力的边长为d；

暴力解的话就是将d从1开始遍历，一直到不能够满足分出k块巧克力为止，复杂度为O(n*d)，超时；

可以使用二分法进行简化，复杂度为O(log₂d)；

解决代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+1;
int h[N],w[N];
int n, k;
int d;// 最大边长 

// 判断是否能够满足分巧克力的条件
bool check(int d){
	int num = 0;
	for(int i=0;i<n;++i){
		num += (h[i]/d)*(w[i]/d);// 计算每块巧克力能够分为多少块正方形 
	}// (h[i])*(w[i])/(d*d)的形式是不可行的，不符合切巧克力的条件 
	if(num>=k)return true;
	return false;
} 


int main() {
	cin>>n>>k;
	for(int i=0;i<n;++i){
		cin>>h[i]>>w[i];
	} 
	int l = 1, r = N;
	while(l<r){
		int mid = (l+r+1)>>1;// 右移一位，表示除以2，+1:表示向右取整 
		if(check(mid))l = mid;
		else r = mid - 1;// 因为前面mid是向右取整的，因此取右边界的时候需要-1 
	}
	// 以上步骤也可以使用mid向左取整来解决 
	cout<<l;
	return 0;	
}

第六天

C++贪心算法的基本思想是在每个决策点上，都采取当前最优的选择，从而希望能够得到全局最优解。具体来说，贪心算法通常包含以下步骤：

将问题分解为若干个子问题；

对每个子问题进行求解，找到它的最优解；

合并各个子问题的解成原问题的解。

在实际应用中，贪心算法常常需要结合具体问题进行设计和优化。因为贪心算法只考虑局部最优解，并不保证得到全局最优解。对于一些问题，贪心算法可以得到最优解，但对于一些复杂问题，贪心算法可能无法得到最优解，此时需要使用其他算法。

【真题练习】翻硬币

$\textcolor{red}{分析：}$

通过思考可以发现，我们每次的操作都会满足以下两个特性：

必要性：只有当被操作的硬币状态和目标状态不同时，才进行操作；

独立性：不会影响已处理好（达到目标状态）的硬币。

显然，满足了必要性和独立性的操作，即最优操作。每次都使用最优操作，那么总的操作次数就会是最少的。

解决代码：

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

//每次的操作都会满足以下两个特性：
//1. 必要性：只有当被操作的硬币状态和目标状态不同时，才进行操作；
//2. 独立性：不会影响已处理好（达到目标状态）的硬币。

int main() {
	string s1, s2;
	cin>>s1;
	cin>>s2;
	int num=0;
	for(int i=0;i<s1.size()-1;++i){
		if(s1[i]!=s2[i]){// s1[i]经过改变之后必定变为目标态，只对s1[i+1]修改即可 
			if(s1[i+1]=='*')s1[i+1]='o'; 
			else s1[i+1]='*';
			num++;
		}
	} 
	cout<<num;
	return 0;
}

【真题练习】巧克力

$\textcolor{red}{分析：}$

第一个是要对输入的n种巧克力进行排序；

第二个是要将保质期到len的巧克力安排在第len天，如果已经安排，则往前面安排；

$\textcolor{red}{注意：}$

因为本题数据量大，使用int会存储数据溢出，因此可以使用using ll = long long;或者是#define int long long来解决数据溢出的问题；

同时应该注意的是使用#define int long long之后，需要将main()函数的类型从int改为signed，否则会报main函数返回类型错误。

解决代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+10;

struct choc {
	int price;// 巧克力价格
	int len;// 保质期到
	int cnt;// 巧克力数量
	bool operator < (const choc&b) { // 重载<符号的原因是sort默认就是使用<符号来实现排序的
		if(price == b.price)return len>b.len;// 价格相等，则按保质期的长度降序
		return price<b.price;// 按价格升序
	}
} a[N];

signed main() {// 在 #define int long long之后，main()函数不能够再定义为int了，而定义为signed：表示有符号的 
	int x, n;
	cin>>x>>n;
	int total = 0;// 存储最后的花费
	for(int i=1; i<=n; ++i) {
		cin>>a[i].price>>a[i].len>>a[i].cnt;
	}
	sort(a+1, a+1+n);// 排序
	set<int>date;// 存储未安排巧克力的日期
	for(int i=1; i<=x; ++i) {
		date.emplace(i);
	}
	int per = 1;
	while(per<=n && date.size()) {
		while(a[per].cnt && date.size() && *date.begin() <= a[per].len) {
			total += a[per].price;
			a[per].cnt--;
			auto iter = date.upper_bound(a[per].len);// 在未安排巧克力的日期中找到第一个大于目标值的位置
			iter--;
			date.erase(iter);// 安排巧克力之后需要删除
		}
		per++;
	}
	if(date.size()) {
		cout<<-1;
	} else cout<<total;
	return 0;
}

【真题练习】答疑

$\textcolor{red}{分析：}$

根据题设条件进行推导，可以知道假设第一个人先进去答疑，第二个人随后进去答疑，可以得到： $s_1+a_1+e_1<s_2+a_2+e_2$ ，根据这个不等式对输入数据进行排序。

根据排序好的顺序进行求和，第i个人的对总量的贡献通式为： $(n-i+1) \times (s_i+a_i)+(n-i)\times e_i$ .

解决代码：

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

using ll = long long;

struct node{
	ll s, a, e;
	bool operator < (const node& b){
		return s+a+e<b.s+b.a+b.e;
	}
}; 
vector<node>vec;

int main() {
	int n;
	cin>>n;
	ll s, a, e;
	for(int i=0;i<n;++i){
		cin>>s>>a>>e;
		vec.push_back({s, a, e});
	}
	sort(vec.begin(), vec.end());
	ll ans = 0;
	for(int i=0;i<n;++i){
		ans += (n-i)*(vec[i].s+vec[i].a) + (n-i-1)*vec[i].e;// 这里的i是从0开始的，推导过程中是从1开始的 
	}
	cout<<ans;
	return 0;
}

【真题练习】顺子日期

$\textcolor{red}{分析：}$

首先注意2022年的2月只有28天；

在2022年份中存在的顺子只可能是012、123；

枚举2022年份并检查是否存在012、123即可；

计算代码：

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

int nums[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};// 存储1-12月份的天数

bool check(int year, int month, int day) {
	string s = to_string(year);
	if(month<10) {
		s += '0';
	}
	s += to_string(month);
	if(day<10) {
		s += '0';
	}
	s += to_string(day);
//	for(auto e:s) {
//		cout<<e;
//	}
	cout<<endl;
	if(s.find("012")!=s.npos||s.find("123")!=s.npos)return true;// find函数返回的是npos 
	return false;
}

int main() {
	int ans = 0;
	for(int month=1; month<=12; ++month) {
		for(int day=1; day<=nums[month]; ++day) {
			if(check(2022, month, day)) {
				ans++;
			}
		}
	}
	cout<<ans;
	return 0;
}

解决代码：

#include <iostream>
using namespace std;
int main()
{
  cout<<14;
  return 0;
}

【真题练习】特殊时间

$\textcolor{red}{分析：}$

共有三个4位数字组成，每个4位数字都只有两个不相等整数组成，不妨设为a，b；

因此每个4位数字只可能是aaab、aaba、abaa、baaa四种可能，对于year来说，它恒有4种情况；而对于月日以及时分来说需要对以上4种情况判断是否符合实际时间；

闰年的2月有29天，但是29这两个数字不能够组成合法日期，所以可以直接考虑2月只有28天的情况。

计算代码：

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

int nums[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool check_md(int num){
	int month = num/100;
	int day = num%100;
	if(month<1||month>12)return false;
	if(day<1||day>nums[month])return false;
	return true;
}

bool check_hm(int num){
	int h = num/100;// 取前两位 
	int m = num%100;// 取后两位 
	if(h<0||h>23)return false;
	if(m<0||m>59)return false;
	return true;
}

int main() {
	int ans = 0;
	for(int a=0;a<=9;a++){
		for(int b=0;b<=9;b++){
			if(a!=b){
				int N_y = 4, N_md = 0, N_hm = 0;
				int A[] = {a, a, a, a};
				for(int i=0;i<4;++i){
					A[i] = b;
					int num = 0;
					for(int j=0;j<4;++j)num = 10*num + A[j];
					N_md += check_md(num);
					N_hm += check_hm(num);
					A[i] = a;// 还原 
				}
				ans += N_y*N_md*N_hm;
			}
		}
	}
	cout<<ans;
	return 0;
}

解决代码：

#include <iostream>
using namespace std;
int main()
{
  // 请在此输入您的代码
  cout<<212;
  return 0;
}

【真题练习】乘积尾零

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

如下的 1010 行数据，每行有 1010 个整数，请你求出它们的乘积的末尾有多少个零？

5650 4542 3554 473 946 4114 3871 9073 90 4329 
2758 7949 6113 5659 5245 7432 3051 4434 6704 3594 
9937 1173 6866 3397 4759 7557 3070 2287 1453 9899 
1486 5722 3135 1170 4014 5510 5120 729 2880 9019 
2049 698 4582 4346 4427 646 9742 7340 1230 7683 
5693 7015 6887 7381 4172 4341 2909 2027 7355 5649 
6701 6645 1671 5978 2704 9926 295 3125 3878 6785 
2066 4247 4800 1578 6652 4616 1113 6205 3264 2915 
3966 5291 2904 1285 2193 1428 2265 8730 9436 7074 
689 5510 8243 6114 337 4096 8199 7313 3685 211

$\textcolor{red}{分析：}$

Python可以直接暴力求解；

C++需要考虑数据溢出问题，因为10=2*5，在所有数中因子为5的个数一定比因子为2的个数少，因此计算因子为5的个数即为尾零的个数。

解决代码：

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

int main() {
	int x, ans = 0;
	for(int i=0; i<100; ++i) {
		cin>>x;
		while(x%5==0) {
			ans++;
			x/=5;
		}
	}
	cout<<ans;
	return 0;
}

【真题练习】平方和

$\textcolor{red}{分析：}$

通过求余和整除得到每一位的数字并判断是否为2、0、1、9，如果有，则直接平方求和；

解决代码：

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

int main() {
	ll ans = 0;
	for(ll x=1; x<=2019; ++x) {
		ll temp = x;
		while(temp>0) {
			if(temp%10==2||temp%10==1||temp%10==0||temp%10==9) {
				ans += x*x;// 平方和
				break;
			}
			temp /= 10;
		}
	}
	cout<<ans;
	return 0;
}

Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.