浙江大学—计算机考研机试真题(1)
- 2026-10-31 15:49:56
考点分析
真题详解
一端进 两端出
问题描述
给定一个输入受限的双端队列（即一个端点允许插入和删除，另一个端点只允许删除的双端队列）和一个长度为 N的插入序列。
插入序列中的元素两两不同。
你需要将插入序列中的元素按顺序依次插入到给定队列中。
在插入过程中和插入完成后的任意时刻，你可以随时删除队列中的现有元素（如果有的话）。
将所有元素按删除顺序进行排列可以得到删除序列。
现在，给定 K个删除序列，对于每个删除序列，请你判断其能否通过给定插入序列得到。
输入格式
第一行包含两个整数 N,K。
第二行包含 N 个不同的整数，表示插入序列。
接下来 K行，每行包含一个删除序列，保证每个删除序列都是给定插入序列的一个排列。
输出格式
每个删除序列，输出一行答案，如果该删除序列可以通过给定插入序列得到，则输出 yes，否则输出 no。
数据范围
1≤N≤10^5,
1≤K≤10,
序列中元素的取值范围 [1,10^9]。
输入样例
5 4
10 2 3 4 5
10 3 2 5 4
5 10 3 2 4
2 3 10 4 5
3 5 10 4 2
输出样例
yes
no
yes
yes
思考
把允许插入的端点看作队头 front，则：
插入元素时只能 push_front；
删除元素时可以从 front 或 back 删除；
已插入但未删除的元素顺序为：最近插入的在队头，最早插入的在队尾。
对于每个删除序列，按删除顺序模拟：
记录原插入序列中每个元素的位置 pos[x]。
维护当前双端队列 dq，以及已经插入到队列中的元素个数 p。
依次处理待删除元素 x：
若 pos[x] >= p，说明 x 尚未插入。为了删除 x，必须把插入序列中从 p 到 pos[x] 的元素依次 push_front。插入完成后 x 一定在队头，直接删除队头。
若 pos[x] < p，说明 x 已经插入且尚未删除。此时只能删除队头或队尾，因此 x 必须等于 dq.front() 或 dq.back()，否则无法得到该删除序列。
如果整个删除序列都能成功模拟，则输出 yes，否则输出 no。
每个元素最多插入一次、删除一次，因此单个删除序列时间复杂度为 O(N)，总复杂度 O(KN)。
代码
#include<bits/stdc++.h>using namespace std;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int N, K;cin >> N >> K;vector<int> a(N);unordered_map<int, int> pos;pos.reserve(N * 2 + 10);for (int i = 0; i < N; ++i) {cin >> a[i];pos[a[i]] = i;}while (K--) {deque<int> dq;int p = 0; // 下一个尚未插入的元素位置bool ok = true;for (int i = 0; i < N; ++i) {int x;cin >> x;if (!ok) continue;int idx = pos[x];if (idx >= p) {// x 尚未插入，需要一直插入到 xwhile (p <= idx) {dq.push_front(a[p]);++p;}// 此时 x 在队头，删除它dq.pop_front();} else {// x 已经插入，只能从两端删除if (!dq.empty() && dq.front() == x) {dq.pop_front();} else if (!dq.empty() && dq.back() == x) {dq.pop_back();} else {ok = false;}}}cout << (ok ? "yes" : "no") << '\n';}return 0;}
平方朋友对
问题描述
给定一个正整数 n，我们规定如果两个正整数 A和 B满足，对于任意 0≤i<n
，都可以通过在 A+i后面添加 3位数字（具体添加什么可以自由选择）的方式得到 (B+i)^2，则称 (A,B)是平方朋友对。
例如，当 n=3时，如果 A=73,B=272，则 (A,B)是平方朋友对，因为 73984=272^2,74529=273^2,75076=274^2（下划线部分即为添加的 3位数字）。
现在，给定两个正整数 n,MaxA，请你找到并输出所有满足 A≤MaxA且 (A,B)
是平方朋友对的 A,B。
输入格式
共一行，包含两个正整数 n,MaxA。
输出格式
如果不存在满足条件的 A,B，则输出 No Solution.
否则，每行输出一对满足条件的 A,B，输出时优先输出 A更小的数对，A相同时，优先输出 B更小的数对。
数据范围
1≤n≤100,
1≤MaxA≤10^6。
输入样例
3 85
输出样例
73 272
78 281
82 288
85 293
思考
对于每个 B，检查 n项。
最后将所有满足条件的 (A,B) 按 A 从小到大、A相同时按 B从小到大排序输出。
代码
#include<bits/stdc++.h>using namespace std;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;long long MaxA;cin >> n >> MaxA;vector<pair<long long, long long>> ans;for (long long B = 1; ; ++B) {long long A = B * B / 1000;// A 随着 B 增大单调不减，超过 MaxA 后可直接结束if (A > MaxA) break;// A 必须是正整数if (A == 0) continue;bool ok = true;for (long long i = 1; i < n; ++i) {long long x = B + i;long long cur = x * x / 1000 - i;if (cur != A) {ok = false;break;}}if (ok) {ans.push_back({A, B});}}sort(ans.begin(), ans.end());if (ans.empty()) {cout << "No Solution.\n";} else {for (auto &p : ans) {cout << p.first << ' ' << p.second << '\n';}}return 0;}
前序遍历
问题描述
假设二叉树上各结点的权值互不相同且都为正整数。
给定二叉树的后序遍历和中序遍历，请你输出二叉树的前序遍历的最后一个数字。
输入格式
第一行包含整数 N，表示二叉树结点总数。
第二行给出二叉树的后序遍历序列。
第三行给出二叉树的中序遍历序列。
输出格式
输出二叉树的前序遍历的最后一个数字。
数据范围
1≤N≤50000,
二叉树结点权值范围 [1,10^9]。
输入样例
7
1 2 3 4 5 6 7
2 1 4 3 7 5 6
输出样例
5
思路
前序遍历的顺序是：
根 → 左子树 → 右子树
因此，整棵二叉树前序遍历的最后一个数字，就是沿着“优先走右子树，没有右子树时走左子树”的路径一直走到叶子时得到的节点。
利用后序遍历和中序遍历可以确定每一层的子树：
后序遍历的最后一个元素是当前子树的根；
在中序遍历中找到根的位置，根左边是左子树，根右边是右子树；
如果右子树非空，则答案一定在右子树中；
否则如果左子树非空，则答案一定在左子树中；
否则当前根就是叶子，也就是答案。
由于 N≤50000，递归可能爆栈，因此使用迭代模拟上述过程。
时间复杂度为
O(N)，空间复杂度为 O(N)。
代码
#include<bits/stdc++.h>using namespace std;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int N;cin >> N;vector<int> post(N), in(N);for (int i = 0; i < N; ++i) cin >> post[i];for (int i = 0; i < N; ++i) cin >> in[i];unordered_map<int, int> pos;pos.reserve(N * 2 + 10);for (int i = 0; i < N; ++i) {pos[in[i]] = i;}// 当前子树：// 后序区间 post[L..R]// 中序区间 in[l..r]int L = 0, R = N - 1;int l = 0, r = N - 1;int answer = -1;while (true) {int rootVal = post[R];answer = rootVal;int rootPos = pos[rootVal];int leftSize = rootPos - l;int rightSize = r - rootPos;if (rightSize > 0) {// 进入右子树L = R - rightSize;R = R - 1;l = rootPos + 1;// r 不变} else if (leftSize > 0) {// 没有右子树，进入左子树R = R - 1;r = rootPos - 1;// L 不变，l 不变} else {// 当前节点是叶子break;}}cout << answer << '\n';return 0;}
负载均衡
问题描述
有 N个石子堆成一堆。
你可以对石子堆进行拆分操作，具体为选中一堆现有石子堆，将其中的石子分为两堆（不能为空）。
此外，在任何时候，最小石子堆的石子数量都必须严格大于最大石子堆的石子数量的一半。
我们希望，通过将石子堆进行拆分，最终可以满足：
石子堆的总数量尽可能大，不妨设这个总数量的最大可能值为 M。
满足上一条要求的前提下，最大石子堆石子数量与最小石子堆石子数量之差尽可能小，不妨设这个差的最小可能值为 D。
请你计算并输出 M和 D的值。
输入格式
一个正整数 N。
输出格式
一行，输出 M和 D。
数据范围
2≤N≤200
输入样例
22
输出样例
4 1
思考
用有序数组表示当前所有石子堆的大小，并记忆化搜索。
由于最优拆分中总是优先拆分当前最大的石子堆（拆非最大堆不会比先拆最大堆更优），因此每次只拆分最大堆。拆分时枚举较小的那一份 a，检查是否满足：
拆分后仍满足 2 * min > max；
若拆分后最大堆不唯一，则无法继续拆分，但可作为最终状态更新答案；
若最大堆唯一，则递归继续拆分。
通过哈希表对状态去重，避免重复搜索。数据范围 N ≤ 200，合法状态数量有限，可在时限内完成。
代码
#include<bits/stdc++.h>using namespace std;int N;unordered_map<string, pair<int,int>> memo;pair<int,int> solve(const vector<int>& state){int k = state.size();// 将状态编码为字符串作为哈希键string key(k, 0);for (int i = 0; i < k; ++i) key[i] = (char)state[i];auto it = memo.find(key);if (it != memo.end()) return it->second;int minv = state.front();int maxv = state.back();int diff = maxv - minv;pair<int,int> best = {k, diff}; // 不继续拆分的情况int x = maxv;if (x >= 2) {// 计算次大值及其出现次数int M_other = 0, cnt_other = 0;if (k >= 2) {M_other = state[k-2];for (int i = k - 1; i >= 0; --i) {if (state[i] == M_other) ++cnt_other;else break;}}// 计算 a 的合法下界与上界int low = max(x / 3 + 1, M_other / 2 + 1);int high = x / 2;for (int a = low; a <= high; ++a) {int b = x - a;int new_min = min(minv, a);int new_max = max(M_other, b);if (2 * new_min <= new_max) continue; // 不满足比例条件// 检查新状态中最大堆是否唯一bool max_unique = true;if (new_max == b) {if (b == M_other || a == b) max_unique = false;} else { // new_max == M_other > bif (cnt_other >= 2) max_unique = false;}// 构造拆分后的新状态vector<int> nxt;nxt.reserve(k + 1);for (int i = 0; i < k - 1; ++i) nxt.push_back(state[i]);auto pos = lower_bound(nxt.begin(), nxt.end(), a);nxt.insert(pos, a);pos = lower_bound(nxt.begin(), nxt.end(), b);nxt.insert(pos, b);if (max_unique) {// 最大堆唯一，可以继续拆分pair<int,int> res = solve(nxt);if (res.first > best.first ||(res.first == best.first && res.second < best.second)) {best = res;}} else {// 最大堆不唯一，无法继续拆分，但当前拆分后的状态是合法的最终状态int new_k = k + 1;int new_diff = new_max - new_min;if (new_k > best.first ||(new_k == best.first && new_diff < best.second)) {best = {new_k, new_diff};}}}}memo[key] = best;return best;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cin >> N;vector<int> init = {N};pair<int,int> ans = solve(init);cout << ans.first << ' ' << ans.second << '\n';return 0;}
