前言
感谢@甘晴void大佬的分享，找到了这套卷子。
一、单项选择题
题干
解析
1. A
2. B
3. A
4. C
5. D
二、简答题
题干
解析
三、算法应用题
3.1 题干
3.1 解析
考试遇到实在画不开的话，最后一层就写文字说明一下吧
3.2 题干
3.2 解析
3.3 题干
3.3 解析
3.4 题干
3.4 解析
3.5 题干
3.5 解析
四、算法设计题
4.1 题干
4.1 解析
4.2 题干
4.2 解析
算法思想
对每个矩形把两条边排序为，把旋转 90° 的情形统一处理；若矩形 i 要能嵌入到矩形 j，则必须同时满足
且
。因此问题化为在二维向量上寻找二维严格增序的最长链。先按 s 升序、在 s 相同时按 t 降序排序（这样可以避免取到同一 s 的多个元素），然后在排序后的序列上对 t 求严格递增的最长子序列（LIS），长度即为答案。
递推式
设排序后序列为。可定义动态规划：
，若不存在则 dp[i]=1。
最终答案 =。
伪代码
由于题目里面给了输入和输出，因此伪代码里就加入了 main 函数。
int solve_one_case(vector<pair<int,int>>& rects) { // 将每个矩形标准化为 (s,t) = (min(a,b), max(a,b)) vector<pair<int,int>> p; for (auto &r : rects) { int s = min(r.first, r.second); int t = max(r.first, r.second); p.emplace_back(s, t); } // 按 s 升序，若 s 相同按 t 降序 sort(p.begin(), p.end(), [](const pair<int,int>& A, const pair<int,int>& B) { if (A.first != B.first) return A.first < B.first; return A.second > B.second; }); // 在 t 上求严格递增的最长子序列（LIS）长度，二分法实现 vector<int> tails; // tails[i] = 最小的尾值，使得存在长度为 i+1 的严格递增子序列 for (auto &pr : p) { int t = pr.second; auto it = lower_bound(tails.begin(), tails.end(), t); // 严格上升 -> lower_bound if (it == tails.end()) tails.push_back(t); else *it = t; } return (int)tails.size(); } int main() { int T; if (!(cin >> T)) return 0; while (T--) { int n; cin >> n; vector<pair<int,int>> rects(n); for (int i = 0; i < n; ++i) cin >> rects[i].first >> rects[i].second; cout << solve_one_case(rects) << '\n'; } return 0; }分析复杂度
时间复杂度：预处理每个矩形并将其边长归一化为 (s,t) 需要 O(n)。对 n 个 (s,t) 对按 s 升序（s 相同时 t 降序）排序耗时 O(nlog n)。在排序后的序列上用二分法维护 tails 求严格递增的 LIS，每个元素插入或替换耗 O(log n)，总共 O(nlog n)。因此总体时间复杂度为 O(nlog n)。
空间复杂度：主要额外空间用于存储归一化后的对 (s,t) 和用于 LIS 的 tails 数组，均为 O(n)。
