笔试时间：2025年9月6日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：dp算法

题目描述： 已知一套试卷包含多个dp算法，即X+dp类型的题（保证X不为空且不含'd'和'p'两个字符）。例如sosdp、adp，其拼接起来为sosdpadp，构成了一套完整的试卷。现在需要知道该试卷中存在多少种本质不同的dp算法。保证字符串可以被唯一地分割为一个或多个形如X+dp的段。

输入描述

在一行上输入一个仅由小写字母组成的字符串s（1≤|s|≤10^5），表示试卷。

输出描述

输出一个整数，表示给定试卷中存在多少种不同类型的dp算法。

样例输入

sosdpadp

样例输出

2

参考题解

解题思路： 将字符串分割成多个X+dp的段，每当遇到"dp"时就将之前的部分作为X记录。使用集合去重统计不同的算法类型数量。

C++：

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

void solve() {
    string s;
    cin >> s;
    
    unordered_set<string> unique_types;
    int start_index = 0;
    int i = 0;
    
    while (i < s.length()) {
        if (i + 1 < s.length() && s.substr(i, 2) == "dp") {
            string x = s.substr(start_index, i - start_index);
            if (!x.empty()) {
                unique_types.insert(x);
            }
            start_index = i + 2;
            i += 2;
        } else {
            i++;
        }
    }
    
    cout << unique_types.size() << 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();
        
        Set<String> uniqueTypes = new HashSet<>();
        int startIndex = 0;
        int i = 0;
        
        while (i < s.length()) {
            if (i + 1 < s.length() && s.substring(i, i + 2).equals("dp")) {
                String x = s.substring(startIndex, i);
                if (!x.isEmpty()) {
                    uniqueTypes.add(x);
                }
                startIndex = i + 2;
                i += 2;
            } else {
                i++;
            }
        }
        
        System.out.println(uniqueTypes.size());
    }
    
    public static void main(String[] args) {
        solve();
    }
}

Python：

def solve():
    s = input()
    unique_types = set()
    start_index = 0
    i = 0
    
    while i < len(s):
        if i + 1 < len(s) and s[i:i+2] == 'dp':
            # 找到一个完整的 'dp'
            x = s[start_index:i]
            if x:
                unique_types.add(x)
            start_index = i + 2
            i += 2
        else:
            i += 1
    
    print(len(unique_types))

solve()

第二题：MEX数组最大和

题目描述： 小美有一个长度为n的数组a。可以将a任意重排。定义一个长度为n的数组b，其中b[i]=MEX(a[1],a[2],...,a[i])。需要最大化数组b中的元素之和。MEX定义为没有出现在数组中的最小非负整数。

输入描述

第一行输入一个整数n（1≤n≤10^5），表示数组a的长度

第二行输入n个整数a[i]（0≤a[i]≤10^5），表示数组a的元素

输出描述

第一行输出一个整数，表示b的元素和

第二行输出n个整数，表示重排后的a

样例输入

3

1 0 1

样例输出

5

0 1 1

参考题解

解题思路： 要使MEX的和最大，应尽可能让每个前缀的MEX尽快增大。策略是先按升序排列所有不同的数，然后将剩余的重复数任意排列在末尾。

C++：

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> counts;
    
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        counts[a[i]]++;
    }
    
    vector<int> unique_sorted;
    for (auto& p : counts) {
        unique_sorted.push_back(p.first);
    }
    
    vector<int> output_a;
    for (int x : unique_sorted) {
        output_a.push_back(x);
        counts[x]--;
    }
    
    for (auto& p : counts) {
        while (p.second > 0) {
            output_a.push_back(p.first);
            p.second--;
        }
    }
    
    int total_sum = 0;
    int mex = 0;
    set<int> seen;
    
    for (int i = 0; i < n; i++) {
        seen.insert(output_a[i]);
        while (seen.count(mex)) {
            mex++;
        }
        total_sum += mex;
    }
    
    cout << total_sum << endl;
    for (int i = 0; i < n; i++) {
        if (i > 0) cout << " ";
        cout << output_a[i];
    }
    cout << 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();
        
        Map<Integer, Integer> counts = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int val = sc.nextInt();
            counts.put(val, counts.getOrDefault(val, 0) + 1);