C++算法
第十三届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组题解
第十三届蓝桥杯省赛 C/C++ 大学 B 组的 10 道真题题解与解析，涵盖进制转换、贪心算法、动态规划、搜索及基础数学运算等核心考点。主要涉及九进制转十进制、顺子日期、刷题统计、修剪灌木、X 进制减法、统计子矩阵、积木画、扫雷、李白打酒加强版及砍竹子等题目。提供了完整的 C++ 代码实现及关键知识点总结，包括数据类型选择、内存分配策略及常用库函数用法，适合备考选手参考学习。
第十三届蓝桥杯省赛 C/C++ 大学 B 组的 10 道真题题解与解析，涵盖进制转换、贪心算法、动态规划、搜索及基础数学运算等核心考点。主要涉及九进制转十进制、顺子日期、刷题统计、修剪灌木、X 进制减法、统计子矩阵、积木画、扫雷、李白打酒加强版及砍竹子等题目。提供了完整的 C++ 代码实现及关键知识点总结，包括数据类型选择、内存分配策略及常用库函数用法，适合备考选手参考学习。
本文整理了第十三届蓝桥杯省赛 C/C++ 大学 B 组的 10 道真题题解与解析，涵盖进制转换、贪心算法、动态规划、搜索及基础数学运算等核心考点。
问题描述 本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。 九进制正整数 (2022)9 转换成十进制等于多少？
解析 (2022)9 = 29^0 + 29^1 + 09^2 + 29^3
#include <bits/stdc++.h>
using namespace std;
int main(){
string str="2022";
reverse(str.begin(),str.end());
int sum=0;
for(int i=0; i<str.size(); ++i){
sum+=pow(9,i)*(str[i]-'0');
}
cout<<sum<<endl;
return 0;
}
问题描述 顺子指的就是连续的三个数字：123、456 等。顺子日期指的就是在日期的 yyyymmdd 表示法中，存在任意连续的三位数是一个顺子的日期。例如 20220123 就是一个顺子日期。小明想知道在整个 2022 年份中，一共有多少个顺子日期？
解析 暴力枚举所有日期，判断月日是否合理且包含顺子。
#include <bits/stdc++.h>
using namespace std;
bool get_num(int mm, int dd){
if(mm==1||mm==3||mm==5||mm==7||mm==8||mm==10||mm==12){
if(dd>=1&&dd<=31) return true;
}else if(mm==2){
if(dd>=1&&dd<=28) return true;
}else if(mm==4||mm==6||mm==9||mm==11){
if(dd>=1&&dd<=30) return true;
}
return false;
}
bool get_cnt(string str){
str = "9"+str;
vector<int> arr(str.size(),0);
for(int i=1; i<str.size(); ++i)
if(str[i]==str[i-1]+1) arr[i]=arr[i-1]+1;
for(int i=1; i<arr.size(); ++i)
if(arr[i]==2) return true;
return false;
}
int main() {
int sum=0;
for(int i=0; i<10; ++i){
for(int j=0; j<10; ++j){
for(int k=0; k<10; ++k){
for(int z=0; z<10; ++z){
int mm = i*10+j;
int dd = k*10+z;
if(get_num(mm,dd)){
string str = to_string(i)+to_string(j)+to_string(k)+to_string(z);
if(get_cnt(str)) sum++;
}
}
}
}
}
cout<<sum<<endl;
return 0;
}
问题描述 小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做 a 道题目，周六和周日每天做 b 道题目。请你帮小明计算，按照计划他将在第几天实现做题数大于等于 n 题？
解析 注意数据范围可能达到 10^18，不能直接循环累加，需利用整除和取模优化。
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int a,b,n;
cin>>a>>b>>n;
int cnt = 0;
int sum = n/(a*5+b*2);
int temp = n%(a*5+b*2);
if(temp<=a*5){
cnt+=ceil((double)temp/a);
}else{
temp-=5*a;
cnt+=5;
cnt+=ceil((double)temp/b);
}
cnt+=sum*7;
cout<<cnt<<endl;
return 0;
}
问题描述 有 N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晚会修剪一棵灌木，让灌木的高度变为 0 厘米。修剪顺序是从最左侧开始向右，修完最右侧后调转方向向左，循环往复。灌木每天从早上到傍晚会长高 1 厘米。求每棵灌木最高长到多高。
解析 贪心观察，第 i 棵树（0-indexed）最高高度为 max(i*2, (N-i-1)*2)。
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<int> res(n,0);
for(int i=0; i<n; ++i){
res[i]=max(i*2,(n-i-1)*2);
}
for(int i:res) cout<<i<<endl;
return 0;
}
问题描述 X 进制是一种很神奇的进制，每一数位的进制并不固定。现在有两个 X 进制表示的整数 A 和 B，每一数位最高为 N 进制，最低为二进制。算出 A-B 的结果最小可能是多少（转换为十进制后模 1000000007）。
解析 贪心策略，为了使差值最小，每一位的进制应尽可能小（至少为 max(A[i], B[i]) + 1，且不小于 2）。
#include <bits/stdc++.h>
#define int long long
const int CNT = 1000000007;
using namespace std;
signed main(){
int N;
cin>>N;
int an,bn;
cin>>an;
vector<int> A(an,0);
for(int i=an-1; i>=0; --i) cin>>A[i];
cin>>bn;
vector<int> B(bn,0);
for(int j=bn-1; j>=0; --j) cin>>B[j];
int sum = 0;
int X = 1;
for(int i=0; i<an; ++i){
sum=(sum+(A[i]-B[i])*X)%CNT;
X *= max(A[i],B[i])<=1?2:max(A[i],B[i])+1;
X%=CNT;
}
cout<<sum<<endl;
return 0;
}
问题描述 给定一个 N×M 的矩阵 A，统计有多少个子矩阵满足子矩阵中所有数的和不超过给定的整数 K。
解析 二维前缀和 + 滑动窗口（双指针）。纯前缀和暴力只能过部分数据。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e2 + 5;
int arr[N][N];
int n, m, K;
signed main() {
cin >> n >> m >> K;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
cin >> arr[i][j];
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
arr[i][j] += arr[i][j - 1];
for (int j = 1; j <= m; ++j)
for (int i = 1; i <= n; ++i)
arr[i][j] += arr[i - 1][j];
int cnt=0;
for(int top=0; top<=n; ++top){
for(int bott=top+1; bott<=n; ++bott){
int l=0;
for(int r=1; r<=m; ++r){
int sum= arr[bott][r]-arr[bott][l]-arr[top][r]+arr[top][l];
while(sum>K&&l<r){
l++;
sum= arr[bott][r]-arr[bott][l]-arr[top][r]+arr[top][l];
}
cnt+=r-l;
}
}
}
cout << cnt << endl;
;
}
问题描述 用 I 型（2 单位面积）和 L 型（3 单位面积）积木拼满 2×N 的画布，求方案数。
解析 线性 DP。定义状态 dp[i][0/1/2] 分别表示第 i 列第一行填满、两行都填满、第二行填满的方案数。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1000000007;
const int N = 1e7+5;
int dp[N][3];
signed main(){
int n;
cin>>n;
dp[0][1]=1;
dp[1][1]=1;
for(int i=2; i<=n; ++i){
dp[i][0]=(dp[i-1][2]+dp[i-2][1])%MOD;
dp[i][2]=(dp[i-1][0]+dp[i-2][1])%MOD;
dp[i][1]=((dp[i-1][0] + dp[i-1][2])%MOD + (dp[i-1][1] + dp[i-2][1])%MOD)%MOD;
}
cout<<dp[n][1]<<endl;
return 0;
}
问题描述 在一个 n 行 m 列的方格图上有一些位置有地雷，请为每个空位置标一个整数，表示周围八个相邻的方格中有多少个地雷。
解析 模拟遍历，对每个格子检查周围 8 个方向是否有地雷。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e2+5;
vector<vector<int>> arr(N,vector<int>(N,0));
vector<vector<int>> res(N,vector<int>(N,0));
int n,m;
int fa1[]={1,1,0,0,-1,1,-1,-1};
int fa2[]={-1,1,1,-1,0,0,1,-1};
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j)
cin>>arr[i][j];
for(int i=1; i<=n; ++i){
( j=; j<=m; ++j){
(arr[i][j]!=) res[i][j]=;
{
sum=;
( k=; k<; ++k){
(arr[i+fa1[k]][j+fa2[k]]!=) sum++;
}
res[i][j]=sum;
}
}
}
( i=; i<=n; ++i){
( j=; j<=m; ++j) cout<<res[i][j]<<;
cout<<endl;
}
;
}
问题描述 李白提壶买酒，初始 2 斗。逢店加一倍，遇花喝一斗。一共遇到店 N 次，花 M 次，最后一次是花，正好喝完。求不同顺序的方案数。
解析 记忆化搜索或动态规划。dfs(n, m, drink) 表示剩余店数、花数和当前酒量。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1000000007;
int used[105][105][105];
int n,m,drink;
int dfs(int n,int m,int drink){
if(n<0||m<0||drink<0) return 0;
if(drink>m) return 0;
if(n==0&&m==1&&drink==1) return 1;
if(used[n][m][drink]!=-1) return used[n][m][drink];
return used[n][m][drink]=(dfs(n-1,m,drink*2)+dfs(n,m-1,drink-1))%MOD;
}
signed main(){
cin>>n>>m;
memset(used,-1,sizeof used);
drink = 2;
cout<<dfs(n,m,drink);
return ;
}
问题描述 有 n 棵竹子，高度 hi。魔法可以对连续相同高度的竹子使用，一次魔法可将高度 H 变为 floor(H/2)+1。求最少使用多少次魔法使所有竹子高度变为 1。
解析 优先队列维护当前最大高度，处理连续相同高度的竹子。
#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
struct cmp{
bool operator()(const pair<int,int>& p1,const pair<int,int>& p2){
if(p1.x==p2.x) return p1.y>p2.y;
return p1.x<p2.x;
}
};
int get_res(int cnt){
return floor(sqrtl(floor(double(cnt)/2)+1));
}
signed main(){
priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> pq;
int n;
cin>>n;
for(int i=0; i<n; ++i){
int num;
cin>>num;
pq.emplace(num,i);
}
cnt=;
temp_id=,temp_cnt=;
(!pq.()){
cur = pq.();
pq.();
(cur.x==) ;
(temp_id==cur.y&&temp_cnt==cur.x){
temp_id=cur.y;
val = (cur.x);
(val!=) pq.(val,temp_id);
}{
cnt++;
temp_cnt=cur.x;
temp_id =cur.y;
val = (cur.x);
(val!=) pq.(val,temp_id);
}
}
cout<<cnt;
;
}
fabs (double), fabsf (float), fabsl (long double)ceil, floor, round 及其对应后缀 f/lsqrt, sqrtf, sqrtl利用位运算 ^ (不进位) 与 & (进位) 实现。
memset 用于按字节填充内存，通常用于清零或设 -1。sizeof 返回字节数，常用于计算数组长度。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online