考点分析
真题详解
字符串匹配
问题描述
给定一个包含 n个字符串的字符串数组 s1,s2,…,sn和一个短字符串 p，找出字符串数组中所有能够和短字符串匹配的字符串。
匹配时不区分大小写，短字符串中可能包含若干个用中括号表示的模式匹配。
例如，对于 aa[123]bb，字符串 aa1bb、aa2bb、aa3bb 均可与其匹配（每次匹配只能与中括号中的任意单个字符进行匹配）。
输入格式
第一行包含整数 n，表示字符串数组中的字符串个数。
接下来 n行，第 i行包含一个字符串表示 si。
最后一行，包含一个字符串表示 p。
输出格式
输出可以匹配的字符串的下标和该字符串。
数据范围
1≤n≤1000,
si的长度不超过 10,
p的长度不超过 50,
所有字符串中只包含大小写字母、数字、[]。
输入样例
4
Aab
a2B
ab
ABB
a[a2b]b
输出样例
1 Aab
2 a2B
4 ABB
思考
可以先把模式串 p 解析成若干个匹配单元：
普通字符：一个固定字符；
中括号：一个字符集合，表示可以匹配集合中的任意一个字符。
然后对于每个字符串 s_i：
判断长度是否等于匹配单元数量；
逐个字符匹配；
如果是普通字符，判断是否相同；
如果是字符集合，判断当前字符是否在集合中；
比较时统一转成小写，实现不区分大小写。
代码
#include<bits/stdc++.h>using namespace std;struct Token {bool isSet; // 是否为中括号字符集合char ch; // 如果是普通字符，记录该字符，统一转小写bool in[128]; // 如果是字符集合，in[c] 表示字符 c 是否可匹配Token() : isSet(false), ch(0) {memset(in, false, sizeof(in));}};// 转小写chartoLowerChar(char c){if (c >= 'A' && c <= 'Z') return c - 'A' + 'a';return c;}// 解析模式串 pvector<Token> parsePattern(const string& p){vector<Token> pattern;for (int i = 0; i < (int)p.size(); ) {if (p[i] == '[') {Token token;token.isSet = true;int j = i + 1;while (j < (int)p.size() && p[j] != ']') {char c = toLowerChar(p[j]);token.in[(unsigned char)c] = true;++j;}pattern.push_back(token);i = j + 1; // 跳过 ']'} else {Token token;token.isSet = false;token.ch = toLowerChar(p[i]);pattern.push_back(token);++i;}}return pattern;}// 判断字符串 s 是否可以匹配模式 patternboolcheck(const string& s, const vector<Token>& pattern){if (s.size() != pattern.size()) return false;for (int i = 0; i < (int)s.size(); ++i) {char c = toLowerChar(s[i]);if (pattern[i].isSet) {if (!pattern[i].in[(unsigned char)c]) {return false;}} else {if (c != pattern[i].ch) {return false;}}}return true;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<string> s(n);for (int i = 0; i < n; ++i) {cin >> s[i];}string p;cin >> p;vector<Token> pattern = parsePattern(p);for (int i = 0; i < n; ++i) {if (check(s[i], pattern)) {// 按题目 s1,s2,...,sn 的下标习惯，输出从 1 开始的下标cout << i + 1 << " " << s[i] << '\n';}}return 0;}
空闲块
问题描述
在操作系统中，空闲存储空间通常以空闲块链表方式组织，每个块包含块起始位置、块长度及一个指向下一块的指针。
空闲块按照存储位置升序组织，最后一块指向第一块（构成循环链表）。
当有空间申请请求时，按照如下原则在空闲块循环链表中寻找并分配空闲块：
1. 从当前位置开始遍历空闲块链表（初始是从地址最小的第一个空闲块开始），寻找满足条件的最小块（即：大于等于请求空间的最小空闲块，如果有多个大小相同的最小空闲块，则选择遍历遇到的第一个最小空闲块）（最佳适应原则）；
2. 如果选择的空闲块恰好与请求的大小相符合，则将它从链表中移除并返回给用户；这时当前位置变为移除的空闲块指向的下一空闲块；
3. 如果选择的空闲块大于所申请的空间大小，则将大小合适的空闲块返回给用户，剩下的部分留在空闲块链表中，且剩下位置的起始地址不变；这时当前位置仍然为该空闲块；
4. 如果找不到足够大的空闲块，则申请失败；这时当前位置不变。
编写程序，模拟上述空闲空间申请。
输入格式
第一行包含正整数 N，表示空闲块个数。
接下来 N行，每行包含两个正整数，按照起始位置由小到大的顺序依次描述每个空闲块的起始位置和长度。
最后一行包含若干正整数，按照申请的先后顺序依次描述每个申请的空间大小，最后以一个 -1 表示结束。
输出格式
按照上述原则模拟完空闲空间申请后，输出当前空闲空间链表状态，即从当前位置开始，遍历链表，分行输出剩余空闲块的起始位置和长度，位置和长度之间以一个空格分隔。
若申请完后，链表中没有空闲块，则什么都不输出。
数据范围
1≤N≤100,
申请请求的个数范围 [1,100]，
每个空闲块的起始位置和长度以及每个申请的空间大小的取值范围 [1,10^9]。
思考
由于 N ≤ 100，申请次数 ≤ 100，可以直接用数组模拟循环链表，维护每个结点的 prev、next 指针以及删除标记。
代码
#include<bits/stdc++.h>using namespace std;struct Node {long long start; // 起始地址long long len; // 长度int next; // 后继结点编号int prev; // 前驱结点编号bool alive; // 是否仍在链表中} nodes[105];intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int N;cin >> N;for (int i = 0; i < N; ++i) {cin >> nodes[i].start >> nodes[i].len;nodes[i].alive = true;}// 构建循环链表for (int i = 0; i < N; ++i) {nodes[i].next = (i + 1) % N;nodes[i].prev = (i - 1 + N) % N;}int current = 0; // 初始当前位置为地址最小的第一个空闲块long long req;while (cin >> req && req != -1) {if (current == -1) continue; // 链表为空，直接忽略后续请求// 从当前位置开始遍历一圈，寻找满足条件的最小块int best = -1;long long bestLen = LLONG_MAX;int cur = current;do {if (nodes[cur].alive && nodes[cur].len >= req) {// 只有严格小于才更新，保证相同长度时保留先遍历到的if (nodes[cur].len < bestLen) {bestLen = nodes[cur].len;best = cur;}}cur = nodes[cur].next;} while (cur != current);if (best == -1) {// 找不到足够大的空闲块，当前位置不变continue;}if (nodes[best].len == req) {// 恰好相等：删除该空闲块int nxt = nodes[best].next;if (nxt == best) {// 链表中只有一个结点nodes[best].alive = false;current = -1;} else {int prv = nodes[best].prev;nodes[prv].next = nxt;nodes[nxt].prev = prv;nodes[best].alive = false;current = nxt; // 当前位置变为被删除块的后继}} else {// 大于申请大小：起始地址不变，长度减少nodes[best].len -= req;current = best; // 当前位置变为该空闲块}}// 输出最终链表状态（从当前位置开始）if (current == -1) {return 0;}int cur = current;do {cout << nodes[cur].start << " " << nodes[cur].len << "\n";cur = nodes[cur].next;} while (cur != current);return 0;}
旋转矩阵
问题描述
任意输入两个 9阶以下矩阵，要求判断第二个是否是第一个的旋转矩阵（顺时针），如果是，输出旋转角度（0、90、180、270），如果不是，输出 −1。
输入格式
第一行包含整数 n，表示矩阵阶数。
接下来 n行，每行包含 n个空格隔开的整数，表示第一个矩阵。
再接下来 n行，每行包含 n个空格隔开的整数，表示第二个矩阵。
输出格式
判断第二个矩阵是否是第一个的旋转矩阵，如果是，输出旋转角度（0、90、180、270），如果不是，输出 −1。
如果旋转角度的结果有多个，则输出最小的那个。
数据范围
1≤n≤9,
矩阵中元素取值范围 [1,9]
输入样例
3
1 2 3
4 5 6
7 8 9
7 4 1
8 5 2
9 6 3
输出样例
90
思考
由于矩阵阶数 n ≤ 9，数据量很小，可以直接依次生成 A 旋转 0°、90°、180°、270° 后的矩阵，并与 B 比较。
如果其中某个角度匹配，直接输出该角度。由于按 0、90、180、270 的顺序检查，因此如果有多个角度都成立，会优先输出最小的角度。
顺时针旋转 90° 的公式
设原矩阵为 a，旋转后的矩阵为 b，矩阵阶数为 n，则：b[i][j] = a[n - 1 - j][i];
代码
#include<bits/stdc++.h>using namespace std;using Matrix = vector<vector<long long>>;// 返回矩阵 a 顺时针旋转 90 度后的矩阵Matrix rotate90(const Matrix& a){int n = a.size();Matrix b(n, vector<longlong>(n));for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {b[i][j] = a[n - 1 - j][i];}}return b;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;Matrix A(n, vector<longlong>(n));Matrix B(n, vector<longlong>(n));for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {cin >> A[i][j];}}for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {cin >> B[i][j];}}Matrix cur = A;int angle = 0;int ans = -1;// 依次检查 0、90、180、270 度for (int k = 0; k < 4; ++k) {if (cur == B) {ans = angle;break;}cur = rotate90(cur);angle += 90;}cout << ans << '\n';return 0;}