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

---

---

一、前言

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

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

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

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

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

---

二、2022年蓝桥杯c++b组国赛真题目录

A，B为填空题

A:2022 [5分]

思路⭐

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

代码🌟

#include <iostream>
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<<dp[10][2022]<<endl;
}

答案：379187662194355221

B 钟表 (5分)

思路⭐

模拟钟表
注意精度问题
模拟题再恶心你一下

代码🌟

#include <iostream>
#include <cmath>
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<<s<<" "<<f<<" "<<m<<endl;
				}
			}
		}
	}
}

答案：4 48 0
0 0 0不算（比赛时发的公告）

---

以下为编程题

C 卡牌(10分)

思路⭐

正解：二分

代码🌟

#include <iostream>
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]<x)
			return 0;
		if(x>=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<r) {
		int mid=l+r+1>>1;
		if(check(mid))
			l=mid;
		else
			r=mid-1;
	}
	cout<<l<<endl;
	return 0;
}

D 最大数字 (10分)

思路⭐

正解：动态规划
再给你来个动态规划

代码🌟

待补

---

E 出差 (15分)

思路⭐

裸的单源最短路问题
正解：Dijkstra算法
两点间的距离为路程的天数加目的地隔离的天数

代码🌟

#include<iostream>
#include<algorithm>
#include<cstring>
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<n; 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<<Dijkstra()<<endl;
	return 0;
}

F 费用报销 (15分)

思路⭐

正解：动态规划
hhh还是动态规划

代码🌟

#include <iostream>
using namespace std;
int n,m,k,x,y,z;
const int N=1e5+7;
int mp[105][105];
int dp[N];
int d[13]= {0,31,28,31,30,31,30,31,31,30,31,30,31};
int main() 
{
	int sum=0;
	for(int i=1; i<=12; i++)
	{
		for(int j=1; j<=d[i]; j++)
	    {
			sum++;
			mp[i][j]=sum;
		}
	}
	cin>>n>>m>>k;
	for(int i=1; i<=n; i++) 
	{
		cin>>x>>y>>z;
		dp[mp[x][y]]=max(dp[mp[x][y]],z);
	}
	for(int i=1; i<=500; i++)
	 {
		if(dp[i]+dp[max(0,i-k)]<=m)
			dp[i]=max(dp[i]+dp[max(0,i-k)],dp[i-1]);
		else
			dp[i]=dp[i-1];
	}
	cout<<dp[500]<<endl;
	return 0;
}

G 故障 (20分)

思路⭐

正解：贝叶斯公式

代码🌟

菜鸡不理解

H 机房 (20分)

思路⭐

正解：树的最近公共祖先

代码🌟

我跑到最短路，非正解

#include <iostream>
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<n-1; i++) {
		cin>>x>>y;
		mx[i]=x;
		my[i]=y;
		a[x]++;
		a[y]++;
	}


	for(int i=0; i<n-1; 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<<d[x][y]<<endl;
		else
			cout << d[x][y] +a[x]<< endl;
	}
	return 0;
}

I 齿轮 (25分)

思路⭐

齿轮间的线速度是相同的
所以只需要找最左边齿轮与最右边齿轮半径成倍数的就可以

代码🌟

我这里用set来找的，应该会超

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
int main() {
	int n,q;
	cin>>n>>q;
	set <int> s;
	for(int i=0; i<n; i++) {
		int a;
		cin>>a;
		s.insert(a);
	}
	
	while(q--) {
		int x;
		cin>>x;
     bool g=1;
		set<int>::iterator it=s.begin();
		for(;it!=s.end();it++) 
		{
			if(s.count((*it)*x)==1)
			{
				cout<<"YES"<<endl;
				g=0;
				break;
			}
		}
		if(g==1)
		cout<<"NO"<<endl;
		
	}
	return 0;
}

J 搬砖 (25分)

思路⭐

按重量价值和进行排序，再进行动态规划

代码🌟

正解待补~

最后

莫言真理无穷尽，寸进自有寸进欢