2024年蓝桥杯 C/C++ 大学 B 组省赛题目解析

3. 好数

问题描述

从低位到高位，奇数位上的数字是奇数，偶数位上的数字是偶数，这样的整数叫'好数'。给定 N，求 1~N 中有多少个好数。

解题思路

数据规模不大（N ≤ ? 题面未给，但猜测在 int 范围内），直接枚举每个数，依次检查每一位。用 place 计数当前是第几位（从低位起），判断奇偶是否匹配。

#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    int cnt = 0;
    for(int i = 1; i <= n; ++i){
        int number = i;
        int place = 0;
        bool ok = true;
        while(number){
            int num = number % 10;
            place++;
            if(place % 2 != 0 && num % 2 == 0) { ok = false; break; }
            else if(place % 2 == 0 && num % 2 != 0) { ok = false; break; }
            number /= 10;
        }
        if(ok) cnt++;
    }
    cout << cnt << endl;
    return 0;
}

4. R 格式

问题描述

对浮点数 d（用字符串给出，可能含小数点），乘以 2^n，再四舍五入到整数。n 可达 1000，d 长度不超过 1024。

解题思路

高精度乘法。先将 d 反转，去掉小数点存储每位数字。实现一个 multiply 函数，将当前大数 a 乘以 2（b 固定为 [2]），循环 n 次即得乘以 2^n 的结果。再根据小数点位置处理四舍五入：检查小数点后的第一位是否 ≥5，决定是否进位，最后反向输出。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> a, b;
void multiply(){
    vector<int> c(a.size() + b.size(), 0);
    for(int i = 0; i < a.size(); ++i)
        for(int j = 0; j < b.size(); ++j)
            c[i + j] += a[i] * b[j];
    int carry = 0;
    for(int i = 0; i < c.size(); ++i){
        carry += c[i];
        c[i] = carry % 10;
        carry /= 10;
    }
    while(c.size() > 1 && c.back() == 0) c.pop_back();
    a = c;
}
int main(){
    int n;
    string str;
    cin >> n >> str;
    reverse(str.begin(), str.end());
    int pla = 0;
    for(int i = 0; i < str.size(); ++i){
        if(str[i] != '.') a.push_back(str[i] - '0');
        else pla = i;
    }
    b.push_back(2);
    for(int i = 0; i < n; ++i) multiply();
    vector<int> res;
    for(int i = pla; i < a.size(); ++i) res.push_back(a[i]);
    if(a[pla - 1] >= 5){
        int carry = 1;
        for(int i = 0; i < res.size(); ++i){
            carry += res[i];
            res[i] = carry % 10;
            carry /= 10;
        }
        if(carry) res.push_back(carry);
    }
    for(int i = res.size() - 1; i >= 0; --i) cout << res[i];
    return 0;
}

5. 宝石组合

问题描述

N 颗宝石，每颗有闪亮度值，选出三颗使得某种组合值（与 GCD/LCM 性质相关）最大，要求输出字典序最小的那组。

解题思路

题目本意是利用 GCD 和 LCM 的关系推导出简化公式，变成寻找一个数 i，使得存在三个倍数 i 的宝石，它们的值按升序输出。从最大值向下枚举 i，检查所有 i 的倍数是否在输入中出现，取前三个即可。由于从大到小枚举，第一个找到的就是使 i 最大的组合，且自动满足字典序最小（因为倍数是从小到大取的）。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
signed main(){
    int n;
    cin >> n;
    vector<int> arr(N, 0);
    int maxN = -1;
    for(int i = 0; i < n; ++i){
        int cnt;
        cin >> cnt;
        arr[cnt]++;
        maxN = max(maxN, cnt);
    }
    for(int i = maxN; i >= 1; --i){
        int num = 0, cnt[3], flag = 0;
        for(int sum = i; sum < N; sum += i){
            if(arr[sum] != 0){
                for(int k = 0; k < arr[sum] && flag < 3; ++k){
                    cnt[flag++] = sum;
                }
            }
            if(flag == 3){
                cout << cnt[0] << " " << cnt[1] << " " << cnt[2];
                return 0;
            }
        }
    }
    return 0;
}

6. 数字接龙

问题描述

N×N 棋盘，从 (0,0) 走到 (N-1,N-1)，路径经过的数字必须按照 0,1,2,…,K-1 循环。路径不能交叉（除了起点终点），求字典序最小的移动方向序列（方向有 8 个，编号 0~7）。

解题思路

DFS 回溯。方向数组按字典序排列，优先尝试编号小的方向。用 visited 记录是否走过，square 四维数组记录两个格子之间是否已有路径，防止交叉。注意八个方向中只有斜向 (1,3,5,7) 才需要记录交叉。递归找到一条合法路径就输出方向序列。

#include <iostream>
#include <vector>
using namespace std;
const int N = 15;
int n, k;
vector<vector<int>> matrix(N, vector<int>(N, 0));
bool visited[N][N];
bool square[N][N][N][N];
int dir[8][2] = {-1, 0, -1, 1, 0, 1, 1, 1, 1, 0, 1, -1, 0, -1, -1, -1};
vector<int> res;
int flag = 0;
bool dfs(int X, int Y){
    if(X == n - 1 && Y == n - 1 && flag == n * n - 1) return true;
    for(int i = 0; i < 8; ++i){
        int x = X + dir[i][0], y = Y + dir[i][1];
        if(x < 0 || x >= n || y < 0 || y >= n || visited[x][y]) continue;
        if((flag + 1) % k != matrix[x][y]) continue;
        if(square[X + dir[i][0]][Y][X][Y + dir[i][1]]) continue;
        visited[x][y] = true;
        res.push_back(i);
        flag++;
        if(i == 1 || i == 3 || i == 5 || i == 7){
            square[X][Y][x][y] = true;
            square[x][y][X][Y] = true;
        }
        if(dfs(x, y)) return true;
        if(i == 1 || i == 3 || i == 5 || i == 7){
            square[X][Y][x][y] = false;
            square[x][y][X][Y] = false;
        }
        flag--;
        res.pop_back();
        visited[x][y] = false;
    }
    return false;
}
int main(){
    cin >> n >> k;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            cin >> matrix[i][j];
    flag = 0;
    visited[0][0] = true;
    if(dfs(0, 0)){
        for(int i = 0; i < res.size(); ++i) cout << res[i];
    } else cout << -1 << endl;
    return 0;
}

7. 拔河

问题描述

从 n 个同学中挑选两个不重叠的连续区间作为两支队伍，使力量值之和的差距最小。

解题思路

预处理前缀和，枚举第二个队的左端点 i，对于所有可能的第一个队（右端点 < i）的区间和，存入 set。然后枚举第二个队的右端点 k，计算出区间和 k_sum，在 set 中二分查找最接近的值，更新最小差距。注意 set 里插入极大极小值避免边界问题。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 1e3 + 5, Num = 0x3f3f3f3f3f3f3f3f;
ll n;
vector<ll> arr(N, 0);
vector<ll> sum(N, 0);
ll minNum = 0x3f3f3f3f3f3f3f3f;
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> arr[i];
        sum[i] = sum[i - 1] + arr[i];
    }
    set<ll> s;
    s.insert(Num);
    s.insert(-Num);
    for(int i = 2; i <= n; ++i){
        for(int j = 1; j <= i - 1; ++j)
            s.insert(sum[i - 1] - sum[j - 1]);
        for(int k = i; k <= n; ++k){
            ll k_sum = sum[k] - sum[i - 1];
            auto it = s.lower_bound(k_sum);
            minNum = min(minNum, abs(*it - k_sum));
            minNum = min(minNum, abs(*(--it) - k_sum));
        }
    }
    cout << minNum;
    return 0;
}

赛后知识点整理

鸽巢定理（抽屉原理）

把多于 n 个物体放到 n 个抽屉里，至少有一个抽屉里有至少两个物体。常用于证明存在性，比如蓝桥杯里出现过的'至少两个数模某个数同余'等场景。

高精度运算

当整数超过 64 位时，需要用数组或字符串模拟加减乘除。乘法实现要先逐位相乘再统一处理进位。注意清除前导零。

快速幂

计算 a^b mod m 可以在 O(log b) 时间内完成，常用于模意义下的指数运算。

最大公约数 (GCD) 与最小公倍数 (LCM)

gcd(a,b) * lcm(a,b) = a * b。求 GCD 通常用辗转相除法（欧几里得算法），LCM 可由乘积除以 GCD 得到。多个数时，可两两递推。

GCD 与 LCM 的性质推导

利用唯一分解定理，把每个数分解成质因数幂次的乘积，那么 GCD 就是取每个质数指数的最小值，LCM 是取最大值。分析指数关系可以解决一些与约数倍数相关的推理题。