淘天笔试 淘天笔试题 0816
笔试时间：2025年8月16日
往年笔试合集：
第一题：混乱的数字
给定一个长度为 ( 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;
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
