2022年第十三届蓝桥杯C++B组国赛思路以及部分代码

ฅ(๑˙o˙๑)ฅ 大家好, 欢迎大家光临我的博客：面向阿尼亚学习
算法学习笔记系列持续更新中~

• 一、前言
• 二、2021年蓝桥杯c++b组国赛真题目录
• • A:2022 [5分]
  • • 思路⭐
    • 代码
  • B 钟表 (5分)
  • • 思路⭐
    • 代码
  • C 卡牌(10分)
  • • 思路⭐
    • 代码
  • D 最大数字 (10分)
  • • 思路⭐
    • 代码
  • E 出差 (15分)
  • • 思路⭐
    • 代码
  • F 费用报销 (15分)
  • • 思路⭐
    • 代码
  • G 故障 (20分)
  • • 思路⭐
    • 代码
  • H 机房 (20分)
  • • 思路⭐
    • 代码
  • I 齿轮 (25分)
  • • 思路⭐
    • 代码
  • J 搬砖 (25分)
  • • 思路⭐
    • 代码
• 最后

本人第一年打蓝桥杯，体验感还算可以

个人感觉5分填空题比编程题还要难（开考暴击）
不过稳定住心态，后面的编程题还是可以拿分的

主要考察了：动态规划，以及前几届很少考的最短路问题
暴力杯转型DP杯了

注意：由于目前没有地方可以测，以下代码不保证AC

正解会补的，待我考完试~
也欢迎大家评论补充

A，B为填空题

暴力跑四个小时也跑不出来
正解：动态规划
开局先给你来个动态规划开开胃

#include 
using namespace std;
typedef long long LL;

LL dp[11][2025];

int main()
{
	dp[0][0]=1;
	for(int i=1;i<=2022;i++)
	{
		for(int j=10;j>=1;j--)
			for(int k=1;k<=2022;k++)
				if(k>=i)dp[j][k]+=dp[j-1][k-i];
		}
		cout< 
答案：379187662194355221
 
B 钟表 (5分) 
 
思路⭐ 
模拟钟表
 注意精度问题
 模拟题再恶心你一下
 
代码 
#include 
#include 
using namespace std;
int main()
{
	for(int s=0;s<=6;s++)
	{
		for(int f=0;f<60;f++)
		{
			for(int m=0;m<60;m++)
			{
				double mm=m/60.*360;
				double ff=f/60.*360+mm/60;
				double ss=s/12.*360+ff/12;
				double A=abs(ff-ss),B=abs(ff-mm);
				A=min(A,360-A);B=min(B,360-B);
				if(fabs(A-2*B)<1e-5)
				{
					cout< 
答案：4 48 0
 0 0 0不算（比赛时发的公告）
 
 
以下为编程题
 
C 卡牌(10分) 

 
 
思路⭐ 
正解：二分
 
代码 
#include 
using namespace std;
const int N=2e5+10;
int a[N],b[N],c[N];
int n,m;
bool check(int x) {
	int res=0;
	for(int i=1; i<=n; i++) {
		if(a[i]+b[i]=a[i])
			res+=x-a[i];
	}
	return res<=m;
}
int main() {
	cin>>n>>m;
	for(int i=1; i<=n; i++)cin>>a[i];
	for(int i=1; i<=n; i++)cin>>b[i];
	int l=0,r=1e9;
	while(l
		int mid=l+r+1>>1;
		if(check(mid))
			l=mid;
		else
			r=mid-1;
	}
	cout< 
D 最大数字 (10分) 

 
 
思路⭐ 
正解：动态规划
 再给你来个动态规划
 
代码 
待补
 
 
E 出差 (15分) 

 
 
思路⭐ 
裸的单源最短路问题
 正解：Dijkstra算法
 两点间的距离为路程的天数加目的地隔离的天数
 
代码 
#include
#include
#include
using namespace std;

const int N=1007;

int a[N];
int g[N][N];
int dist[N];
bool st[N];

int n,m;

int Dijkstra() {
	memset(dist, 0x3f,sizeof dist);

	dist[1]=0;

	for(int i=0; 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;

		for(int j=1; j<=n; j++)
			dist[j]=min(dist[j],dist[t]+g[t][j]);
	}

	if(dist[n]==0x3f3f3f3f) return -1;

	return dist[n];
}
int main() {
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
	}

	a[1]=0;
	a[n]=0;


	memset(g,0x3f,sizeof g);

	while(m--) {
		int x,y,z;
		cin>>x>>y>>z;
		g[x][y]=min(g[x][y],z+a[y]);
		g[y][x]=min(g[y][x],z+a[x]);
	}

	cout< 
F 费用报销 (15分) 

 
 
思路⭐ 
正解：动态规划
 hhh还是动态规划
 
代码 
我觉得我有必要练一下动态规划
 
G 故障 (20分) 

 
 
 
思路⭐ 
正解：贝叶斯公式
 
代码 
菜鸡不理解
 
H 机房 (20分) 

 
 
思路⭐ 
正解：树的最近公共祖先
 
代码 
我跑到最短路，非正解
 
#include 
using namespace std;

const int N = 100007, INF = 1e9;
int mx[N];
int my[N];
int n, m, x, y;
int d[N][N];
int a[N];
void floyd() {
	for(int k = 1; k <= n; k++)
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			d[i][j] = INF;

	for(int i=0; i
		cin>>x>>y;
		mx[i]=x;
		my[i]=y;
		a[x]++;
		a[y]++;
	}


	for(int i=0; i
		d[mx[i]][my[i]]=min(d[mx[i]][my[i]],a[my[i]]);
		d[my[i]][mx[i]]=min(d[my[i]][mx[i]],a[mx[i]]);
	}


	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			if(i==j)
				d[i][j]=min(d[i][j],a[j]);
		}
	}
	floyd();
	while(m--) {
		cin >> x >> y;

		if(x==y)
			cout< 
I 齿轮 (25分) 

 
 
思路⭐ 
齿轮间的线速度是相同的
 所以只需要找最左边齿轮与最右边齿轮半径成倍数的就可以
 
代码 
我这里用set来找的，应该会超
 
#include 
#include 
#include 
using namespace std;
int main() {
	int n,q;
	cin>>n>>q;
	set  s;
	for(int i=0; i
		int a;
		cin>>a;
		s.insert(a);
	}
	
	while(q--) {
		int x;
		cin>>x;
bool g=1;
		set::iterator it=s.begin();
		for(;it!=s.end();it++) 
		{
			if(s.count((*it)*x)==1)
			{
				cout<<"YES"< 
J 搬砖 (25分) 

 
 
思路⭐ 
按重量价值和进行排序，再进行动态规划
 
代码 
正解待补~
 
最后 
莫言真理无穷尽，寸进自有寸进欢