淘天笔试 淘天笔试题 0419
笔试时间：2025年04月19日
历史笔试传送门：
第一题
题目
给定长度为 n 的正整数序列 a = (a₁, a₂, …, aₙ)，小莱希望将序列恰好划分成 k 个不相交的连续区间（段），使得每一段内都存在一个长度为 m 的子序列（不要求连续），恰好是整数 1,2,…,m 的一个排列。求在所有合法划分方案中，最大的 m。若不存在任何合法方案，输出 0。
输入描述
第一行：整数 T（1 ≤ T ≤ 100），表示测试组数。每组第一行：n k（1 ≤ k ≤ n ≤ 2×10^5）。
第二行：n 个整数 aᵢ（1 ≤ aᵢ ≤ n）。保证所有测试中 ∑n ≤ 2×10^5。
输出描述
对每组测试，输出一行： 如果无任何合法划分，输出 0； 否则输出最大的 m。
样例输入
2
11 4
1 2 3 2 1 2 1 3 1 2 3
5 1
1 2 3 4 5
样例输出
2
5
解释：对于 11 4：可划分为 [1..3],[4..5],[6..7],[8..11] 4 段，每段都含子序列 {1,2}，故 m_max=2。 对于 5 1：整段包含 {1,2,3,4,5} ，故 m_max=5。
参考题解
先统计 1…n 中每个数的出现次数，确定最大的上界 在 [1,上界] 内二分 m，对于每个 m，贪心地在原序列中扫描、收集不超过 m 的不同元素，凑齐 m 个就划分一段，若能得到 k 段则 m 可行，否则向下搜索。
C++：[此代码未进行大量数据的测试，仅供参考]
// C++ 版本
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int size, groups_required;
cin >> size >> groups_required;
vector<int> data(size);
for (int i = 0; i < size; i++) {
cin >> data[i];
}
// 统计每个 1..size 出现的频次
vector<int> freq(size + 2, 0);
for (int v : data) {
if (v >= 1 && v <= size)
freq[v]++;
}
// 找到最大的 max_prefix，使得对所有 i ≤ max_prefix，freq[i] ≥ groups_required
int max_prefix = 0;
for (int i = 1; i <= size; i++) {
if (freq[i] < groups_required)
break;
max_prefix = i;
}
int left = 1, right = max_prefix, result = 0;
vector<int> last_seen(size + 2, 0);
int timestamp = 1;
while (left <= right) {
int mid = (left + right) / 2;
int group_count = 0;
int current_count = 0;
// 贪心地从 data 中摘取 ≤ mid 的不同元素
for (int v : data) {
if (v <= mid && last_seen[v] != timestamp) {
last_seen[v] = timestamp;
current_count++;
if (current_count == mid) {
group_count++;
timestamp++;
current_count = 0;
if (group_count == groups_required)
break;
}
}
}
if (group_count >= groups_required) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
cout << result << "\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 size = Integer.parseInt(st.nextToken());
int groupsRequired = Integer.parseInt(st.nextToken());
st = new StringTokenizer(in.readLine());
int[] data = new int[size];
for (int i = 0; i < size; i++) {
data[i] = Integer.parseInt(st.nextToken());
}
// 统计每个 1..size 出现的频次
int[] freq = new int[size + 2];
for (int v : data) {
if (v >= 1 && v <= size) {
freq[v]++;
}
}
// 找到最大的 maxPrefix
int maxPrefix = 0;
for (int i = 1; i <= size; i++) {
if (freq[i] < groupsRequired) break;
maxPrefix = i;
}
int left = 1, right = maxPrefix, result = 0;
int[] lastSeen = new int[size + 2];
int timestamp = 1;
while (left <= right) {
int mid = (left + right) / 2;
int groupCount = 0;
int currentCount = 0;
// 贪心地从 data 中摘取 ≤ mid 的不同元素
for (int v : data) {
if (v <= mid && lastSeen[v] != timestamp) {
lastSeen[v] = timestamp;
currentCount++;
if (currentCount == mid) {
groupCount++;
timestamp++;
currentCount = 0;
if (groupCount == groupsRequired) break;
}
}
}
if (groupCount >= groupsRequired) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
out.println(result);
}
out.flush();
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
import sys def main(): input = sys.stdin.readline test_cases = int(input()) for _ in range(test_cases): size, groups_required = map(int, input().split()) data = list(map(int, input().split())) # 统计每个 1..size 出现的频次 freq = [0] * (size + 2) for value in data: if 1 <= value <= size: freq[value] += 1 # 找到最大的 max_prefix，使得对所有 i ≤ max_prefix，freq[i] ≥ groups_required max_prefix = 0 for i in range(1, size + 1): if freq[i] < groups_required: break max_prefix = i # 在 [1..max_prefix] 区间内二分查找最优的 m left, right = 1, max_prefix result = 0 last_seen = [0] * (size + 2) timestamp = 1 while left <= right: mid = (left + right) // 2 group_count = 0 # 已完成的组数 current_count = 0 # 当前组已收集的不同元素数 # 贪心地从 data 中摘取 ≤ mid 的不同元素，集齐 mid 个就成一组 for value in data: if value <= mid and last_seen[value] != timestamp: last_seen[value] = timestamp current_count += 1 if current_count == mid: group_count += 1 timestamp += 1 current_count = 0 if group_count == groups_required: break if group_count >= groups_required: result = mid left = mid + 1 else: right = mid - 1 sys.stdout.write(str(result) + "\n") if __name__ == "__main__": main()
第二题
题目
给定一个仅由小写字母和 ? 字符组成的字符串 s。小红希望将字符串中的每个 ? 字符替换成某个小写字母，使得在最终替换后的字符串中，子串 "tao" 出现次数与子串 "tian" 出现次数之和尽可能大。 例如，对于字符串 "xxtaotianxxx"，其中包含一个 "tao" 和一个 "tian"，总计出现次数 1+1=2。
输入描述
输入一个由小写字母和 ? 组成的字符串 s，满足 1 ≤ |s| ≤ 2×10⁵。
输出描述
输出替换后的字符串（将所有 ? 替换为小写字母后的结果）。如果存在多种最优替换方案，输出任意一种即可，系统会自动校验。
样例输入
ta???an
样例输出
taotian
参考题解
1.模式匹配预处理将目标子串 “tao” 和 “tian” 插入到一个 Aho–Corasick 字典树中，标记每个终结节点的匹配贡献（out[u] 表示到达状态 u 时能额外得到多少次匹配）。 构建失败指针 fail[u]，并将失败指针指向的状态上的 out 累加到当前状态，确保在自动机转移时能正确统计所有重叠匹配。2.状态转移表对于字母表中每个字母，预先计算从任意状态 u 读入该字母后应跳转到哪个状态 go[u][c]，这样在 DP 时可以 O(1) 获得下一状态。3.动态规划定义 dp[i][u] 为处理到原串第 i 个字符（0≤i<n）后，自动机处于状态 u 时能获得的最大匹配数。为了节省空间，只保留一维数组 dp[u]，每次滚动更新。 当当前字符是固定字母时，只沿一个字母分支转移；如果是 ?，则枚举 26 个小写字母，尝试所有可能的转移，选出得分最高的。 每次转移时加上 out[v]，即到新状态 v 时新匹配到的次数。回溯重建在 DP 过程中记录每一步的最优前驱状态和使用的字符。最后在所有状态中选取最终得分最大的状态 end_state，从尾到头依次回溯，恢复出每个位置应该填的字母。5.时间与空间复杂度构建自动机：O(ΣL)（ΣL=所有模式长度之和，固定为常量） DP 转移：O(n · A · S)，其中 n=|s|，A=26，S=自动机状态数（约为 ΣL）；在最坏情况下 S≈7，故整体≈O(26n) 空间：O(n·S) 用于回溯指针，若只要输出结果，也可压缩为 O(S) 再额外保存一次决策，复合常数开销可接受。
C++：[此代码未进行大量数据的测试，仅供参考]
// C++ 版本
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MIN / 4;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
string s;
if(!getline(cin, s)) return 0;
int n = s.size();
vector<string> patterns = {"tao", "tian"};
// 构建 Trie
vector<array<int,26>> go_trie;
vector<int> out, fail;
go_trie.push_back(array<int,26>{});
out.push_back(0);
for(auto &row: go_trie.back()) row = -1;
for(auto &pat: patterns){
int u = 0;
for(char ch: pat){
int c = ch - 'a';
if(go_trie[u][c] == -1){
go_trie[u][c] = go_trie.size();
go_trie.push_back(array<int,26>{});
out.push_back(0);
for(auto &r: go_trie.back()) r = -
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
