笔试时间：2025年04月20日

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目

多多在玩一个游戏，给定N个字符串，多多可以从第i字符串中提取出最多 义,个字符，被取出字符可以按任意顺序拼接成一个长度为K 的新字符串T，但多多希望这个字符串的字典序尽可能的小。请问多多最终得到的新字符串是什么？

输入描述

第一行，两个整数 N和 K，表示有N 字符串以及目标串T的长度接下来N行，第i行有一个字符串和一个整数:S,x S;是第i个字符串 X;是要求第i个字符串取出的字符个数。

1 <=N<= 1000

1 <= |Si| <= 1000

0 <= Xi <= |Si|

0 <=K<= ∑Xi<= 1000,000

输出描述

一个字符串 T

样例输入

2 3

abb 2

ccaa 1

样例输出

aabe

说明：说明从第2个字符串中取出a，第1个字符串中取出a和 b，拼接成aab的字典序最小。

参考题解

题目要求从每个字符串中取出指定数量的字符，并将这些字符组合成字典序最小的新字符串。关键在于每次选择字符时尽可能选取字典序小的字符。每个字符串排序，取出前Xi个字符。然后将所有取出的字符合并后再次排序，取前K个字符组成结果即可。

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

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

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

import sys
N, K = map(int, input().split())
pool = []
for _ in range(N):
    S, x = input().split()
    x = int(x)
    if x > 0:
        arr = sorted(S)
        pool.extend(arr[:x])
pool.sort()
result = ''.join(pool[:K])
print(result)

第二题

题目

多多制作人正在筹拍一部电影，需要招慕一批演员、为了确保影片顺利拍摄，制作团队需要合理地分配每位演员的片酬,否则演品可能罢演、片酬的分配中团队成员共同商议决定、每立成员对演员的片酬标准有自己独特的评估意见。在团队讨论时，成员们可能会根据演员所饰演角色的复杂性、表演难度、台词量等因素，提出不同的薪资调整建议。例如，某些成员认为某个角色的表演难度较大，应该给予更高的片酬;而另一些成员则认为某个角色的台词较多，也应该提高该演员的报酬。团队成员的意见可以通过会议提出，并且不同成员的意见有可能存在矛盾，每条意见以一对明确的优先顺序给出,例如，某个演员的片酬应该高于另一个演员的片酬。请你帮多多计算在满足所有制作团队成员的意见下，求出一个使得演员片酬总额最小的方案。每位演员的片酬必须至少为100元，且每次调整的增量为10元。

输入描述

第一行为一个整数T,表示共有T个测试数据(1 <= T<= 10)每组测试数据:

第一行为两个整数n和m,分别表示招募演员的总数和制作团队成员提出的意见数(1<= n<= 10000.1<= m <= 20000)

接下来的m行:

每行输入两个整数ai,bi 表示有制作团队成员认为演员ai的片酬应当比演员bi的片酬高(1 <= ai, bi <=n)

输出描述

每组数据输出一个结果，每个结果占一行,如果满足不了所有制作团队成员的意见则输出-1。

对于20%的数据有:1<=n<=100,1<=m <= 200

对于40%的数据有:1<=n<=1000,1<=m<=2000

对于100%的数据有:1<=n<=10000.1<=m <= 20000

样例输入

1

7 4

7 2

4 6

2 5

7 5

样例输出

740

参考题解

根据给出的优先关系构建有向图，通过拓扑排序确定每个演员的最低片酬层级，确保满足所有约束条件。使用拓扑排序计算每个节点的最长路径（层级），确保每个节点的层级满足所有约束，也就是不存在环。层级决定了每个演员的增量次数，所以总片酬为100n + 10总层级。

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

// C++ 版本
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--){
        int n, m;
        cin >> n >> m;
        vector<vector<int>> g(n+1);
        vector<int> indeg(n+1, 0);
        for(int i = 0; i < m; i++){
            int a, b;
            cin >> a >> b;
            // b -> a edge
            g[b].push_back(a);
            indeg[a]++;
        }

        deque<int> dq;
        for(int i = 1; i <= n; i++){
            if(indeg[i] == 0) dq.push_back(i);
        }

        int cnt = 0;
        vector<int> h(n+1, 0);
        while(!dq.empty()){
            int u = dq.front(); dq.pop_front();
            cnt++;
            for(int v: g[u]){
                // 更新最长路径
                h[v] = max(h[v], h[u] + 1);
                if(--indeg[v] == 0){
                    dq.push_back(v);
                }
            }
        }

        if(cnt < n){
            cout << -1 << "\n";
        } else {
            ll sumh = 0;
            for(int i = 1; i <= n; i++) sumh += h[i];
            ll total = 100LL * n + 10LL * sumh;
            cout << total << "\n";
        }
    }
    return 0;
}

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

// Java 版本
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        int T = Integer.parseInt(in.readLine().trim());
        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(in.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            List<List<Integer>> g = new ArrayList<>(n+1);
            for(int i = 0; i <= n; i++) g.add(new ArrayList<>());
            int[] indeg = new int[n+1];

            for(int i = 0; i < m; i++){
                st = new StringTokenizer(in.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                // b -> a
                g.get(b).add(a);
                indeg[a]++;
            }

            Deque<Integer> dq = new ArrayDeque<>();
            for(int i = 1; i <= n; i++){
                if(indeg[i] == 0) dq.addLast(i);
            }

            int cnt = 0;
            int[] h = new int[n+1];
            while(!dq.isEmpty()){
                int u = dq.removeFirst();
                cnt++;
                for(int v : g.get(u)){
                    h[v] = Math.max(h[v], h[u] + 1);
                    if(--indeg[v] == 0){
                        dq.addLast(v);
                    }
                }
            }

            if(cnt < n){
                out.println(-1);
            } else {
                long sumh = 0;
                for(int i = 1; i <= n; i++){
                    sumh += h[i];
                }
                long total = 100L * n + 10L * sumh;
                out.println(total);
            }
        }
        out.flush();
    }
}

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

import sys
from collections import deque
sint = lambda: int(sys.stdin.readline())
mint = lambda: map(int, sys.stdin.readline().split())
lint = lambda: list(map(int, sys.stdin.readline().split()))
def main():
    T = sint()
    out_lines = []
    for _ in range(T):
        n, m = mint()
        g = [[] for _ in range(n+1)]
        indeg = [0] * (n+1)
        for _ in range(m):
            a, b = mint()
            g[b].append(a)
            indeg[a] += 1

        dq = deque(i for i in range(1, n+1) if indeg[i] == 0)
        cnt = 0
        h = [0] * (n+1)
        w