2023 第十四届蓝桥杯国赛 C/C++ 大学 B 组真题及题解

Java

public class DpProblem {
    public static void main(String[] args) {
        long[] dp = new long[4];
        StringBuilder str = new StringBuilder();
        for (int i = 1; i <= 2023; i++) {
            str.append(i);
        }
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c == '2') {
                dp[0]++;
                dp[2] += dp[1];
            }
            if (c == '0') {
                dp[1] += dp[0];
            }
            if (c == '3') {
                dp[3] += dp[2];
            }
        }
        System.out.println(dp[3]);
    }
}

二、双子数

问题描述

若一个正整数 x 可以被表示为 p^2 * q^2，其中 p、q 为质数且 p≠q，则 x 是一个双子数。请计算区间 [2333, 23333333333333] 内有多少个双子数？

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数。

// 注意数据类型使用 unsigned long long 防止溢出 // int->1e9, long long->1e18, unsigned long long 范围更大

C++

#include <iostream>
#include <vector>
#define ll long long
using namespace std;
const int N = 1e7 + 10;
vector<bool> vec(N, true);
vector<ll> res;

void sieve(){
    vec[0] = vec[1] = false;
    for(int i = 2; i < vec.size(); ++i){
        if(vec[i]) res.push_back((ll)i);
        for(ll num : res){
            if(num * i > vec.size()) break;
            vec[i * num] = false;
            if(i % num == 0) break;
        }
    }
}

int main(){
    sieve();
    ll num = 0;
    for(ll i = 0; i < res.size(); i++){
        unsigned long long pp = res[i] * res[i];
        if(pp * pp > 23333333333333) break;
        for(ll j = i + 1; j < res.size(); j++){
            ll qq = res[j] * res[j];
            if(pp * qq > 23333333333333) break;
            if(pp * qq < 2333) continue;
            num++;
        }
    }
    cout << num << endl;
    return 0;
}

Java

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class PrimeNumberCombination {
    static final int N = 10000010;
    static boolean[] isPrime = new boolean[N];
    static List<Integer> primes = new ArrayList<>();

    public static void sieve() {
        for (int i = 0; i < N; i++) isPrime[i] = true;
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i < N; i++) {
            if (isPrime[i]) primes.add(i);
            for (int prime : primes) {
                if (prime * i >= N) break;
                isPrime[prime * i] = false;
                if (i % prime == 0) break;
            }
        }
    }

    public static void main(String[] args) {
        sieve();
        BigInteger limit1 = BigInteger.valueOf(23333333333333L);
        BigInteger limit2 = BigInteger.valueOf(2333L);
        long num = 0;
        for (int i = 0; i < primes.size(); i++) {
            BigInteger pp = BigInteger.valueOf(primes.get(i)).pow(2);
            if (pp.pow(2).compareTo(limit1) > 0) break;
            for (int j = i + 1; j < primes.size(); j++) {
                BigInteger qq = BigInteger.valueOf(primes.get(j)).pow(2);
                BigInteger product = pp.multiply(qq);
                if (product.compareTo(limit1) > 0) break;
                if (product.compareTo(limit2) < 0) continue;
                num++;
            }
        }
        System.out.println(num);
    }
}

三、班级活动

问题描述

班上一共有 n 名 (n 为偶数) 同学，老师想把所有的同学进行分组，每两名同学一组。为了公平，老师给每名同学随机分配了一个 n 以内的正整数作为 id。老师希望通过更改若干名同学的 id 使得对于任意一名同学 i，有且仅有另一名同学 j 的 id 与其相同。请问老师最少需要更改多少名同学的 id？

输入格式

第一行为一个正整数 n。 第二行为 n 个由空格隔开的整数 a1,a2,...,an。

输出格式

输出共 1 行，一个整数。

// 思路：统计每个 ID 出现的次数 // 如果某个 ID 出现次数大于 2，超出部分需要修改 // 如果某个 ID 出现次数为 1，需要配对

C++

#include <iostream>
const int N = 1e5 + 5;
using namespace std;
int arr[N];

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i){
        int num;
        cin >> num;
        arr[num]++;
    }
    int num1 = 0, num2 = 0;
    for(int i : arr){
        if(i > 2) num1 += i - 2;
        else if(i == 1) num2++;
    }
    int sum = 0;
    if(num1 > num2){
        sum = num1;
    } else {
        sum = num2 + (num1 - num2) / 2;
    }
    cout << sum << endl;
    return 0;
}

Java

import java.util.Scanner;

public class StudentIdAdjustment {
    static final int N = 100005;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] arr = new int[N];
        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            int num = scanner.nextInt();
            arr[num]++;
        }
        int num1 = 0, num2 = 0;
        for (int i : arr) {
            if (i > 2) num1 += i - 2;
            else if (i == 1) num2++;
        }
        int sum = 0;
        if (num1 > num2) {
            sum = num1;
        } else {
            sum = num2 + (num1 - num2) / 2;
        }
        System.out.println(sum);
        scanner.close();
    }
}

四、合并数列

问题描述

小明发现有很多方案可以把一个很大的正整数拆成若干正整数的和。他采取了其中两种方案，分别将他们列为两个数组 {a1,a2,...,an} 和 {b1,b2,...,bm}。两个数组的和相同。 定义一次合并操作可以将某数组内相邻的两个数合并为一个新数，新数的值是原来两个数的和。小明想通过若干次合并操作将两个数组变成一模一样。请计算至少需要多少次合并操作可以完成小明的目标。

输入格式

第一行为两个正整数 n, m。 第二行为 n 个由空格隔开的整数。 第三行为 m 个由空格隔开的整数。

// 思路：双指针与前缀和结合 // 从头开始计算前缀和，如果相同时，代表俩数列第 i 位已经相同，更新起始位置

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n, 0);
    vector<int> b(m, 0);
    for(int i = 0; i < n; ++i) cin >> a[i];
    for(int i = 0; i < m; ++i) cin >> b[i];

    long long sum_a = 0, sum_b = 0;
    int cnt_a = 0, cnt_b = 0;
    int cnt_sum = 0;

    while(true){
        if(sum_a == sum_b){
            if(cnt_a < n) sum_a += a[cnt_a++];
            if(cnt_b < m) sum_b += b[cnt_b++];
        } else if(sum_a < sum_b){
            sum_a += a[cnt_a++];
            cnt_sum++;
        } else if(sum_b < sum_a){
            sum_b += b[cnt_b++];
            cnt_sum++;
        }
        if(cnt_a == n && cnt_b == m) break;
    }
    cout << cnt_sum;
    return 0;
}

Java

import java.util.Scanner;

public class MergeArrays {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] a = new int[n];
        int[] b = new int[m];
        for (int i = 0; i < n; i++) a[i] = scanner.nextInt();
        for (int i = 0; i < m; i++) b[i] = scanner.nextInt();

        long sum_a = 0, sum_b = 0;
        int cnt_a = 0, cnt_b = 0;
        int cnt_sum = 0;

        while (true) {
            if (sum_a == sum_b) {
                if (cnt_a < n) sum_a += a[cnt_a++];
                if (cnt_b < m) sum_b += b[cnt_b++];
            } else if (sum_a < sum_b) {
                sum_a += a[cnt_a++];
                cnt_sum++;
            } else {
                sum_b += b[cnt_b++];
                cnt_sum++;
            }
            if (cnt_a == n && cnt_b == m) break;
        }
        System.out.println(cnt_sum);
        scanner.close();
    }
}

五、数三角

问题描述

小明在二维坐标系中放置了 n 个点，他想在其中选出一个包含三个点的子集，这三个点能组成三角形。然而这样的方案太多了，他决定只选择那些可以组成等腰三角形的方案。请帮他计算出一共有多少种选法可以组成等腰三角形？

输入格式

第一行为一个正整数 n。 后面 n 行，每行两个整数 xi, yi 表示第 i 个点的坐标。

// 优化思路：根据半径求解，叉乘判是否三点在一条直线 // 预处理分组，避免 O(n^3) 暴力

C++

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
#define ll long long
const ll N = 2e3 + 5;
struct point{ int x; int y; }p[N];

ll get_radius(int i, int j){
    return (ll)(p[i].x - p[j].x) * (p[i].x - p[j].x) + (ll)(p[i].y - p[j].y) * (p[i].y - p[j].y);
}

bool is_parallel(int i, int j, int k){
    ll v = (ll)(p[j].x - p[i].x) * (p[k].y - p[i].y) - (ll)(p[j].y - p[i].y) * (p[k].x - p[i].x);
    if(v == 0) return true;
    else return false;
}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i) cin >> p[i].x >> p[i].y;

    vector<unordered_map<ll, vector<int>>> vec(n);
    for(int i = 0; i < n; ++i){
        unordered_map<ll, vector<int>> m;
        for(int j = 0; j < n; ++j){
            if(i == j) continue;
            ll len = get_radius(i, j);
            m[len].push_back(j);
        }
        vec[i] = m;
    }

    int sum = 0;
    for(int i = 0; i < n; ++i){
        auto m = vec[i];
        for(auto it = m.begin(); it != m.end(); ++it){
            vector<int> p_m = it->second;
            if(p_m.size() <= 1) continue;
            for(int j = 0; j < p_m.size(); ++j){
                for(int k = j + 1; k < p_m.size(); ++k){
                    if(is_parallel(i, p_m[j], p_m[k])) continue;
                    sum++;
                }
            }
        }
    }
    cout << sum << endl;
    return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] x = new int[n];
        int[] y = new int[n];
        HashMap<String, Integer> s = new HashMap<>();

        for(int i = 0; i < n; i++){
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
            String t = x[i] + " " + y[i];
            s.put(t, s.getOrDefault(t, 0) + 1);
        }

        long res = 0;
        for(int i = 0; i < n; i++){
            HashMap<Long, List<Integer>> map = new HashMap<>();
            for(int j = 0; j < n; j++){
                if(i == j) continue;
                long d = (long)Math.pow(x[i] - x[j], 2) + (long)Math.pow(y[i] - y[j], 2);
                List<Integer> list = map.getOrDefault(d, new ArrayList<>());
                list.add(j);
                map.put(d, list);
            }

            for(long b : map.keySet()){ 
                List<Integer> list = map.get(b);
                res += (long)list.size() * (list.size() - 1) / 2;
                long c = 0;
                for(int j : list){
                    long x3 = 2L * x[i] - x[j], y3 = 2L * y[i] - y[j];
                    if(s.containsKey(x3 + " " + y3)){
                        c += s.get(x3 + " " + y3);
                    }
                }
                res -= c / 2;
            }
        }
        System.out.println(res);
    }
}

六、删边问题

问题描述

给定一个包含 N 个结点 M 条边的无向图 G，结点编号 1...N。其中每个结点都有一个点权 Wi。 你可以从 M 条边中任选恰好一条边删除，如果剩下的图恰好包含 2 个连通分量，就称这是一种合法的删除方案。 对于一种合法的删除方案，我们假设 2 个连通分量包含的点的权值之和分别为 X 和 Y，请你找出一种使得 X 与 Y 的差值最小的方案。输出 X 与 Y 的差值。

// 本题为 tarjan 算法的变种，涉及割边问题 // 使用 dfn 和 low 数组判断割边

C++

#include <iostream>
#include <cmath>
#include <vector>
#define ll long long
using namespace std;
const ll N = 1e6 + 5;
const ll maxn = 0x3f3f3f3f3f3f3f3f;
ll n, m, sum_value = 0, cnt = 0, ans = maxn;
vector<ll> dfn(N, 0), low(N, 0);
vector<int> vec[N];
vector<ll> value(N, 0);

void tarjan(int u, int fa){
    dfn[u] = low[u] = ++cnt;
    for(int v : vec[u]){ 
        if(dfn[v] == 0){
            tarjan(v, u);
            low[u] = min(low[v], low[u]);
            if(dfn[u] < low[v]) ans = min(ans, abs(sum_value - 2 * value[v]));
            value[u] += value[v];
        } else if(v != fa){
            low[u] = min(low[u], low[v]);
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> value[i], sum_value += value[i];
    for(int i = 0; i < m; ++i){
        int r1, r2;
        cin >> r1 >> r2;
        vec[r1].push_back(r2);
        vec[r2].push_back(r1);
    }
    tarjan(1, 0);
    if(value[1] != sum_value) cout << abs(sum_value - 2 * value[1]) << endl;
    else if(ans != maxn) cout << ans << endl;
    else cout << -1 << endl;
    return 0;
}

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static final long N = (long) (1e6 + 5);
    static final long maxn = 0x3f3f3f3f3f3f3f3fL;
    static long n, m, sum_value = 0, cnt = 0, ans = maxn;
    static List<Long> dfn = new ArrayList<>();
    static List<Long> low = new ArrayList<>();
    static List<List<Integer>> vec = new ArrayList<>();
    static List<Long> value = new ArrayList<>();

    static void tarjan(int u, int fa) {
        dfn.set(u, ++cnt);
        low.set(u, cnt);
        for (int v : vec.get(u)) {
            if (dfn.get(v) == 0) {
                tarjan(v, u);
                low.set(u, Math.min(low.get(u), low.get(v)));
                if (dfn.get(u) < low.get(v)) {
                    ans = Math.min(ans, Math.abs(sum_value - 2 * value.get(v)));
                }
                value.set(u, value.get(u) + value.get(v));
            } else if (v != fa) {
                low.set(u, Math.min(low.get(u), low.get(v)));
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextLong();
        m = scanner.nextLong();
        for (int i = 0; i <= n; i++) {
            dfn.add(0L); low.add(0L); value.add(0L); vec.add(new ArrayList<>());
        }
        for (int i = 1; i <= n; i++) {
            value.set(i, scanner.nextLong());
            sum_value += value.get(i);
        }
        for (int i = 0; i < m; i++) {
            int r1 = scanner.nextInt();
            int r2 = scanner.nextInt();
            vec.get(r1).add(r2);
            vec.get(r2).add(r1);
        }
        tarjan(1, 0);
        if (value.get(1) != sum_value) {
            System.out.println(Math.abs(sum_value - 2 * value.get(1)));
        } else if (ans != maxn) {
            System.out.println(ans);
        } else {
            System.out.println(-1);
        }
    }
}

七、AB 路线

问题描述

小明拿了 n 条线段练习抓娃娃。他将所有线段铺在数轴上，第 i 条线段的左端点在 li，右端点在 ri。小明用 m 个区间去框这些线段，第 i 个区间的范围是 [Li, Ri]。如果一个线段有至少一半的长度被包含在某个区间内，则将其视为被这个区间框住。请计算出每个区间框住了多少个线段？

// 审题：最短路径，BFS 解决图的最短路径问题 // 引入记忆化搜索，used[i][j][k] 标记状态

C++

#include <iostream>
#include <queue>
using namespace std;
const int N = 1e3 + 5;
const int step = 1e1 + 5;
struct node{ int x; int y; int step; };
int n, m, k;
queue<node> q;
bool used[N][N][step];
int res[N][N][step];
char grid[N][N];
int xf[] = {1, -1, 0, 0};
int yf[] = {0, 0, 1, -1};

int BFS(){
    q.push({0, 0, 0});
    while(!q.empty()){ 
        node u = q.front();
        q.pop();
        if(u.x == n - 1 && u.y == m - 1) return res[u.x][u.y][u.step];
        for(int i = 0; i < 4; ++i){
            int X = u.x + xf[i], Y = u.y + yf[i], st = u.step + 1;
            if(X < 0 || X >= n || Y < 0 || Y >= m) continue;
            if(st < k && grid[X][Y] != grid[u.x][u.y]) continue;
            if(st == k && grid[X][Y] == grid[u.x][u.y]) continue;
            st = st % k;
            if(used[X][Y][st]) continue;
            used[X][Y][st] = true;
            res[X][Y][st] = res[u.x][u.y][u.step] + 1;
            q.push({X, Y, st});
        }
    }
    return -1;
}

int main(){
    cin >> n >> m >> k;
    string str;
    for(int i = 0; i < n; ++i){
        cin >> str;
        for(int j = 0; j < m; ++j) grid[i][j] = str[j];
    }
    cout << BFS();
    return 0;
}

Java

import java.util.*;

public class Main {
    static long INF = (long) 1e18;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        sc.nextLine();
        char[][] mg = new char[n][m];
        for (int i = 0; i < n; i++) {
            mg[i] = sc.nextLine().toCharArray();
        }
        LinkedList<Pair> qu = new LinkedList<>();
        qu.add(new Pair(0, 0, 1));
        int[][] d = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        boolean[][][] visited = new boolean[n][m][2 * k];
        for (int step = 0; !qu.isEmpty(); step++) {
            int num = qu.size();
            for (int i = 0; i < num; i++) {
                Pair pair = qu.pollFirst();
                int px = pair.x, py = pair.y, pf = pair.flag;
                if (visited[px][py][pf]) continue;
                visited[px][py][pf] = true;
                if (pair.x == n - 1 && pair.y == m - 1) {
                    System.out.print(step);
                    return;
                }
                for (int j = 0; j < 4; j++) {
                    int x = px + d[j][0];
                    int y = py + d[j][1];
                    int f = (pf + 1) % (2 * k);
                    if (x >= 0 && x < n && y >= 0 && y < m) {
                        if (visited[x][y][f]) continue;
                        if (pf < k && mg[x][y] == 'A' || pf >= k && mg[x][y] == 'B') {
                            qu.addLast(new Pair(x, y, f));
                        }
                    }
                }
            }
        }
        System.out.print(-1);
    }
}
class Pair {
    int x, y, flag;
    public Pair(int x, int y, int flag) {
        this.x = x; this.y = y; this.flag = flag;
    }
}

八、抓娃娃

问题描述

小明拿了 n 条线段练习抓娃娃。他将所有线段铺在数轴上，第 i 条线段的左端点在 li，右端点在 ri。小明用 m 个区间去框这些线段，第 i 个区间的范围是 [Li, Ri]。如果一个线段有至少一半的长度被包含在某个区间内，则将其视为被这个区间框住。请计算出每个区间框住了多少个线段？

// 思路：差分 + 前缀和 // 注意处理边界条件

C++

#include <iostream>
#include <vector>
const int N = 2e6 + 5;
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> res(N, 0);
    for(int i = 0, r, l; i < n; ++i) cin >> l >> r, res[r + l]++;
    for(int i = 1; i < N; ++i) res[i] += res[i - 1];
    for(int i = 1, L, R; i <= m; ++i){
        cin >> L >> R;
        L *= 2; R *= 2;
        if(L == 0) cout << res[R] << endl;
        else cout << res[R] - res[L - 1] << endl;
    }
    return 0;
}

Java

import java.util.Scanner;

public class SegmentQuery {
    public static void main(String[] args) {
        final int N = 2000005;
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] res = new int[N];
        for (int i = 0; i < n; i++) {
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            res[l + r]++;
        }
        for (int i = 1; i < N; i++) {
            res[i] += res[i - 1];
        }
        for (int i = 1; i <= m; i++) {
            int L = scanner.nextInt();
            int R = scanner.nextInt();
            L *= 2; R *= 2;
            int result;
            if (L == 0) {
                result = res[R];
            } else {
                result = res[R] - res[L - 1];
            }
            System.out.println(result);
        }
        scanner.close();
    }
}

知识点：

一、向量、点乘、叉乘

1、向量：

• 定义：兼具大小和方向的量。
• 基本属性：模长、方向。
• 常见运算：加减、数乘、点乘、叉乘。

2、点乘：

• 定义为两向量对应分量乘积之和，结果为标量。
• 应用：判断角度（钝角、直角、锐角）、投影长度、做功。

3、叉乘：

• 二维叉乘求平行四边形面积，除以 2 为三角形面积。
• 应用：判断点与直线关系、线段相交检测。

二、浮点数比较

• 编程中通常不用==号比较浮点数，建议使用 abs(a-b)<1e-6。

三、map 与 unordered_map

• map 底层为红黑树，效率 O(logN)。
• unordered_map 底层为哈希表，效率 O(1)。

四、极大值

• INT32_MAX: 约 2.15 × 10⁹。
• INT64_MAX: 约 9.22 × 10¹⁸。
• 0x3f3f3f3f3f3f3f3f: 常用作伪最大值。

五、广搜 (BFS) 与深搜 (DFS)

• 广搜：队列实现，适合最短路径、层序遍历。
• 深搜：递归/栈实现，适合路径寻找、回溯、组合问题。

六、vector 的比较方案

• map 支持 vector 作为键（字典序比较）。
• unordered_map 不支持 vector 作为键（需哈希函数）。