笔试时间：2024年09月14日 秋招

历史笔试传送门：2023秋招笔试合集

第一题

题目

有一个序列a1,a2,...,an,牛牛将对这个序列切一刀，使其分为两个不相交的非空子序列，一个序列为a1,a2,...ap，另一个序列为ap+1,...,an。牛牛切割的代价为两个字序列元素和的乘积，牛牛想知道切割代价最小是多少？

输入描述

第一行输入n (1 <= n <= 1e6)

第二行输入n个数 对于每个数ai。(-1e3 <= ai <= 1e3)

输出描述

输出答案

样例输入

5

1 2 3 4 5

样例输出

14

参考题解

遍历第一个序列

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

#include<iostream>
#include<vector>
using namespace std;
#define ll long long
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    int sum = 0;
    ll ans = 1e18;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }

    int lsum = 0;
    for (int i = 0; i < n - 1; i++) {
        lsum += a[i];
        sum -= a[i];
        ans = min(ans, 1LL * sum * lsum);
    }

    cout << ans << "\n";
}

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

import java.util.Scanner;
import java.util.Vector;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Vector<Integer> a = new Vector<>(n);
        int sum = 0;
        long ans = (long) 1e18;

        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            a.add(num);
            sum += num;
        }

        int lsum = 0;
        for (int i = 0; i < n - 1; i++) {
            lsum += a.get(i);
            sum -= a.get(i);
            ans = Math.min(ans, (long) sum * lsum);
        }

        System.out.println(ans);
        sc.close();
    }
}

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

def main():
    n = int(input())
    a = list(map(int, input().split()))
    total_sum = sum(a)
    ans = 1e18

    lsum = 0
    for i in range(n - 1):
        lsum += a[i]
        total_sum -= a[i]
        ans = min(ans, total_sum * lsum)

    print(int(ans))

if __name__ == "__main__":
    main()

第二题

题目

给定n个字符串，并且给定一个长为26的字符串rank，代表每个字母处的位置，请你根据这个rank对这n个字符串进行排序。

输入描述

第一行输入rank(size(rank) = 26)

第二行输入n(1 <= n <= 1000)

接下来n行输入n个字符串，每个字符串的长度不超过1000。

输出描述

输出排序后的字符串

样例输入一

abcdefghijklmnopqrstuvwxyz

3

aaa

aac

aaaa

样例输出一

aaa

aaaa

aac

说明：按照原字母表排序

样例输入二

zyxwvutsrpqonmlkjihgfedcba

3

aaa

aac

aaaa

样例输出二

aac

aaa

aaaa

说明：字母表变了，对应的顺序也变了。

参考题解

根据字母表对每个字母进行替换处理，记录下标，然后排序即可。

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

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int main() {
    string rank;
    cin >> rank;
    int n;
    cin >> n;
    vector<string> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int order[26];
    for (int i = 0; i < 26; i++) {
        order[rank[i] - 'a'] = i;
    }
    vector<pair<string, int>> b(n);
    for (int i = 0; i < n; i++) {
        string s = a[i];
        for (int j = 0; j < s.size(); j++) {
            s[j] = (char)(order[s[j] - 'a'] + 'a');
        }
        b[i] = {s, i};
    }

    sort(b.begin(), b.end());
    for (int i = 0; i < n; i++) {
        cout << a[b[i].second] << "\n";
    }
}

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String rank = sc.next();
        int n = sc.nextInt();
        String[] a = new String[n];
        
        for (int i = 0; i < n; i++) {
            a[i] = sc.next();
        }
        
        int[] order = new int[26];
        for (int i = 0; i < 26; i++) {
            order[rank.charAt(i) - 'a'] = i;
        }

        List<Pair> b = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringBuilder s = new StringBuilder(a[i]);
            for (int j = 0; j < s.length(); j++) {
                s.setCharAt(j, (char) (order[s.charAt(j) - 'a'] + 'a'));
            }
            b.add(new Pair(s.toString(), i));
        }

        Collections.sort(b, Comparator.comparing(p -> p.first));

        for (int i = 0; i < n; i++) {
            System.out.println(a[b.get(i).second]);
        }

        sc.close();
    }

    static class Pair {
        String first;
        int second;

        Pair(Stri