笔试时间：2024年09月13日 秋招

历史笔试传送门：2023秋招笔试合集

第一题

题目

小牛现在有一个魔法，他可以选择一个字符串里的数字进行加一或者减一。但是如果数字为'9'的话，则不能加一，数字为0'的话，不能减一。小牛现在收到一个字符串s，他希望施展最小的魔法次数后，字符串中有一个长度为k的连续子串，满足子串内的字符都相同。请你输出最小的魔法次数。

输入描述

第一行输入两个正整数n和k，用空格隔开

第二行输一个长度为n的、由数字字符组成的字符串s。

1 <= k <= n <= 200000

输出描述

一个整数，代表最小的魔法次数。

样例输入

5 3

59283

样例输出

6

参考题解

动态规划，最小代价。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <cmath>
#include <climits> // for INT_MAX

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    int res = INT_MAX;
    vector<vector<int>> a(n + 1, vector<int>(10, 0));

    // 填充动态规划数组
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= 9; j++) {
            a[i][j] = a[i - 1][j];
            a[i][j] += abs((s[i - 1] - '0') - j);
        }
    }

    for (int i = k; i <= n; i++) {
        for (int j = 0; j <= 9; j++) {
            res = min(res, a[i][j] - a[i - k][j]);
        }
    }

    cout << res << endl;

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); 
        int k = sc.nextInt(); 
        String s = sc.next();

        int res = (int) 1e9; 
        int[][] a = new int[n + 1][10]; 

        // 填充动态规划数组
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= 9; j++) {
                a[i][j] = a[i - 1][j];
                a[i][j] += Math.abs((s.charAt(i - 1) - '0') - j);
            }
        }
        for (int i = k; i <= n; i++) {
            for (int j = 0; j <= 9; j++) {
                res = Math.min(res, a[i][j] - a[i - k][j]);
            }
        }
        System.out.println(res);
        sc.close();
    }
});

Python：[此代码未进行大量数据的测试，仅供参考]

n = int(input())
k = int(input())
s = input()

res = int(1e9)
a = [[0] * 10 for _ in range(n + 1)]

# 填充动态规划数组
for i in range(1, n + 1):
    for j in range(10):
        a[i][j] = a[i - 1][j]
        a[i][j] += abs((int(s[i - 1]) - j))

for i in range(k, n + 1):
    for j in range(10):
        res = min(res, a[i][j] - a[i - k][j])

print(res)

第二题

题目

给定一张 n 个点 m 条边的无向带权图，保证图联通。定义一条路径的花费为这条路径上边权最大的边的权值。统计图上不同的节点对的数量，满足它们之间所有路径的最小花费恰好为k。两个点之间的路径可能有多条，只需要找花费最小的那条。

输入描述

第一行三个正整数 n,m,k。

接下来 m行，每行三个正整数 x, y, v，表示节点x ,y之间有一条权值为v的边。

1 ≤ n ≤ 10^51 ≤ m ≤ 5*10^51 ≤ v, k≤ 10^9

输出描述

一行一个数字表示答案。

样例输入

5 4 3

1 2 1

1 3 2

1 4 3

1 5 4

样例输出

3

说明：满足要求的点对为(1, 4), (3, 4), (2, 4)

参考题解

带权图的最小生成树与并查集。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric> // for iota
#include <cmath> // for abs

using namespace std;

struct E {
    int u, v, w;
    E(int u, int v, int w) : u(u), v(v), w(w) {}

    // 比较函数用于排序
    bool operator<(const E& other) const {
        return w < other.w;
    }
};

vector<int> p; // 并查集的父节点数组
vector<long> sz; // 连通分量的大小数组

// 查找函数，带路径压缩
int find(int x) {
    if (p[x] != x) {
        p[x] = find(p[x]);
    }
    return p[x];
}

// 合并函数
void union_sets(int x, int y) {
    int rx = find(x);
    int ry = find(y);

    if (rx != ry) {
        p[rx] = r