ARTICLE · 1267176
中山大学考研复试机试真题
考点总结
真题详解
排队
问题描述
N个小朋友，编号 1∼N，要排成一队。
在安排每个人的顺序时，有 M个要求，每个要求包含两个整数 a,b，表示小朋友 a要排在小朋友 b的前面。
请你找出符合所有要求的排队顺序。
输入格式
第一行包含整数 N,M。
接下来 M 行，每行包含两个整数 a,b。
输出格式
按排好队列从前到后的顺序在一行内输出每个小朋友的编号。
保证至少存在一个符合条件的顺序。
当符合条件的排队顺序不唯一时，编号更小的小朋友尽量更靠前。
数据范围
1≤N≤500,
1≤M≤5000,
1≤a,b≤N,
输入样例
4 3
1 2
2 3
4 3
输出样例
1 2 4 3
思考
如果要求 a 排在 b 前面，就建一条有向边 a -> b。
统计每个点的入度。
使用拓扑排序。
为了让编号更小的小朋友尽量靠前，每次从当前入度为 0 的点中选择编号最小的点，因此使用小根堆 priority_queue。
最后按顺序输出即可。
代码
#include<bits/stdc++.h>using namespace std;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int N, M;cin >> N >> M;vector<vector<int>> g(N + 1);vector<int> indeg(N + 1, 0);for (int i = 0; i < M; ++i) {int a, b;cin >> a >> b;// a 必须排在 b 前面，建边 a -> bg[a].push_back(b);++indeg[b];}// 小根堆：每次选择当前可选编号最小的小朋友priority_queue<int, vector<int>, greater<int>> pq;for (int i = 1; i <= N; ++i) {if (indeg[i] == 0) {pq.push(i);}}vector<int> ans;ans.reserve(N);while (!pq.empty()) {int u = pq.top();pq.pop();ans.push_back(u);for (int v : g[u]) {--indeg[v];if (indeg[v] == 0) {pq.push(v);}}}for (int i = 0; i < N; ++i) {if (i) cout << ' ';cout << ans[i];}cout << '\n';return 0;}
循环移位
问题描述
给出字符串 A和 B，判断 A是否是 B的进行循环移位得到的子串。
如 A=“ABC”，B=“BCDEFA”，则是。
输入格式
输入包含多组测试数据。
每组数据占一行，包含两个空格隔开的字符串 A和 B。
输出格式
每组数据输出一行结果，如果是循环移位子串输出 yes，否则输出 no。
数据范围
输入最多包含 100组数据。
字符串长度不超过 100，且只包含大写字母。
输入样例
ABC BCDEFA
ABC BADEFC
输出样例
yes
no
思考
如果 A 的长度大于 B，那么 A 不可能成为 B 某个循环移位串的子串，直接输出 no。
B 的所有循环移位串，都可以在 B + B 中找到。
因此只需要判断 A 是否是 B + B 的子串。
使用 C++ string::find 即可完成子串查找。
代码
#include<bits/stdc++.h>using namespace std;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);string A, B;while (cin >> A >> B) {if (A.size() > B.size()) {cout << "no\n";continue;}// B 的所有循环移位都包含在 B + B 中string C = B + B;if (C.find(A) != string::npos) {cout << "yes\n";} else {cout << "no\n";}}return 0;}
括号的匹配
问题描述
在算术表达式中，除了加、减、乘、除等运算外，往往还有括号。
包括有大括号 {}，中括号 []，小括号 ()，尖括号 <> 等。
对于每一对括号，必须先左边括号，然后右边括号；如果有多个括号，则每种类型的左括号和右括号的个数必须相等；对于多重括号的情形，按运算规则，从外到内的括号嵌套顺序为：大括号->中括号->小括号->尖括号，另外相同的括号可以嵌套。
例如，{[()]},{(())},{{}} 为一个合法的表达式，而 ([{}]),{([])},[{<>}] 都是非法的。
输入格式
第一行包含整数 n，表示共有 n个表达式需要判断。
接下来 n行，每行包含一个括号表达式。
输出格式
每行输出一个表达式的判断结果。
如果合法输出 YES，否则输出 NO。
数据范围
1≤n≤100
表达式长度不超过 100。
输入样例
5
{[(<>)]}
[()]
<>()[]{}
[{}]
{()}
输出样例
YES
YES
YES
NO
YES
思考
使用栈模拟括号匹配。
遇到左括号时：
如果栈非空，检查当前左括号的等级是否小于栈顶左括号的等级。等级顺序为 { [ ( <;，从外到内必须非递减。
若满足，则压栈。
遇到右括号时：
栈不能为空，且栈顶必须是与当前右括号同类型的左括号。
匹配成功则弹出。
遍历结束后，栈必须为空，表示所有括号都正确匹配。
输入时使用 getline 读取整行，并过滤掉非括号字符，增强鲁棒性。
代码
#include<bits/stdc++.h>using namespace std;// 括号的嵌套优先级：从外到内必须满足等级非递减// { -> [ -> ( -> <intlevel(char c){if (c == '{') return 0;if (c == '[') return 1;if (c == '(') return 2;if (c == '<') return 3;return -1;}boolisLeft(char c){return c == '{' || c == '[' || c == '(' || c == '<';}boolisRight(char c){return c == '}' || c == ']' || c == ')' || c == '>';}charmatchLeft(char right){if (right == '}') return '{';if (right == ']') return '[';if (right == ')') return '(';if (right == '>') return '<';return 0;}boolcheck(const string& s){stack<char> st;for (char c : s) {if (isLeft(c)) {// 检查嵌套顺序：内层括号的等级不能小于外层括号if (!st.empty() && level(c) < level(st.top())) {return false;}st.push(c);} else if (isRight(c)) {if (st.empty() || st.top() != matchLeft(c)) {return false;}st.pop();}}return st.empty();}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;cin.ignore(numeric_limits<streamsize>::max(), '\n');while (n--) {string line;getline(cin, line);// 只保留括号字符，过滤空格等无关字符string s;for (char c : line) {if (isLeft(c) || isRight(c)) {s.push_back(c);}}cout << (check(s) ? "YES" : "NO") << '\n';}return 0;}
不连续1的子串
问题描述
请计算长度为 N且不含连续 1的 01串的个数。
例如，当 N=3 时，答案为 5，因为长度为 3且不含连续 1
的 01串一共 5个：000,001,010,100,101。
输入格式
一个整数 N。
输出格式
一个整数，表示结果。
数据范围
N<=20
输入样例
3
输出样例
5
思路
设 dp[i] 表示长度为 i 且不含连续 1 的 01 串个数。
最后一位是 0：前 i-1 位任意合法，共 dp[i-1] 种；
最后一位是 1：倒数第二位必须是 0，前 i-2 位任意合法，共 dp[i-2] 种。
所以：dp[i]=dp[i−1]+dp[i−2]
初始值：
dp[0]=1,dp[1]=2
由于 N ≤ 20，直接用 int 即可。
代码
#include<bits/stdc++.h>using namespace std;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int N;cin >> N;// dp[i] 表示长度为 i 且不含连续 1 的 01 串个数// dp[0] = 1（空串）// dp[1] = 2（"0", "1"）// dp[i] = dp[i-1] + dp[i-2]if (N == 0) {cout << 1 << '\n';return 0;}int a = 1, b = 2; // a = dp[0], b = dp[1]if (N == 1) {cout << b << '\n';return 0;}for (int i = 2; i <= N; ++i) {int c = a + b;a = b;b = c;}cout << b << '\n';return 0;}
