笔试时间：2025年10月11日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：挖掘宝石

题目： 小明设计了一个挖掘宝石的小游戏。在游戏中有红宝石、蓝宝石、绿宝石等多种不同类型的宝石，当然也有昂贵的钻石。现在给出一个地图，在地图上有N种不同的宝石。每一种宝石都有一颗或者多颗，同一种宝石每一颗的价值都是相同的。此外，每一种宝石都有一个挖掘时间。在给定的时间内，哪一个玩家挖掘的宝石的总价值最大就是游戏的赢家。现在给出N类不同宝石的数量以及每一类宝石中每一颗的价值和挖掘时间，并且给出一个总的游戏时间T。在不考虑竞争对手的情况下，请问可以得到的最大价值是多少？

输入描述

第1行输入一个正整数N和一个正整数T，分别表示宝石类型的数量和总游戏时间（分钟），两者之间用空格隔开。1 ≤ N ≤ 100，1 ≤ T ≤ 1000。从第2行到第N+1行每一行三个正整数X[i]，Y[i]和Z[i]，分别表示第i类宝石的数量、第i类宝石中一颗宝石的价值和挖掘时间（分钟）。X[i]、Y[i]和Z[i]均不超过100。

输出描述

输出可以得到的最大价值。

样例输入

3 10

2 5 5

3 4 3

2 8 6

样例输出

12

参考题解

解题思路： 二进制拆分：将每种宝石的数量拆分成若干个"二进制数"对应的数量（如1,2,4,8,…），这样可以用这些拆分后的"物品"（每个"物品"代表一定数量的该类宝石），通过类似0-1背包的方式来处理多重背包问题，减少时间复杂度。动态规划数组dp：dp[j]表示使用j分钟能获得的最大价值。初始时所有元素为0。状态转移：对于每类宝石拆分后的每个"物品"，从后往前遍历时间（避免重复选择），如果当前剩余时间j大于等于该"物品"的挖掘时间cost，则更新dp[j]为dp[j]和dp[j-cost]+value中的较大值。

C++：

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

int main() {
    int N, T;
    cin >> N >> T;
    vector<int> dp(T + 1, 0);
    
    for (int i = 0; i < N; ++i) {
        int X, Y, Z;
        cin >> X >> Y >> Z;
        
        // 二进制拆分处理多重背包
        for (int k = 1; X > 0; k <<= 1) {
            int num = min(k, X);
            X -= num;
            int cost = Z * num;  // 该份宝石的总挖掘时间
            int value = Y * num; // 该份宝石的总价值
            
            // 0-1背包思路，从后往前遍历
            for (int j = T; j >= cost; --j) {
                dp[j] = max(dp[j], dp[j - cost] + value);
            }
        }
    }
    
    cout << dp[T] << endl;
    return 0;
}

Java：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int T = scanner.nextInt();
        int[] dp = new int[T + 1];
        
        for (int i = 0; i < N; ++i) {
            int X = scanner.nextInt(); // 宝石数量
            int Y = scanner.nextInt(); // 单颗价值
            int Z = scanner.nextInt(); // 单颗挖掘时间
            
            // 二进制拆分处理多重背包
            for (int k = 1; X > 0; k <<= 1) {
                int num = Math.min(k, X);
                X -= num;
                int cost = Z * num;  // 该份宝石的总挖掘时间
                int value = Y * num; // 该份宝石的总价值
                
                // 0-1背包思路，从后往前遍历
                for (int j = T; j >= cost; --j) {
                    dp[j] = Math.max(dp[j], dp[j - cost] + value);
                }
            }
        }
        
        System.out.println(dp[T]);
        scanner.close();
    }
}

Python：

N, T = map(int, input().split())
dp = [0] * (T + 1)

for _ in range(N):
    X, Y, Z = map(int, input().split())
    
    # 二进制拆分处理多重背包
    k = 1
    while X > 0:
        num = min(k, X)
        X -= num
        cost = Z * num   # 该份宝石的总挖掘时间
        value = Y * num  # 该份宝石的总价值
        
        # 0-1背包思路，从后往前遍历
        for j in range(T, cost - 1, -1):
            dp[j] = max(dp[j], dp[j - cost] + value)
        
        k <<= 1

print(dp[T])

第二题：相似

小A觉得文本中有一些微小错误不会影响人类的正常阅读。同样的，他也希望人工智能也能达成这样的目标。为此他想制作一些测试数据集。小A认为微小错误是这样的：要么只有一个字符被改变；要么是仅有一个字符错位了，被移动到字符串其他地方，而其他字符相对顺序不变。小A认为上述两项错误只能选有最多一项，否则将会让人类也难以辨认原来的单词。小A想验证一下自己的数据集，看看是否都符合此种要求的错误。

输入描述

第一行一个整数t表示数据组数。

对每组数据：第一行1个整数n，表示笔记的长度。

第二行长为n的英文字符串S，表示正确的单词。

第三行长为n的英文字符串T，表示微小错误的单词。

1 ≤ n ≤ 5000，1 ≤ t ≤ 20

输出描述

对每组数据，输出一行Yes或No表示T是否是S发生微小错误后的字符串。

样例输入

3

5

Ababa

aAbab

2

Ab

Ac

2

Ab

Cd

样例输出

Yes

Yes

No

样例说明： 第一组，将最后一个a提到最前面即可。第二组，将最后一个b替换成c即可。第三组无论如何无法通过一次微小错误完成。

参考题解

字符替换判断：遍历两个字符串，统计对应位置不同字符的数量，若数量为1，则满足替换错误条件。字符移动判断：首先检查字符频率，若两个字符串字符频率不同，直接不满足。然后找到两个字符串首尾开始不同的位置l和r，若l>=r，说明无错位。最后检查两种移动情形：s中位置l的字符移到更右位置，或s中位置r的字符移到更左位置，若其中一种情形满足，则符合移动错误条件。

C++：

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

// 检查是否只替换了一个字符
bool isReplace(string s, string t) {
    int diff = 0;
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] != t[i]) {
            diff++;
        }
    }
    return diff == 1;
}

// 检查是否通过一次字符移动得到
bool isMove(string s, string t) {
    if (s == t) {
        return false; // 没变化不算
    }
    
    // 1. 检查字符频率是否相同
    vector<int> cnt(256, 0);
    for (char c : s) {
        cnt[c]++;
    }
    for (char c : t) {
        cnt[c]--;
    }
    for (int count : cnt) {
        if (count != 0) {
            return false;
        }
    }
    
    int n = s.length();
    int l = 0, r = n - 1;
    
    // 2. 找出首尾开始不同的位置
    while (l < n && s[l] == t[l]) {
        l++;
    }
    while (r >= 0 && s[r] == t[r]) {
        r--;
    }
    
    if (l >= r) {
        return false; // 说明没发生错位
    }
    
    // 3. 检查"左移一位"或"右移一位"情形
    // case1: s[l] 移到更右的位置
    bool moveRight = (s[l] == t[r]);
    for (int i = l + 1; i <= r; ++i) {
        if (s[i] != t[i - 1]) {
            moveRight = false;
        }
    }
    
    // case2: s[r] 移到更左的位置
    bool moveLeft = (s[r] == t[l]);
    for (int i = l; i < r; ++i) {
        if (s[i] != t[i + 1]) {
            moveLeft = false;
        }
    }
    
    return moveLeft || moveRight;
}

int main() {
    int T;
    cin >> T;
    
    while (T-- > 0) {
        int n;
        string s, t;
        cin >> n >> s >> t;
        
        if (isReplace(s, t) || isMove(s, t)) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    
    return 0;
}

Java：

import java.util.Scanner;

public class Main {
    // 检查是否只替换了一个字符
    public static boolean isReplace(String s, String t) {
        int diff = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) != t.charAt(i)) {
                diff++;
            }
        }
        return diff == 1;
    }
    
    // 检查是否通过一次字符移动得到
    public static boolean isMove(String s, String t) {
        if (s.equals(t)) {
            return false; // 没变化不算
        }
        
        // 1. 检查字符频率是否相同
        int[] cnt = new int[256];
        for (char c : s.toCharArray()) {
            cnt[c]++;
        }
        for (char c : t.toCharArray()) {
            cnt[c]--;
        }
        for (int count : cnt)