笔试时间：2025年8月16日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：混乱的数字

给定一个长度为 ( n ) 的数组 ({a_1, a_2, \ldots, a_n})，数组中的元素互不相同。我们希望最后能够按严格从大到小的顺序将所有元素输出。为此，我们决定使用若干个队列来对元素进行整理，每一个队列都是先进先出（FIFO）的结构。整个过程分为两个阶段：

分配阶段：按照数组的原始顺序（从 ( i = 1 ) 到 ( n )），选择任意一个队列将 ( a_i ) 放入。然而，如果队列中已经存在元素，则只能将 ( a_i ) 放入与队列中已有元素相同奇偶性的队列中。

输出阶段：当所有元素都分配完毕后，开始输出。每一步，选择任意一个队列，取出其头部的元素并输出。目标是在整个输出过程中得到一个严格递减的序列。

显然，如果不限制队列的数量，那么可以轻松的完成任务。所以，你需要求解，至少需要多少个队列，才能完成上述流程并保证最终输出严格递减。

输入描述

第一行输入一个整数 ( n )（(1 \le n \le 2 \times 10^5)），表示数组的长度。

第二行输入 ( n ) 个整数 ( a_1, a_2, \ldots, a_n )（(0 \le a_i \le 10^9)），表示数组中的元素。

输出描述

输出一个整数，表示至少需要多少个队列，才能完成上述流程并保证最终输出严格递减。

样例输入

9

8 4 2 5 3 7 1 6 0

样例输出

4

说明：在这个样例中，其中一个分配阶段的展示是：第一个队列依次放入 (8, 4, 2)；第二个队列依次放入 (5, 3, 1)；第三个队列放入 (7)；最后第四个队列依次放入 (6, 0)。可以证明四个队列是所需要的最少的队列的数量。

参考题解

C++：

#include <bits/stdc++.h>
using namespace std;

// 计算数组的 LIS 长度（非严格递增：使用 lower_bound）
int lis_length(const vector<long long>& arr) {
    if (arr.empty()) return 0;
    vector<long long> tails;  // tails[len-1] = 长度为 len 的递增子序列的最小尾值
    for (auto x : arr) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return (int)tails.size();
}

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

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> evens, odds;
    evens.reserve(n);
    odds.reserve(n);

    for (int i = 0; i < n; ++i) {
        long long x; cin >> x;
        if ((x & 1LL) == 0) evens.push_back(x);
        else odds.push_back(x);
    }

    cout << lis_length(evens) + lis_length(odds) << "\n";
    return 0;
}

Java：

import java.io.*;
import java.util.*;

public class Main {
    // 简单快速输入
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { this.in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        long nextLong() throws IOException {
            int c; long sgn = 1, x = 0;
            do { c = read(); } while (c <= ' ');
            if (c == '-') { sgn = -1; c = read(); }
            while (c > ' ') { x = x * 10 + (c - '0'); c = read(); }
            return x * sgn;
        }
        int nextInt() throws IOException { return (int) nextLong(); }
    }

    // 计算数组的 LIS 长度（非严格递增：lower_bound）
    static int lisLength(List<Long> arr) {
        if (arr.isEmpty()) return 0;
        ArrayList<Long> tails = new ArrayList<>();
        for (long x : arr) {
            int pos = lowerBound(tails, x);
            if (pos == tails.size()) tails.add(x);
            else tails.set(pos, x);
        }
        return tails.size();
    }

    // 在非降序列表中找第一个 >= target 的位置
    static int lowerBound(ArrayList<Long> a, long target) {
        int l = 0, r = a.size();
        while (l < r) {
            int mid = (l + r) >>> 1;
            if (a.get(mid) >= target) r = mid;
            else l = mid + 1;
        }
        return l;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt();

        ArrayList<Long> evens = new ArrayList<>(n);
        ArrayList<Long> odds  = new ArrayList<>(n);

        for (int i = 0; i < n; i++) {
            long x = fs.nextLong();
            if ((x & 1L) == 0) evens.add(x);
            else odds.add(x);
        }

        int ans = lisLength(evens) + lisLength(odds);
        System.out.println(ans);
    }
}

Python：

import sys
import bisect

input = sys.stdin.read
data = input().split()

n = int(data[0])
a = list(map(int, data[1:]))

evens = [x for x in a if x % 2 == 0]
odds = [x for x in a if x % 2 != 0]

def lis_length(arr):
    ifnot arr:
        return0
    tails = []
    for num in arr:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    return len(tails)

print(lis_length(evens) + lis_length(odds))

第二题：小C的矩阵

给定一个 ( n \times m ) 的矩阵。矩阵第 ( i ) 行第 ( j ) 列的初始值记为 ( v_{i,j} )。

给定一个长度为 ( n ) 的数组 ({a_1, a_2, \ldots, a_n})，以及一个长度为 ( m ) 的数组 ({b_1, b_2, \ldots, b_m})。

对于每个位置 ((i, j)) 的权值为：( w_{i,j} = v_{i,j} \times (a_i + b_j) )

你可以对矩阵进行任意次以下操作（数组 ( a, b ) 不会随操作改变）：

• 交换矩阵中任意两行所有同列的值（行变换）；
• 交换矩阵中任意两列所有同行的值（列变换）。

请通过这些操作，使得矩阵的权值和最大化。

【名词解释】

• 行变换：行变换就是选取两个不同的行，将它们互换。
• 列变换：列变换就是选取两个不同的列，将它们互换。

输入描述

第一行输入两个整数 ( n, m )（(1 \le n, m \le 10^3)），分别表示矩阵的行数和列数。

第二行输入 ( n ) 个整数 ( a_1, a_2, \ldots, a_n )（(1 \le a_i \le 10^4)），表示每行的权值。

第三行输入 ( m ) 个整数 ( b_1, b_2, \ldots, b_m )（(1 \le b_j \le 10^4)），表示每列的权值。

接下来 ( n ) 行，每行输入 ( m ) 个整数 ( v_{i,1}, v_{i,2}, \ldots, v_{i,m} )（(1 \le v_{i,j} \le 10^4)），表示矩阵的初始值。

输出描述

输出一个整数，表示通过任意次行变换或列变换后，矩阵权值和的最大值。

样例输入

1 3

1

1 2 3

3 1 2

样例输出

20

参考题解

C++：

#include <bits/stdc++.h>
using namespace std;

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

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<long long> a(n), b(m);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int j = 0; j < m; ++j) cin >> b[j];

    vector<long long> row_sums(n, 0), col_sums(m, 0);

    // 逐行读入矩阵并累加行和、列和，避免存整矩阵
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            long long v; cin >> v;
            row_sums[i] += v;
            col_sums[j] += v;
        }
    }

    // 降序排序以最大化点积
    sort(a.begin(), a.end(), greater<long long>());
    sort(b.begin(), b.end(), greater<long long>());
    sort(row_sums.begin(), row_sums.end(), greater<long long>());
    sort(col_sums.begin(), col_sums.end(), greater<long long>());

    long long max_total_weight = 0;

    for (int i = 0; i < n;