筆試時間：2024年09月13日 秋招

歷史筆試傳送門：2023秋招筆試合集

第一題

題目

小?，F(xiàn)在有一個魔法，他可以選擇一個字符串里的數(shù)字進行加一或者減一。但是如果數(shù)字為'9'的話，則不能加一，數(shù)字為0'的話，不能減一。小牛現(xiàn)在收到一個字符串s，他希望施展最小的魔法次數(shù)后，字符串中有一個長度為k的連續(xù)子串，滿足子串內(nèi)的字符都相同。請你輸出最小的魔法次數(shù)。

輸入描述

第一行輸入兩個正整數(shù)n和k，用空格隔開

第二行輸一個長度為n的、由數(shù)字字符組成的字符串s。

1 <= k <= n <= 200000

輸出描述

一個整數(shù)，代表最小的魔法次數(shù)。

樣例輸入

5 3

59283

樣例輸出

6

參考題解

動態(tài)規(guī)劃，最小代價。

C++：[此代碼未進行大量數(shù)據(jù)的測試，僅供參考]

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

    // 填充動態(tài)規(guī)劃數(shù)組
    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：[此代碼未進行大量數(shù)據(jù)的測試，僅供參考]

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]; 

        // 填充動態(tài)規(guī)劃數(shù)組
        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：[此代碼未進行大量數(shù)據(jù)的測試，僅供參考]

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

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

# 填充動態(tài)規(guī)劃數(shù)組
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 條邊的無向帶權(quán)圖，保證圖聯(lián)通。定義一條路徑的花費為這條路徑上邊權(quán)最大的邊的權(quán)值。統(tǒng)計圖上不同的節(jié)點對的數(shù)量，滿足它們之間所有路徑的最小花費恰好為k。兩個點之間的路徑可能有多條，只需要找花費最小的那條。

輸入描述

第一行三個正整數(shù) n,m,k。

接下來 m行，每行三個正整數(shù) x, y, v，表示節(jié)點x ,y之間有一條權(quán)值為v的邊。

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

輸出描述

一行一個數(shù)字表示答案。

樣例輸入

5 4 3

1 2 1

1 3 2

1 4 3

1 5 4

樣例輸出

3

說明：滿足要求的點對為(1, 4), (3, 4), (2, 4)

參考題解

帶權(quán)圖的最小生成樹與并查集。

C++：[此代碼未進行大量數(shù)據(jù)的測試，僅供參考]

#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) {}

    // 比較函數(shù)用于排序
    bool operator<(const E& other) const {
        return w < other.w;
    }
};

vector<int> p; // 并查集的父節(jié)點數(shù)組
vector<long> sz; // 連通分量的大小數(shù)組

// 查找函數(shù)，帶路徑壓縮
int find(int x) {
    if (p[x] != x) {
        p[x] = find(p[x]);
    }
    return p[x];
}

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

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