笔试时间：2025年03月29日

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目：合并代价

小红拿到一个长度为n的数组，下标从1开始。定义一次合井操作为：选定任意的两个相邻的元素ai和ai+1，将它们合并成一个数，其余元素按照原有顺序从前到后依次拼接。这个数等于ai和ai+1的最大值，数组长度减少1。

例如a=[1,2,3,4,5]，小红可以选定a2和a3，合并成3，数组变为[1,3,4,5]，花费代价3。在执行上述的合并操作前，小红可以选择任意两个元索，将它们交换任意次(也可以不交换)。求解，执行恰好n-1轮"合并"操作，使得将数组合并的只剩一个数，最少需要花费多少代价？

输入描述

第一行输入一个整数n，表示数组长度。

第二行输入n个整数a1,a2,..an代表数组元素。

输出描述

输出一个整数，表示最小花费。

样例输入

3

3 2 1

样例输出

5

说明：

在这个样例中，有两种直接合并的方法:

1、先合并3,2，花费max{3,2}=3；再合井{3,1}，花费max{3,1}=3，总花费6。

2、先合并2,1，花费max{2,1}=1；再合幷{3,2}，花费max{3,2}=3，总花费5。

然而，不要忘记了，在开始前。我们还可以进行交换操作。然而，可以证明，再怎么交换也不会存在比5更小的答案。

参考题解

由于可以在操作之前进行任意次交换，那么问题其实就转化成了类似哈夫曼树问题。用一个优先队列维护所有元素，每次取出最小的两个数，把他们中较大的那个重新入队并加到答案中，直到只剩最后一个数。

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

#include <bits/stdc++.h>
usingnamespacestd;
using ll = longlong;
int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    priority_queue<ll, vector<ll>, greater<ll>> q;
    for (auto& x : a) {
        q.push(x);
    }
    ll res = 0;
    while (q.size() > 1) {
        ll x = q.top(); q.pop();
        ll y = q.top(); q.pop();
        res += max(x, y);
        q.push(max(x, y));
    }
    cout << res << endl;
}

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }

        PriorityQueue<Long> q = new PriorityQueue<>(Comparator.naturalOrder());
        for (long x : a) {
            q.add(x);
        }

        long res = 0;
        while (q.size() > 1) {
            long x = q.poll();
            long y = q.poll();
            res += Math.max(x, y);
            q.add(Math.max(x, y));
        }

        System.out.println(res);
    }
}

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

import heapq

def main():
    n = int(input())
    a = list(map(int, input().split()))
    
    q = []
    for x in a:
        heapq.heappush(q, x)
    
    res = 0
    while len(q) > 1:
        x = heapq.heappop(q)
        y = heapq.heappop(q)
        res += max(x, y)
        heapq.heappush(q, max(x, y))
    
    print(res)

if __name__ == "__main__":
    main()

第二题

题目：最少修改次数

小苯有一个长度为n的01串x(下标从1到n)，巧合的是格格也有一个长度恰好为n-1的01串y。(下标从1到n-1)

据说，格格的字符串y是用来匹配小菜的字符串x的，具体来说：

如果yi = 1 (1 ≤ i ≤ n - 1)，则意味着必须有：xi ≠ xi+1

如果yi = 0 (1 ≤ i ≤ n - 1)，则意味着必须有：xi = xi+1

而现在小菜的串并不一定满足y串的匹配要求，因此格格希望小菜修改尽可能少的字符，使得匹配成立，调你帮小菜算一算至少需要修改多少个字符吧。

修改：选择i (1 ≤ i ≤ n)，执行：xi := xi ⊕ 1。（其中⊕表示按位异或或运算。）

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数T (1 ≤ T ≤ 100) 代表数据组数，

每组测试数据描述如下：第一行输入一个正整数n (2 ≤ n ≤ 10^6) 代表x串的长度。

第二行输入一个长度为n，仅由字符'0'和'1'构成的字符串x。

第三行输入一个长度为n-1，仅由字符'0'和'1'构成的字符串y。

除此之外，保证单个测试文件的n之和不超过10^6。

输出描述

对于每组测试数据在单独的一行输出一个整数，表示最少的修改次数。

样例输入

2

8

11001011

1000111

6

101010

11111

样例输出

4

0

说明：

对于第一组测试数据，我们修改x串为"10000101"即可，需要至少4次修改操作。

对于第二组测试数据，我们不需要修改x，因此输出0即可。

参考题解

除第一个位置外，x的每一项都受到y对应位置的影响。确切来说只要决定了x的第一位，那么后面的所有位置都能依次确定。因此做法就是枚举x的第一位是0还是1，进而计算出总花费，两种情况取最小即可。

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

#include <bits/stdc++.h>
usingnamespacestd;
int calc(vector<int> x, string& y, int st) {
    int res = 0;
    int n = y.size();
    if (x[0] != st) {
        res++;
        x[0] ^= 1;
    }
    for (int i = 0; i < n; i++) {
        if (y[i] == '1') {
            if (x[i + 1] == x[i]) {
                x[i + 1] ^= 1;
                res++;
            }
        } else {
            if (x[i + 1] != x[i]) {
                x[i + 1] ^= 1;
                res++;
            }
        }
    }
    return res;
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string z, y;
        cin >> z >> y;
        vector<int> x;
        for (char ch : z) {