第16届蓝桥杯c++省赛c组个人题解

偷偷吐槽：

        c组没人写题解吗，找不到题解啊

P12162 [蓝桥杯 2025 省 C/研究生组] 数位倍数

题目背景

本站蓝桥杯 2025 省赛测试数据均为洛谷自造，与官方数据可能存在差异，仅供学习参考。

题目描述

请问在 1 至 202504（含）中，有多少个数的各个数位之和是 5 的整数倍。

例如：5、19、8025 都是这样的数。

输入格式

无

输出格式

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

输入输出样例

无

思路：

        模拟

#include<bits/stdc++.h>
using namespace std;
bool check(int x){int num=0;while(x){num+=x%10;x/=10;}if(num%5==0)return 1;return 0;
}
int main(){int ans=0;for(int i=1;i<=202504;++i){if(check(i))ans++;}cout<<ans;
}

P12163 [蓝桥杯 2025 省 C] 2025

题目描述

求 1∼20250412 中，有多少个数可以通过改变其数字顺序后含有 2025。

例如，5220、21520 可以，而 205、225、2200、222555111 则不行。

提示：要求的数就是含有至少 1 个 0、2 个 2、1 个 5 的数。

输入格式

无

输出格式

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

输入输出样例

无

思路：

        模拟

#include<bits/stdc++.h>
using namespace std;
int a[10];
bool check(long long x){memset(a,0,sizeof a);while(x){a[x%10]++;x/=10;}if(a[0]>=1&&a[2]>=2&&a[5]>=1)return 1;return 0;
}
int main(){int ans=0;for(int i=1;i<=20250412;++i){if(check(i))ans++;}cout<<ans;
}

P12164 [蓝桥杯 2025 省 C/Python A] 2025 图形

题目背景

本站蓝桥杯 2025 省赛测试数据均为洛谷自造，与官方数据可能存在差异，仅供学习参考。

题目描述

小蓝要画一个 2025 图形。图形的形状为一个 h×w 的矩形，其中 h 表示图形的高，w 表示图形的宽。当 h=5,w=10 时，图形如下所示：

2025202520
0252025202
2520252025
5202520252
2025202520

图形的规律是：第一行用 2025 重复填入，第二行开始，每行向左移动一个字符，用 2025 重复填入。 给定 h,w，请输出对应的图形。

输入格式

输入的第一行包含两个正整数 h,w，用一个空格分隔。

输出格式

输出若干行，表示对应的图形。

输入输出样例

输入 #1复制

4 5

输出 #1复制

20252
02520
25202
52025

说明/提示

评测用例规模与约定

• 对于 30% 的评测用例，h=1，1≤w≤20；
• 对于 60% 的评测用例，1≤h,w≤20；
• 对于所有评测用例，1≤h,w≤100

思路：

        模拟，顺便说一句他给的pdf差点看成带空格的

#include<bits/stdc++.h>
using namespace std;
string a[4]={"2025","0252","2520","5202"};
int h,w;
int main(){cin>>h>>w;for(int i=0;i<h;++i){for(int j=0;j<w;++j){cout<<a[i%4][j%4];}cout<<"\n";}
}

P12165 [蓝桥杯 2025 省 C] 最短距离

题目描述

在一条一维的直线上，存在着 n 台显示器和 n 个电源插座。老师给小蓝布置了个任务：负责将每台显示器通过电源线与一个插座相连接（每个插座最多只能给一台显示器供电）；同时，老师希望所消耗的电源线的长度尽可能的少，请你帮小蓝计算下电源线的最小消耗长度为多少？

为了便于计算，你只需要考虑直线距离即可。

输入格式

输入的第一行包含一个正整数 n。

接下来 n 行，每行包含一个整数 xi​，依次表示每台显示器的坐标。

接下来 n 行，每行包含一个整数 yi​，依次表示每个插座的坐标。

输出格式

输出一行包含一个整数表示答案。

输入输出样例

输入 #1复制

2
0
1
2
3

输出 #1复制

4

说明/提示

评测用例规模与约定

• 对于 20% 的评测用例，1≤n≤10，0≤xi​,yi​≤100；
• 对于 40% 的评测用例，1≤n≤100，0≤xi​,yi​≤103；
• 对于 60% 的评测用例，1≤n≤1000，0≤xi​,yi​≤105；
• 对于 80% 的评测用例，1≤n≤10000，0≤xi​,yi​≤109；
• 对于所有评测用例，1≤n≤50000，0≤xi​,yi​≤109。

思路：

        记得开longlong，贪心

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int a[N],b[N];
int main(){int n;cin>>n;for(int i=1;i<=n;++i)cin>>a[i];for(int i=1;i<=n;++i)cin>>b[i];sort(a+1,a+1+n);sort(b+1,b+1+n);long long ans=0;for(int i=1;i<=n;++i){ans+=abs(a[i]-b[i]);}cout<<ans;
}

P12167 [蓝桥杯 2025 省 C/Python A] 倒水

题目描述

小蓝有 n 个装了水的瓶子，从左到右摆放，第 i 个瓶子里装有 ai​ 单位的水。为了美观，小蓝将水循环染成了 k 种颜色，也就是说，第 i 个瓶子和第 i+k 个瓶子里的水的颜色相同。

小蓝发现有的瓶子里的水太少了，因此他规定如果第 i 个瓶子和第 j 个瓶子中的水颜色相同并且满足 i<j，即可将任意整数单位的水从第 i 个水瓶倒出，倒入第 j 个水瓶中。小蓝想知道任意次操作后所有瓶子中的水的最小值 min{ai​} 最大可以是多少？

输入格式

输入的第一行包含两个正整数 n,k，用一个空格分隔。

第二行包含 n 个正整数 a1​,a2​,⋯,an​，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

输入输出样例

输入 #1复制

7 3
8 5 5 2 2 3 4

输出 #1复制

3

说明/提示

样例说明

其中一种方案：

• a1​ 往 a4​ 倒入 3 单位；
• a2​ 往 a5​ 倒入 2 单位；
• a3​ 往 a6​ 倒入 1 单位； 最终每个瓶子里的水：5,3,4,5,4,4,4，最小值为 3。

评测用例规模与约定

• 对于 40% 的评测用例，1≤n,ai​≤100；
• 对于所有评测用例，1≤n,ai​≤100000，1≤k≤n。

思路：

又是熟悉的蓝桥阅读理解，不知道能得几分，考场上写单调栈去了

只有k相同的才能给水

1 1+k 1+2k

2 2+k 3+k 等

只有前面的水杯可以给后面的水杯，后面的水杯给不了前面，如果能给就是整个区间的平均数

题目要求的是最大的最小水，也就是前面大的要给后面小的水以至于达到平均的

一个水杯加进来有两种情况， 大于等于 平均数会变大，为什么因为后面小的水他可以多给

小于 平均数会变小，与上面同理

#include<bits/stdc++.h>
using namespace std;
long long a[100005];
int main(){int n,k;cin>>n>>k;for(int i=1;i<=n;++i){cin>>a[i];}long long ans=12e9;for(int i=1;i<=k;++i){long long sum=a[i];long long num=a[i];int cnt=1;num=min(num,a[i]);for(int j=i+k;j<=n;j+=k){cnt++;sum+=a[j];if(a[j]<num){num=min(num,sum/cnt);   }}ans=min(ans,num);}cout<<ans;
}

P12166 [蓝桥杯 2025 省 C/研究生组] 冷热数据队列

题目描述

冷热数据队列 q 可以看做由两个子队列组成：长度为 n1​ 的热数据队列 q1​ 和长度为 n2​ 的冷数据队列 q2​。当我们需要访问某个数据页 p 时：

1. 若 p 不在队列 q 中（即既不在 q1​ 中，也不在 q2​ 中），则加载数据页 p，并插入到 q2​ 的首部。
2. 若 p 已经在队列 q 中，则将 p 移动至 q1​ 首部。
3. 当 q1​ 或 q2​ 队列容量不足时，会将其尾部的数据页淘汰出去。
4. 当 q1​ 已满，但 q2​ 未满时，从 q1​ 中淘汰出的数据页会移动到 q2​ 首部。

输入格式

输入的第一行包含两个正整数 n1​,n2​，用一个空格分隔。

第二行包含一个整数 m，表示操作次数。

第三行包含 m 个正整数 v1​,v2​,⋯,vm​，表示依次访问到的数据页的编号，相邻整数之间使用一个空格分隔。

输出格式

输出两行。

第一行包含若干个整数，相邻整数之间使用一个空格分隔，依次表示 q1​ 中的数据页。

第二行包含若干个整数，相邻整数之间使用一个空格分隔，依次表示 q2​ 中的数据页。

输入输出样例

输入 #1复制

3 3
10
1 2 3 4 3 2 2 1 3 4

输出 #1复制

4 3 2
1

说明/提示

样例说明

i	vi​	q1​	q2​
−	−	[]	[]
1	1	[]	[1]
2	2	[]	[2,1]
3	3	[]	[3,2,1]
4	4	[]	[4,3,2]
5	3	[3]	[4,2]
6	2	[2,3]	[4]
7	2	[2,3]	[4]
8	1	[2,3]	[1,4]
9	3	[3,2]	[1,4]
10	4	[4,3,2]	[1]

评测用例规模与约定

• 对于 20% 的评测用例，1≤n1​,n2​≤10，1≤m≤10；
• 对于 40% 的评测用例，1≤n1​,n2​≤20，1≤m≤100；
• 对于 60% 的评测用例，1≤n1​,n2​≤100，1≤m≤1000；
• 对于 80% 的评测用例，1≤n1​,n2​≤103，1≤m≤104；
• 对于所有评测用例，1≤n1​,n2​≤104，1≤m≤105，0≤vi​≤104。

思路：

        模拟

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int n1, n2;
int m;
int q1[N], q2[N];
int tt1=-1,s1=0;
int tt2 = -1, s2 = 0;
int a[N];
int main(){cin >> n1 >> n2;cin >> m;for (int i = 1; i <= m;++i){int x;cin >> x;if(a[x]==0){q2[++tt2] = x;if(tt2-s2+1>n2){a[q2[s2]] = 0;s2++;}a[x] = 2;}else if(a[x]==1){int j;for (j = s1; j <= tt1;++j){if(q1[j]==x){break;}}for (j; j < tt1;++j){q1[j] = q1[j + 1];}q1[tt1] = x;}else{int j;for (j = s2; j <= tt2; ++j){if (q2[j] == x){break;}}for (j; j < tt2; ++j){q2[j] = q2[j + 1];}tt2--;q1[++tt1] = x;a[x] = 1;if(tt1+1-s1>n1){if(tt2+1-s2<n2){q2[++tt2] = q1[s1];a[q1[s1]] = 2;}else {a[q1[s1]] = 0;}s1++;}}}for (int i = tt1; i >= s1;i--){cout << q1[i]<<" \n"[i==s1];}for (int i = tt2; i >= s2; i--){cout << q2[i] << " \n"[i == s2];}return 0;
}

P12168 [蓝桥杯 2025 省 C/Python A] 拼好数

题目描述

我们将含有不少于 6 个 6 的数视为一个好数。例如 666666、162636465666 是好数，12366666 不是好数。

给定 n 个正整数 ai​，你可以把这些数分成若干组拼起来，每组内的数可以按任意顺序拼，但一组最多只能有 3 个数。求最多可以得到多少个好数。

输入格式

输入的第一行包含一个正整数 n。

第二行包含 n 个正整数 a1​,a2​,⋯,an​，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案，即最多可以得到的好数的数量。

输入输出样例

输入 #1复制

3
66 66 66

输出 #1复制

1

输入 #2复制

7
666666 16166 6696 666 6 6 6

输出 #2复制

2

说明/提示

评测用例规模与约定

• 对于 70% 的评测用例，1≤n≤20；
• 对于所有评测用例，1≤n≤1000，0≤ai​≤109。

思路：        

极其shi题，我看成贪心，~~一分没拿到，讨厌oi赛制~~，原来是枚举

5可以选1 2 3 4 5

4 可以选 (1,1) 2 3 4 5 

3可以选 (2,2),(2,3) 

2 可以选 (1,1)

1 只能跟别人玩

   

#include<bits/stdc++.h>
using namespace std;
int a[5];
int main(){int n;cin>>n;int ans=0;for(int i=1;i<=n;++i){int x;cin>>x;int cnt=0;while(x){if(x%10==6)cnt++;x/=10;}if(cnt>=6)ans++;else{a[cnt]++;}}int p=1;while(a[5]>0){while(a[p]==0&&p<=6)p++;a[p]--;a[5]--;ans++;}while(a[4]>0&&a[1]>=2){a[1]-=2;a[4]--;ans++;}p=2;while(a[4]>0){while(a[p]==0&&p<=6)p++;if(p==6)break;a[p]-=1;a[4]--;ans++;}while(a[2]>0&&a[1]>0&&a[3]>0){ans++;a[2]--;a[3]--;a[1]--;}ans+=(3*a[3]+2*a[2])/6;//因为顺序无所无，直接打乱分配cout<<ans;
}

P12169 [蓝桥杯 2024 省 C/Python A] 登山

题目描述

小蓝正在登山，山峰的高度构成 n 行 m 列的正整数矩阵，ai,j​ 表示第 i 行第 j 列格子 (i,j) 上的山峰的高度。小蓝以一种特别的方式进行登山，如果他此刻在第 p 行第 q 列的格子 (p,q) 上，那么下一步可以选择：

1. 走到格子 (i,q)，满足 ai,q​<ap,q​ 且 i>p；
2. 走到格子 (i,q)，满足 ai,q​>ap,q​ 且 i<p；
3. 走到格子 (p,j)，满足 ap,j​<ap,q​ 且 j>q；
4. 走到格子 (p,j)，满足 ap,j​>ap,q​ 且 j<q。

小蓝想知道，如果他依次从每一个格子开始出发，按照最优策略，他最高能到达的山峰的高度的平均值是多少？

输入格式

输入的第一行包含两个正整数 n,m，用一个空格分隔。

接下来 n 行，每行包含 m 个正整数。其中第 i 行包含 ai,1​,ai,2​,⋯,ai,m​，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个实数表示答案，四舍五入保留正好 6 位小数。

输入输出样例

输入 #1复制

2 2
1 3
3 2

输出 #1复制

2.500000

输入 #2复制

2 3
2 4 1
4 2 5

输出 #2复制

4.166667

说明/提示

样例说明 1

除了从格子 (1,1) 出发以外，其他格子都能到达高度为 3 的山峰，(1+3+3+3)/4=2.5。

样例说明 2

每个格子能到达的高度：

44​44​45​

其中 (1,1) 可以先到达格子 (1,3) 再到达格子 (1,2)。

评测用例规模与约定

• 对于 40% 的评测用例，1≤n,m≤102；
• 对于所有评测用例，1≤n,m≤104，1≤n×m≤106，1≤aij​≤109。

完了，我爆搜的，可能MLE哭，不知道能不能省一

待补