笔试时间：2025年9月16日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目描述小红拿到了一个字符串，她可以做任意次以下操作：标记这个字符串中相邻的两个字母，并且这两个字母必须满足以下条件之一：

1. 两个字母相同；
2. 两个字母在字母表中相邻。

已经被标记的字母无法再次被标记。每个字母对应的分数：'a'得1分，'b'得2分，...，'z'得26分。小红想知道，自己最多可以获得多少分？

输入描述

输入一行，只包含小写字母的非空字符串s，代表小红拿到的字符串。 满足约束条件：1 ≤ |s| ≤ 10^6

输出描述

输出一个整数，表示小红可以获得的最大分数。

样例输入

abdbb

样例输出

7

样例说明 第一次标记前两个字母'a'和'b'，获得1+2=3分； 第二次标记后两个字母'b'和'b'，获得2+2=4分； 总分为3+4=7。

参考题解

解题思路：使用动态规划。定义dp[i]表示处理到前i个字符时能获得的最大分数。

• 对于每个位置，有两种选择：不标记当前字母对（跳过）或标记当前字母对（如果满足条件）
• 状态转移：dp[i] = max(dp[i-1], dp[i-2] + score)

C++：

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

void solve() {
    string s;
    cin >> s;
    int n = s.length();
    
    if (n < 2) {
        cout << 0 << endl;
        return;
    }
    
    vector<int> dp(n + 1, 0);
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1];
        char char1 = s[i - 2];
        char char2 = s[i - 1];
        
        if (char1 == char2 || abs(char1 - char2) == 1) {
            int score = (char1 - 'a' + 1) + (char2 - 'a' + 1);
            int current_score_with_pair = dp[i - 2] + score;
            dp[i] = max(dp[i], current_score_with_pair);
        }
    }
    
    cout << dp[n] << endl;
}

int main() {
    solve();
    return 0;
}

Java：

import java.util.*;

public class Solution {
    public static void solve() {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int n = s.length();
        
        if (n < 2) {
            System.out.println(0);
            return;
        }
        
        int[] dp = new int[n + 1];
        
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1];
            char char1 = s.charAt(i - 2);
            char char2 = s.charAt(i - 1);
            
            if (char1 == char2 || Math.abs(char1 - char2) == 1) {
                int score = (char1 - 'a' + 1) + (char2 - 'a' + 1);
                int currentScoreWithPair = dp[i - 2] + score;
                dp[i] = Math.max(dp[i], currentScoreWithPair);
            }
        }
        
        System.out.println(dp[n]);
    }
    
    public static void main(String[] args) {
        solve();
    }
}

Python：

import sys

def solve():
    s = sys.stdin.readline().strip()
    n = len(s)
    
    if n < 2:
        print(0)
        return
    
    dp = [0] * (n + 1)
    
    for i in range(2, n + 1):
        dp[i] = dp[i-1]
        char1 = s[i-2]
        char2 = s[i-1]
        
        if char1 == char2 or abs(ord(char1) - ord(char2)) == 1:
            score = (ord(char1) - ord('a') + 1) + (ord(char2) - ord('a') + 1)
            current_score_with_pair = dp[i-2] + score
            dp[i] = max(dp[i], current_score_with_pair)
    
    print(dp[n])

solve()

第二题

题目描述 大科学家dd在研究转基因白菜，白菜的基因序列由一串大写英文字母构成。只有当白菜的基因序列呈按位非递减形式时，这株白菜的高附加值才会达到最高。 每次可以选择基因序列中的一位进行修改，将字母X修改成Y会产生|X-Y|的改动偏移量。 dd希望通过修改，使得基因序列呈非递减形式，并且总的改动偏移量最小。

输入描述

第一行一个正整数n； 第二行一个长度为n的字符串，表示所给白菜的基因序列； 保证字符串中有且仅有大写英文字母。 1 ≤ n ≤ 10^6

输出描述

输出一个整数，表示最小改动偏移量总和。

样例输入

5

AEEBC

样例输出

5

样例说明 修改成AEEEE：偏移量总和 = |B-E| + |C-E| = 3 + 2 = 5； 修改成ACCCC：偏移量总和 = |E-C| + |E-C| + |B-C| = 2 + 2 + 1 = 5；

参考题解

解题思路：使用动态规划。定义dp[j]表示处理到当前字符时，将当前字符修改为第j个字母（'A'+j）的最小累计偏移量。

• 序列必须非递减，每个位置的字符不能小于前一个位置
• 维护前缀最小值优化转移

C++：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    
    vector<int> dp(26);
    int ord_s0 = s[0];
    int ord_A = 'A';
    
    for (int j = 0; j < 26; j++) {
        dp[j] = abs(ord_s0 - (ord_A + j));
    }
    
    for (int i = 1; i < n; i++) {
        vector<int> new_dp(26);
        int ord_si = s[i];
        int min_prev_cost = INT_MAX;
        
        for (int j = 0; j < 26; j++) {
            min_prev_cost = min(min_prev_cost, dp[j]);
            int cost_change = abs(ord_si - (ord_A + j));
            new_dp[j] = cost_change + min_prev_cost;
        }
        
        dp = new_dp;
    }
    
    int result = *min_element(dp.begin(), dp.end());
    cout << result << endl;
}

int main() {
    solve();
    return 0;
}

Java：

import java.util.*;

public class Solution {
    public static void solve() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        String s = sc.nextLine();
        
        int[] dp = new int[26];
        int ordS0 = s.charAt(0);
        int ordA = 'A';
        
        for (int j = 0;