第十三届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组题解

3. 刷题统计

问题描述 小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做 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;
}

4. 修剪灌木

问题描述 有 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;
}

5. X 进制减法

问题描述 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;
}

6. 统计子矩阵

问题描述 给定一个 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;
    return 0;
}

7. 积木画

问题描述 用 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;
}

8. 扫雷

问题描述 在一个 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){
        for(int j=1; j<=m; ++j){
            if(arr[i][j]!=0) res[i][j]=9;
            else{
                int sum=0;
                for(int k=0; k<8; ++k){
                    if(arr[i+fa1[k]][j+fa2[k]]!=0) sum++;
                }
                res[i][j]=sum;
            }
        }
    }
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=m; ++j) cout<<res[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

9. 李白打酒加强版

问题描述 李白提壶买酒，初始 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 0;
}

10. 砍竹子

问题描述 有 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);
    }
    int cnt=0;
    int temp_id=-2,temp_cnt=-2;
    while(!pq.empty()){
        auto cur = pq.top();
        pq.pop();
        if(cur.x==1) continue;
        if(temp_id==cur.y-1&&temp_cnt==cur.x){
            temp_id=cur.y;
            int val = get_res(cur.x);
            if(val!=1) pq.emplace(val,temp_id);
        }else{
            cnt++;
            temp_cnt=cur.x;
            temp_id =cur.y;
            int val = get_res(cur.x);
            if(val!=1) pq.emplace(val,temp_id);
        }
    }
    cout<<cnt;
    return 0;
}

知识点总结

一、double 与 long double

• double: 通常占用 8 字节，有效位数约为 15~17 位。
• long double: 编译器决定，通常不少于 double，在某些架构下占 12 或 16 字节，有效位数 18-19 位。

二、C++ 数学函数后缀

• 绝对值: fabs (double), fabsf (float), fabsl (long double)
• 取整: ceil, floor, round 及其对应后缀 f/l
• 开方: sqrt, sqrtf, sqrtl

三、不用 + 号的加法

利用位运算 ^ (不进位) 与 & (进位) 实现。

四、内存分配建议

• 小数组 (1e4 以下): 函数内部直接定义。
• 大数组 (1e5 以上): 必须用全局数组或 static 局部数组，避免栈溢出。
• 动态数组: 若大小运行时确定，用 vector（堆空间），但过大时不建议。

五、memset 与 sizeof

• memset 用于按字节填充内存，通常用于清零或设 -1。
• sizeof 返回字节数，常用于计算数组长度。