北京航空航天大学—计算机考研复试机试真题(2)
- 2026-11-02 13:57:18
考点分析
真题详解
连续合数段
问题描述
给定区间 [a,b]，输出这个区间里最长的连续合数段。
输入格式
一行，两个整数 a,b。
输出格式
一行，输出最长的连续合数段。
如果答案不唯一，则输出首项最小的那一段。
数据范围
a,b都在[1,10000]
输入样例
1 10
输出样例
8 9 10
思考
先用埃氏筛标记 [1, b] 中的质数，然后扫描区间 [a, b]，找出最长的连续合数段。
合数判断：x > 2 && !isPrime[x]。
若长度相同，因为从左到右扫描，保留先出现的即可，即首项最小。
复杂度：筛法 O(b log log b)
代码
#include<bits/stdc++.h>using namespace std;intmain(){int a, b;cin >> a >> b;vector<bool> isPrime(b + 1, true);if (b >= 0) isPrime[0] = false;if (b >= 1) isPrime[1] = false;for (int i = 2; i * i <= b; ++i) {if (isPrime[i]) {for (long long j = 1LL * i * i; j <= b; j += i) {isPrime[j] = false;}}}auto isComposite = [&](int x) {return x >= 2 && !isPrime[x];};int bestL = -1, bestR = -1, bestLen = 0;int curL = -1;for (int i = a; i <= b; ++i) {if (isComposite(i)) {if (curL == -1) curL = i;} else {if (curL != -1) {int curR = i - 1;int len = curR - curL + 1;if (len > bestLen) {bestLen = len;bestL = curL;bestR = curR;}curL = -1;}}}// 处理区间末尾的连续合数段if (curL != -1) {int curR = b;int len = curR - curL + 1;if (len > bestLen) {bestLen = len;bestL = curL;bestR = curR;}}// 输出最长连续合数段中的所有合数for (int i = bestL; i <= bestR; ++i) {if (i != bestL) cout << ' ';cout << i;}cout << '\n';return 0;}
素数
问题描述
输入一个整数 n，要求输出所有从 1到这个整数之间(不包括 1和这个整数)个位为 1的素数，如果没有则输出 −1。
输入格式
输入包含多组测试数据。
每组数据占一行，包含一个整数 n。
输出格式
每组数据输出占一行，由小到大输出所有满足条件的素数，素数之间单个空格隔开。如果没有则输出 −1。
数据范围
2≤n≤10000,
输入最多包含 100组数据。
输入样例
100
输出样例
11 31 41 61 71
思考
使用埃氏筛预处理 1~10000 内的所有素数。
对每组输入的 n，遍历 2 ~ n-1，因为题目要求不包括 1 和 n。
判断条件为：isPrime[x] && x % 10 == 1，即该数是素数且个位为 1。
代码
#include<bits/stdc++.h>using namespace std;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);const int MAXN = 10000;// 埃氏筛预处理素数vector<bool> isPrime(MAXN + 1, true);isPrime[0] = isPrime[1] = false;for (int i = 2; i * i <= MAXN; ++i) {if (isPrime[i]) {for (int j = i * i; j <= MAXN; j += i) {isPrime[j] = false;}}}int n;while (cin >> n) {bool first = true;// 范围是 1 到 n 之间，不包括 1 和 nfor (int x = 2; x < n; ++x) {if (isPrime[x] && x % 10 == 1) {if (!first) cout << ' ';cout << x;first = false;}}if (first) {cout << -1;}cout << '\n';}return 0;}
机场登机口调整模拟
问题描述
假设某机场所有登机口（Gate）呈树形排列（树的度为 3），安检处为树的根，如下图所示。
图中的分叉结点（编号大于等于 100）表示分叉路口，登机口用小于 100 的编号表示（其一定是一个叶结点）。
通过对机场所有出发航班的日志分析，得知每个登机口每天的平均发送旅客流量。
作为提升机场服务水平的一个措施，在不改变所有航班相对关系的情况下（即：出发时间不变，原在同一登机口的航班不变），仅改变登机口（例如：将 3号登机口改到 5号登机口的位置），使得整体旅客到登机口的时间有所减少（即：从安检口到登机口所经过的分叉路口最少）。
编写程序模拟上述登机口的调整，登机口调整规则如下：
首先按照由大到小的顺序对输入的登机口流量进行排序，流量相同的按照登机口编号由小到大排序；
从上述登机口树的树根开始，按照从上到下（安检口在最上方）、从左到右的顺序，依次放置上面排序后的登机口。
例如上图的树中，若只考虑登机口，则从上到下有三层，第一层从左到右的顺序为：5、6、14、13，第二层从左到右的顺序为：7、8、9、10、1、2、18、17、16、15，第三层从左到右的顺序为：11、12、3、4、20、19。
若按规则 1排序后流量由大至小的前五个登机口为 3、12、16、20、15，则将流量最大的 3号登机口调整到最上层且最左边的位置（即：5号登机口的位置），12号调整到 6号，16号调整到 14号，20 号调整到 13号，15号调整到第二层最左边的位置（即 7号登机口的位置）。
输入格式
首先输入一个整数表示树结点关系的条目数。
接着在下一行开始，按层次从根开始依次输入树结点之间的关系。其中分叉结点编号从数字 100开始（树根结点编号为 100，其它分叉结点编号没有规律但不会重复），登机口为编号小于 100的数字（编号没有规律但不会重复，其一定是一个叶结点）。
树中结点间关系用下面方式描述：
R S1 S2 S3
其中 R为分叉结点，从左至右 S1,S2,S3分别为树叉 R的子结点，其可为树叉或登机口，由于树的度为 3，S1,S2,S3中至多可以 2个为空，该项为空时用 -1 表示。
如：
100 101 102 103表明编号 100的树根有三个子叉，编号分别为 101、102和 103。
又如：
104 7 8 -1 表明树叉 104上有 2个编号分别为 7和 8
的登机口。
假设分叉结点数不超过 100个。
分叉结点输入的顺序不确定，但可以确定：输入某个分叉结点信息时，其父结点的信息已经输入。
在输入完树结点关系后，接下来输入登机口的流量信息，每个登机口流量信息分占一行，分别包括登机口编号（ 1∼99之间的整数）和流量（大于 0的整数），两整数间以一个空格分隔。
输出格式
按照上述调整规则中排序后的顺序（即按旅客流量由大到小，流量相同的按照登机口编号由小到大）依次分行输出每个登机口的调整结果：先输出调整前的登机口编号，再输出要调整到的登机口编号。编号间均以一个空格分隔。
数据范围
分叉结点数量 [1,100]，
分叉结点编号不超过 300。
登机口数量 [1,99]，
流量数据范围 [1,10000]
输入样例
12
100 101 102 103
103 14 108 13
101 5 104 6
104 7 8 -1
102 105 106 107
106 1 110 2
108 16 15 -1
107 18 111 17
110 3 4 -1
105 9 109 10
111 20 19 -1
109 11 12 -1
17 865
5 668
20 3000
13 1020
11 980
8 2202
15 1897
6 1001
14 922
7 2178
19 2189
1 1267
12 3281
2 980
18 1020
10 980
3 1876
9 1197
16 980
4 576
输出样例
12 5
20 6
8 14
19 13
7 7
15 8
3 9
1 10
9 1
13 2
18 18
6 17
2 16
10 15
11 11
16 12
14 3
17 4
5 20
4 19
思考
建树：
分叉结点编号均 >= 100，登机口编号均 < 100。用 children 记录每个分叉结点的子结点，并保持输入时从左到右的顺序。
得到目标位置顺序：
从根结点 100 开始进行层序遍历（BFS）。由于题目要求“从上到下、从左到右”，层序遍历恰好满足。遍历时，遇到编号 < 100 的结点就是登机口，将其加入 positions 数组。
排序登机口：
根据规则，按流量从大到小排序；流量相同时按登机口编号从小到大排序。
配对输出：
排序后的第 i 个登机口，调整到 positions[i] 所表示的登机口位置。输出“原登机口编号 目标位置编号”。
该程序时间复杂度为 O(m + n log n)，其中 n 为登机口数量，完全满足数据范围。
代码
#include<bits/stdc++.h>using namespace std;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int m;if (!(cin >> m)) return 0;unordered_map<int, vector<int>> children;// 读入树的分叉结点关系for (int i = 0; i < m; ++i) {int R, S1, S2, S3;cin >> R >> S1 >> S2 >> S3;vector<int> v;if (S1 != -1) v.push_back(S1);if (S2 != -1) v.push_back(S2);if (S3 != -1) v.push_back(S3);children[R] = v;}// 层序遍历，收集登机口位置序列// 从上到下、从左到右vector<int> positions;queue<int> q;q.push(100); // 根结点编号为 100while (!q.empty()) {int u = q.front();q.pop();if (u < 100) {// 登机口（叶结点）positions.push_back(u);} else {// 分叉结点，按从左到右顺序入队for (int v : children[u]) {q.push(v);}}}// 读入每个登机口的流量vector<pair<int, int>> gates; // {登机口编号, 流量}int id, flow;while (cin >> id >> flow) {gates.push_back({id, flow});}// 排序：流量从大到小；流量相同按登机口编号从小到大sort(gates.begin(), gates.end(), [](const pair<int, int>& a, const pair<int, int>& b) {if (a.second != b.second) return a.second > b.second;return a.first < b.first;});// 依次与位置序列配对输出for (size_t i = 0; i < gates.size(); ++i) {cout << gates[i].first << ' ' << positions[i] << '\n';}return 0;}
