2024 蓝桥杯省赛 C/C++ 大学 B 组题解与复盘

3、好数

问题描述

一个整数如果按从低位到高位的顺序，奇数位 (个位、百位、万位 ⋯⋯ ) 上的数字是奇数，偶数位 (十位、千位、十万位 ⋯⋯ ) 上的数字是偶数，我们就称之为'好数'。

给定一个正整数 N，请计算从 1 到 N 一共有多少个好数。

输入格式

一个整数 N。

输出格式

一个整数代表答案。

样例说明

对于第一个样例，24 以内的好数有 1、3、5、7、9、21、23，一共 7 个。

评测用例规模与约定

对于 10% 的评测用例，1≤N≤100。

对于 100% 的评测用例，1≤N≤10^7。

简单的模拟。注意不要使用 reverse 反转，否则可能超时。

解法：硬是把暴力枚举题，做出模拟题的味道。

#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;
        while(number){
            int num = number % 10;
            place++;
            if(place % 2 != 0 && num % 2 == 0) break;
            else if(place % 2 == 0 && num % 2 != 0) break;
            number /= 10;
        }
        if(number == 0) cnt++;
    }
    cout << cnt << endl;
    return 0;
}

4、R 格式

问题描述

小蓝最近在研究一种浮点数的表示方法：R 格式。对于一个大于 0 的浮点数 d，可以用 R 格式的整数来表示。给定一个转换参数 n，将浮点数转换为 R 格式整数的做法是：将浮点数乘以 2^n；四舍五入到最接近的整数。

输入格式

一行输入一个整数 n 和一个浮点数 d，分别表示转换参数，和待转换的浮点数。

输出格式

输出一行表示答案：d 用 R 格式表示出来的值。

样例说明

3.14×2^2=12.56，四舍五入后为 13。

评测用例规模与约定

对于 50% 的评测用例：1≤n≤10,1≤ 将 d 视为字符串时的长度 ≤15。

对于 100% 的评测用例：1≤n≤1000,1≤ 将 d 视为字符串时的长度 ≤1024；保证 d 是小数，即包含小数点。

本题本质上是一道高精度题目。不断乘以 2，要用高精度的乘法模版乘。循环 n 次。先记录小数点的位置，然后减去。

#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;
    }
    for(int i = c.size() - 1; i > 0; --i){
        if(c[i] == 0) c.pop_back();
        else break;
    }
    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 != 0) res.push_back(carry);
    }
    for(int i = res.size() - 1; i >= 0; --i) cout << res[i];
    return 0;
}

5、宝石组合

输入格式

第一行包含一个整数 N 表示宝石个数。 第二行包含 N 个整数表示 N 个宝石的'闪亮度'。

输出格式

输出一行包含三个整数表示满足条件的三枚宝石的'闪亮度'。

评测用例规模与约定

对于 30% 的评测用例：3≤N≤100,1≤Hi≤1000。 对于 60% 的评测用例：3≤N≤2000。 对于 100% 的评测用例：3≤N≤10^5,1≤Hi≤10^5。

前提是知道 gcd 与 lcm 都是怎么求的。直接暴力拿 30% 分数，字典序列最小只是听着唬人。

30% 解法：

#include <bits/stdc++.h>
using namespace std;
#define int long long

int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }
int lcm(int a, int b) { return a * b / gcd(a, b); }
int gcd3(int a, int b, int c) { return gcd(gcd(a, b), c); }
int lcm3(int a, int b, int c) { return lcm(lcm(a, b), c); }

signed main() {
    int n;
    cin >> n;
    vector<int> a(n), b(3);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                int s = a[i] * a[j] * a[k] * lcm3(a[i], a[j], a[k]) / (lcm(a[i], a[j]) * lcm(a[i], a[k]) * lcm(a[j], a[k]));
                if (s > ans) {
                    ans = s;
                    b[0] = a[i]; b[1] = a[j]; b[2] = a[k];
                }
            }
        }
    }
    cout << b[0] << " " << b[1] << " " << b[2];
    return 0;
}

100% 解法：

推导公式后，利用 GCD 性质。假设 sum=gcd(a,b,c)，说明 a、b、c 都是 sum 的倍数。

#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…K−1 之间的整数。游戏规则如下：从左上角 (0,0) 处出发，目标是到达右下角 (N−1,N−1) 处的格子，每一步可以选择沿着水平/垂直/对角线方向移动到下一个格子。对于路径经过的棋盘格子，按照经过的格子顺序，上面的数字组成的序列要满足：0,1,2,…,K−1,0,1,2,…,K−1,0,1,2…。途中需要对棋盘上的每个格子恰好都经过一次（仅一次）。路径中不可以出现交叉的线路。

为了方便表示，我们对可以行进的所有八个方向进行了数字编号。现在请你帮小蓝规划出一条行进路径并将其输出。如果有多条路径，输出字典序最小的那一个；如果不存在任何一条路径，则输出 −1。

输入格式

第一行包含两个整数 N,K。 接下来输入 N 行，每行 N 个整数表示棋盘格子上的数字。

输出格式

输出一行表示答案。如果存在答案输出路径，否则输出 −1。

评测用例规模与约定

对于 80% 的评测用例：1≤N≤5。 对于 100% 的评测用例：1≤N≤10,1≤K≤10。

DFS 模版总结。字典序最小指从第一位开始比较 ASCII 码值。

#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、拔河

问题描述

小明是学校里的一名老师，他带的班级共有 nn 名同学，第 ii 名同学力量值为 aiai。在闲暇之余，小明决定在班级里组织一场拔河比赛。

为了保证比赛的双方实力尽可能相近，需要在这 nn 名同学中挑选出两个队伍，队伍内的同学编号连续：{al1,al1+1,…,ar1−1,ar1} 和 {al2,al2+1,…,ar2−1,ar2}，其中 l1≤r1<l2≤r2。

两个队伍的人数不必相同，但是需要让队伍内的同学们的力量值之和尽可能相近。请计算出力量值之和差距最小的挑选队伍的方式。

输入格式

输入共两行。 第一行为一个正整数 n。 第二行为 n 个正整数 ai。

输出格式

输出共一行，一个非负整数，表示两个队伍力量值之和的最小差距。

评测用例规模与约定

对于 20% 的评测用例，保证 n≤50。 对于 100% 的评测用例，保证 n≤10^3,ai≤10^9。

定一个区间，动一个区间。使用双动态，定一，动一。

#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;
}

知识点

1、鸽巢定理（抽屉原理）

基本原理：常被用于证明存在性证明，和求最坏情况下的解。

• 存在性证明：连最坏情况都不存在解，所以情况也就肯定不存在解。

举例：世界上肯定有两个人头发数量一样多；1500 人中，至少有 5 个人的生日相同；n 个人之间握手，一定有两个人握手的次数相同。

例题：hdu1205 吃糖果（隔板法）

假设 N 糖果数最多的一种糖果，S 是总数-N；如果：S>=N-1 必然有解；S<N-1 必然无解。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int K;
LL S, N, x;
void solve() {
    cin >> K;
    S = N = 0;
    for(int i = 1; i <= K; i ++) {
        cin >> x;
        N = max(N, x);
        S += x;
    }
    S -= N;
    cout << (S >= N - 1 ? "Yes" : "No") << '\n';
}
int main() {
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) { solve(); }
}

2、高精度运算

基本概念：高精度，通常是用来处理大的整数，如超过 (int、long long) 的整数的加减乘除。通常是用 string 字符串或数组来储存这些数，然后模拟手算。

常见类型：高精度加、减、乘、除低精度算法等。

高精度 + 高精度

在做这道题目的时候，需注意细节：'进位问题-carry'，溢出。

#include <iostream>
#include <vector>
using namespace std;
string add(string str1, string str2){
    vector<int> A, B;
    for(int i = str1.size() - 1; i >= 0; --i) A.push_back(str1[i] - '0');
    for(int i = str2.size() - 1; i >= 0; --i) B.push_back(str2[i] - '0');
    vector<int> c;
    int carry = 0;
    for(int i = 0; i < A.size() || i < B.size() || carry; ++i){
        if(i < A.size()) carry += A[i];
        if(i < B.size()) carry += B[i];
        c.push_back(carry % 10);
        carry /= 10;
    }
    string res;
    for(int i = c.size() - 1; i >= 0; --i) res += c[i] + '0';
    return res;
}
int main(){
    string num1 = "1534";
    string num2 = "1534";
    cout << add(num1, num2);
    return 0;
}

高精度 - 高精度

#include <iostream>
#include <vector>
using namespace std;
bool cmp(vector<int> A, vector<int> B){
    if(A.size() != B.size()) return A.size() > B.size();
    for(int i = A.size() - 1; i >= 0; --i){
        if(A[i] != B[i]) return A[i] > B[i];
    }
    return true;
}
string sub(string str1, string str2){
    vector<int> A, B;
    for(int i = str1.size() - 1; i >= 0; --i) A.push_back(str1[i] - '0');
    for(int i = str2.size() - 1; i >= 0; --i) B.push_back(str2[i] - '0');
    if(!cmp(A, B)) return "-" + sub(str2, str1);
    vector<int> C;
    int borrow = 0;
    for(int i = 0; i < A.size(); ++i){
        borrow = A[i] - borrow;
        if(i < B.size()) borrow -= B[i];
        C.push_back((borrow + 10) % 10);
        borrow = borrow < 0 ? 1 : 0;
    }
    while(C.size() != 1 && C[C.size() - 1] == 0) C.pop_back();
    string res;
    for(int i = C.size() - 1; i >= 0; --i) res += to_string(C[i]);
    return res;
}
int main(){
    string num1 = "1000";
    string num2 = "1999";
    cout << sub(num1, num2);
    return 0;
}

高精度 乘 高精度算法

#include <iostream>
#include <vector>
using namespace std;
string mul(string str1, string str2){
    vector<int> A, B;
    for(int i = str1.size() - 1; i >= 0; --i) A.push_back(str1[i] - '0');
    for(int i = str2.size() - 1; i >= 0; --i) B.push_back(str2[i] - '0');
    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 = carry + C[i];
        C[i] = carry % 10;
        carry /= 10;
    }
    while(C.size() != 1 && C[C.size() - 1] == 0) C.pop_back();
    string res;
    for(int i = C.size() - 1; i >= 0; --i) res += to_string(C[i]);
    return res;
}
int main(){
    string str1 = "123";
    string str2 = "456";
    cout << mul(str1, str2);
    return 0;
}

高精度除于高精度

#include <iostream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
bool cmp(vector<int> v1, vector<int> v2){
    if(v1.size() != v2.size()) return v1.size() > v2.size();
    for(int i = v1.size() - 1; i >= 0; --i)
        if(v1[i] != v2[i]) return v1[i] > v2[i];
    return true;
}
vector<int> sub(vector<int> v1, vector<int> v2){
    vector<int> c;
    int borrow = 0;
    for(int i = 0; i < v1.size(); ++i){
        borrow = v1[i] - borrow;
        if(i < v2.size()) borrow -= v2[i];
        c.push_back((borrow + 10) % 10);
        borrow = borrow < 0 ? 1 : 0;
    }
    while(c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}
string div(string str1, string str2, string& rs){
    vector<int> A, B;
    for(int i = str1.size() - 1; i >= 0; --i) A.push_back(str1[i] - '0');
    for(int i = str2.size() - 1; i >= 0; --i) B.push_back(str2[i] - '0');
    vector<int> C;
    vector<int> cur;
    for(int i = str1.size() - 1; i >= 0; --i){
        cur.insert(cur.begin(), A[i]);
        while(cur.size() > 1 && cur.back() == 0) cur.pop_back();
        int t = 0;
        while(cmp(cur, B)){
            cur = sub(cur, B);
            t++;
        }
        C.push_back(t);
    }
    reverse(C.begin(), C.end());
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    string res;
    for(int i = C.size() - 1; i >= 0; --i) res += to_string(C[i]);
    string r;
    for(int i = cur.size() - 1; i >= 0; --i) r += to_string(cur[i]);
    rs = r;
    return res;
}
int main(){
    string s1 = "1234";
    string s2 = "23";
    string remainer;
    cout << div(s1, s2, remainer) << endl;
    cout << remainer << endl;
    return 0;
}

3、快速幂

简单复习一下。

#include <iostream>
using namespace std;
int main(){
    int base = 3;
    int exponent = 3;
    int result = 1;
    while(exponent){
        if(exponent & 1) result *= base;
        base *= base;
        exponent >>= 1;
    }
    cout << result;
}

4、最大公约数 (gcd) 与最小公倍数 (lcm)

最大公约数，就是两个数，共有的最大的因数。 lcm 是最小公倍数。

定理：a、b 两个数的最小公倍数 (lcm) 乘以它们的最大公约数 (gcd) 等于 a 和 b 本身的乘积。

如：gcd(a,b) * lcm(a,b)=a*b

#include <iostream>
using namespace std;
int gcd(int a, int b){
    return b != 0 ? gcd(b, a % b) : a;
}
int main(){
    int num1 = 10, num2 = 8;
    cout << gcd(num1, num2) << endl;
    cout << num1 * num2 / gcd(num1, num2);
    return 0;
}

5、gcd 与 lcm 推导

通过质因数分解和指数分析，我们发现：

• 所有质因数的最小指数相乘，就是三个数的最大公约数（GCD)
• 你在网上列举其他例子也是这样，我私下推导过。