考点分析
真题详解
重复者
问题描述
给定一个仅包含一种字符和空格的模板，将之不断重复扩大。
例如，模板如下所示
# # # #那么，第1级的图形为# # # # #第 2级的图形为# # # # # # # # # # # # # # # # # # # # # # # # #模板中包含多少元素，那么任意级别的图形中就包含多少元素。模板或 1级图形中的元素为单个字符，而高等级的图形中的元素为低一级别的图形。现在给定模板，请你输出该模板的第 Q级图形的具体图案。
输入格式
输入包含多组测试数据。
每组数据第一行包含整数 N，表示模板的尺寸大小为 N×N。
接下来 N行，每行包含 N个字符，用来描述模板。
最后一行，包含一个整数 Q，表示所求的图形等级。
当输入 N=0时，表示输入结束。
输出格式
每组数据输出一个所求的具体图案。
数据范围
3≤N≤5,
输出图案保证尺寸不超过 3000×3000,
每个输入最多包含 10组数据。
输入样例
3
# # # #13# # # # #34 OO O OO O OO 20
输出样例
思路
第 1 级就是原模板。之后每一级都把上一级图形看成一个“字符块”：
若模板中当前位置是空格，则放置一个与上一级图形同尺寸的全空格块；
若模板中当前位置不是空格，则放置完整的上一级图形。
由于最终尺寸不超过 3000×3000，可以直接用 vector<string> 逐级扩展。
代码
#include<bits/stdc++.h>using namespace std;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int N;while (cin >> N && N != 0) {cin.ignore(numeric_limits<streamsize>::max(), '\n');vector<string> tmpl(N);for (int i = 0; i < N; ++i) {getline(cin, tmpl[i]);// 处理可能出现的 Windows 换行符if (!tmpl[i].empty() && tmpl[i].back() == '\r') {tmpl[i].pop_back();}// 防止输入行长度异常if ((int)tmpl[i].size() < N) {tmpl[i].resize(N, ' ');} else if ((int)tmpl[i].size() > N) {tmpl[i] = tmpl[i].substr(0, N);}}int Q;cin >> Q;vector<string> cur = tmpl;int curSize = N;// 从第 2 级扩展到第 Q 级for (int level = 2; level <= Q; ++level) {int newSize = curSize * N;vector<string> nxt(newSize, string(newSize, ' '));for (int bi = 0; bi < N; ++bi) {for (int bj = 0; bj < N; ++bj) {// 模板中为空格，则对应块保持全空格if (tmpl[bi][bj] == ' ') continue;int startRow = bi * curSize;int startCol = bj * curSize;// 将上一级图形复制到对应位置for (int i = 0; i < curSize; ++i) {copy(cur[i].begin(), cur[i].end(),nxt[startRow + i].begin() + startCol);}}}cur.swap(nxt);curSize = newSize;}for (const string &line : cur) {cout << line << '\n';}}return 0;}
坠落的蚂蚁
问题描述
一根长度为 1米的木棒上有若干只蚂蚁在爬动。
它们的速度为每秒一厘米或静止不动，方向只有两种，向左或者向右。
如果两只蚂蚁碰头，则它们立即交换速度并继续爬动。
三只蚂蚁碰头，则两边的蚂蚁交换速度，中间的蚂蚁仍然静止。
如果它们爬到了木棒的边缘（0或 100厘米处）则会从木棒上坠落下去。
在某一时刻蚂蚁的位置各不相同且均在整数厘米处（即 1，2，3，…99
厘米），有且只有一只蚂蚁 A速度为 0，其他蚂蚁均在向左或向右爬动。
给出该时刻木棒上的所有蚂蚁位置和初始速度，找出蚂蚁 A从此时刻到坠落所需要的时间。
输入格式
第一行包含一个整数表示蚂蚁的个数 N，之后共有 N行，每一行描述一只蚂蚁的初始状态。
每个初始状态由两个整数组成，中间用空格隔开，第一个数字表示初始位置厘米数 P，第二个数字表示初始方向，−1表示向左，1表示向右，0表示静止。
输出格式
蚂蚁 A从开始到坠落的时间。若不会坠落，输出 Cannot fall!。
数据范围
2≤N≤99,
1≤P≤99
输入样例
4
10 1
90 0
95 -1
98 -1
输出样例
98
思考
维护每只蚂蚁的位置、速度和“是否是 A”。
反复找下一次事件的最短时间：
有蚂蚁到边缘；
或相邻蚂蚁追及。
推进时间，更新位置。
检查 A 是否掉落。
删除已经掉落的蚂蚁。
对同一位置的一组蚂蚁反转速度序列，模拟碰头交换速度。
若没有可发生的事件且 A 静止，则不会掉落。
代码
#include<bits/stdc++.h>using namespace std;struct Ant {double x; // 位置int v; // 速度：-1 向左，1 向右，0 静止bool isA; // 是否是蚂蚁 A};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int N;while (cin >> N) {vector<Ant> ants(N);for (int i = 0; i < N; ++i) {int p, d;cin >> p >> d;ants[i] = {(double)p, d, d == 0};}// 按位置从左到右排序，碰撞只可能发生在相邻蚂蚁之间sort(ants.begin(), ants.end(), [](const Ant &a, const Ant &b) {return a.x < b.x;});const double EPS = 1e-9;const double L = 100.0;double curTime = 0.0;double fallTime = 0.0;bool fallen = false;bool cannotFall = false;while (true) {// 如果木棒上只剩 A，且 A 静止，则永远不会掉落if ((int)ants.size() == 1) {if (ants[0].isA && ants[0].v == 0) {cannotFall = true;} else if (ants[0].isA) {if (ants[0].v == 1)fallTime = curTime + (L - ants[0].x);elsefallTime = curTime + ants[0].x;fallen = true;}break;}// 计算下一次事件的最短时间double tMin = 1e100;// 蚂蚁到达边缘的事件for (const Ant &ant : ants) {if (ant.v == 1) {tMin = min(tMin, L - ant.x);} else if (ant.v == -1) {tMin = min(tMin, ant.x);}}// 相邻蚂蚁碰撞的事件for (int i = 0; i + 1 < (int)ants.size(); ++i) {if (ants[i].v > ants[i + 1].v) {double dt = (ants[i + 1].x - ants[i].x) /(ants[i].v - ants[i + 1].v);tMin = min(tMin, dt);}}if (tMin > 1e50) {// 没有运动事件，说明所有蚂蚁都静止（实际上只剩 A 静止）cannotFall = true;break;}// 推进时间curTime += tMin;for (Ant &ant : ants) {ant.x += ant.v * tMin;}// 检查 A 是否已经到达边缘for (const Ant &ant : ants) {if (ant.isA) {if (ant.x <= EPS && ant.v == -1) {fallen = true;fallTime = curTime;break;}if (ant.x >= L - EPS && ant.v == 1) {fallen = true;fallTime = curTime;break;}}}if (fallen) break;// 移除已经掉落的蚂蚁vector<Ant> remain;bool aRemoved = false;for (const Ant &ant : ants) {if (ant.x <= EPS && ant.v == -1) {if (ant.isA) {aRemoved = true;fallTime = curTime;}continue;}if (ant.x >= L - EPS && ant.v == 1) {if (ant.isA) {aRemoved = true;fallTime = curTime;}continue;}remain.push_back(ant);}if (aRemoved) {fallen = true;break;}ants = move(remain);// 处理碰撞：找到所有位置相同的连续蚂蚁组，交换速度（反转速度序列）int sz = (int)ants.size();int i = 0;while (i < sz) {int j = i + 1;while (j < sz && fabs(ants[j].x - ants[i].x) < EPS) {++j;}if (j - i >= 2) {vector<int> vs;for (int k = i; k < j; ++k)vs.push_back(ants[k].v);reverse(vs.begin(), vs.end());for (int k = i; k < j; ++k)ants[k].v = vs[k - i];}i = j;}}if (cannotFall) {cout << "Cannot fall!\n";} else {// 最终时间一定是整数，四舍五入输出long long ans = (long long)llround(fallTime);cout << ans << '\n';}}return 0;}
我想回家
问题描述
某国正处于激烈的内战之中，该国的各个城市按照支持领导人的不同分属两个阵营。
作为一个商人，M先生并不关心政治，但他能够感受到目前事态的严峻。
你需要帮助他尽快回家。
出于安全的考虑，你所提供的回家线路中，最多只能包含一条连接两个不同阵营城市的道路。
请你计算，M先生回家所需花费的最短时间。
输入格式
输入包含多组测试数据。
每组数据第一行包含整数 N，表示该国家的城市数量。
第二行包含整数 M，表示该国家的道路数量。
接下来 M 行，每行包含三个整数 A,B,T，表示城市 A和城市 B之间存在一条道路，通过它的时间为 T。
最后一行包含 N个整数 1或 2，其中的第 i个整数是 1，则表示城市 i位于阵营 1，否则，表示城市 i位于阵营 2。
所有城市编号 1∼N。
为了简化问题，我们假设 M先生是从城市 1出发，目的地是城市 2，并且城市 1
一定位于阵营 1，城市 2一定位于阵营 2。
注意，所有道路都是双向的，且两个城市之间最多只有一条道路。输入 N=0时，表示输入结束。
输出格式
每组数据输出一行一个结果，表示最短时间。如果无法到达目的地，则输出 −1。
数据范围
每个输入最多包含 10组数据。
2≤N≤600,
0≤M≤10000,
1≤A,B≤N,
1≤T≤500
输入样例
2
1
1 2 100
1 2
3
3
1 2 100
1 3 40
2 3 50
1 2 1
5
5
3 1 200
5 3 150
2 5 160
4 3 170
4 2 170
1 2 2 2 1
0
输出样例
100
90
540
思考
这题的核心是：路径中最多只能经过一条“跨阵营边”。
因此可以把状态扩展成二维：
dist[i][0]：从城市 1 到城市 i，且还没有走过跨阵营边的最短时间；
dist[i][1]：从城市 1 到城市 i，且已经走过一条跨阵营边的最短时间。
然后做分层图最短路，用 Dijkstra。
建图规则：
同阵营道路：
第 0 层内部连边；
第 1 层内部也连边。
不同阵营道路：
只能作为唯一一次跨阵营道路使用；
从第 0 层跨到第 1 层，不能从第 1 层再跨。
起点是 (1, 0)，终点是 (2, 1)，答案就是 dist[2][1]。
如果不可达，输出 -1。
考察知识点概要：
最短路；
Dijkstra；
分层图 / 状态扩展；
将“最多经过一条特殊边”转化为 0/1 两种状态。
代码
#include<bits/stdc++.h>using namespace std;const int INF = 0x3f3f3f3f;struct Edge {int to, w;};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int N;while (cin >> N && N != 0) {int M;cin >> M;vector<tuple<int, int, int>> edges;edges.reserve(M);for (int i = 0; i < M; ++i) {int A, B, T;cin >> A >> B >> T;--A;--B;edges.emplace_back(A, B, T);}vector<int> camp(N);for (int i = 0; i < N; ++i) {cin >> camp[i];}// 分层图：0 ~ N-1 表示未跨阵营，N ~ 2N-1 表示已跨阵营vector<vector<Edge>> g(2 * N);auto addEdge = [&](int u, int v, int w) {g[u].push_back({v, w});};for (auto [u, v, w] : edges) {if (camp[u] == camp[v]) {// 同阵营边：两层内部都连addEdge(u, v, w);addEdge(v, u, w);addEdge(u + N, v + N, w);addEdge(v + N, u + N, w);} else {// 跨阵营边：只能从第 0 层跨到第 1 层addEdge(u, v + N, w);addEdge(v, u + N, w);}}int start = 0; // 城市 1，未跨阵营int target = N + 1; // 城市 2，已跨阵营vector<int> dist(2 * N, INF);priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;dist[start] = 0;pq.push({0, start});while (!pq.empty()) {auto [d, u] = pq.top();pq.pop();if (d != dist[u]) continue;for (auto &e : g[u]) {int v = e.to;int nd = d + e.w;if (nd < dist[v]) {dist[v] = nd;pq.push({nd, v});}}}if (dist[target] == INF) {cout << -1 << '\n';} else {cout << dist[target] << '\n';}}return 0;}
这是一棵树吗？
问题描述
树是一种众所周知的数据结构，它既可以是空的（null），也可以是一个节点或多个节点的集合，这些节点通过有向边连接且满足以下属性。
有且仅有一个节点，我们称之为根节点，没有任何有向边指向该节点。
除了根节点外，每个节点都有且仅有一条指向它的边。
从根节点到每个其他节点都有一条唯一的有向边序列。
例如，参考下图，节点用圆圈表示，有向边用带箭头的线表示，前两个图形是树，最后一个图形不是树。
给定若干个由有向边连接的节点集合的描述，请确定它们是否满足树的定义。
输入格式
输入包含多组测试数据。
每组数据占若干行，包含若干个对于有向边的描述，每个有向边的描述包含两个整数 a 和 b，表示这条有向边从节点 a指向节点 b。
当出现数对 0 0 时，表示这组数据的输入结束。
当出现数对 -1 -1 时，表示全部输入结束。
具体可参考样例。
输出格式
每个数据输出占一行，表示结果。
格式为 Case k is a tree. 或 Case k is not a tree.，其中 k
为组别编号，从 1开始。
数据范围
0<a,b<10000,
每个输入最多包含 100组数据。
输入样例
6 8 5 3 5 2 6 4
5 6 0 0
8 1 7 3 6 2 8 9 7 5
7 4 7 8 7 6 0 0
3 8 6 8 6 4
5 3 5 6 5 2 0 0
-1 -1
输出样例
Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.
思考
题目是经典的有向树判定（类似 HDU 1325 / POJ 1308）。
思路概要：
空树 0 0 是合法的树。
对于非空图，判断是否满足树的性质：
除根节点外，每个节点入度最多为 1；
不能有环；
最终有且仅有一个入度为 0 的节点（即唯一根节点）。
使用并查集检测环：如果当前边 a -> b 的起点和终点已经在同一集合中，则形成环。
使用入度数组检测“一个节点有多个父亲”的情况。
每组数据结束后，统计出现过的节点中入度为 0 的个数，必须恰好为 1。
代码
#include<bits/stdc++.h>using namespace std;const int MAXN = 10005;int parent[MAXN];intfind(int x){if (parent[x] != x)parent[x] = find(parent[x]);return parent[x];}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int a, b;int caseNo = 1;while (cin >> a >> b) {if (a == -1 && b == -1) break;for (int i = 0; i < MAXN; ++i) {parent[i] = i;}vector<int> indeg(MAXN, 0);vector<bool> vis(MAXN, false);vector<int> nodes;bool ok = true;while (!(a == 0 && b == 0)) {if (ok) {if (!vis[a]) {vis[a] = true;nodes.push_back(a);}if (!vis[b]) {vis[b] = true;nodes.push_back(b);}// 一个节点最多只能有一个父亲if (indeg[b] > 0) {ok = false;} else {int ra = find(a);int rb = find(b);// 已经在同一集合中，再加边会形成环if (ra == rb) {ok = false;} else {parent[rb] = ra;++indeg[b];}}}cin >> a >> b;}if (ok) {if (!nodes.empty()) {int rootCnt = 0;for (int x : nodes) {if (indeg[x] == 0) {++rootCnt;}}if (rootCnt != 1) {ok = false;}}// nodes 为空表示空树，空树也是树}cout << "Case " << caseNo++ << " is "<< (ok ? "a tree." : "not a tree.") << '\n';}return 0;}
假币
问题描述
“金条”银行从可靠来源获得的信息表明，在他们的最后一组 N
个硬币中，有一个是假币。
假币的重量和其他硬币不同（其他硬币都是真的，重量都相同）。
经济危机过后，他们只有一个天平可以使用。
使用这个天平可以确定左端放置的物品重量是否小于、等于或大于右端放置的物品重量。
为了测出假币，工作人员将这 N个硬币从 1
到 N编号，每个硬币都有一个唯一的编号。
然后他们开始进行若干组比较实验。
每组实验向左右两端放置同样数量的硬币，然后进行重量的比较。
每次实验的使用硬币编号和重量比较结果均被记录。
请你根据这些信息帮助银行工作人员确定假币的编号。
输入格式
第一行包含两个整数 N和 K，表示硬币数量以及实验次数。
接下来 2K行，每两行描述一组实验。
每组实验第一行首先包含整数 P，表示实验时两端各放入 P枚硬币，随后 P
个整数表示放入左端的硬币编号，再随后 P个整数表示放入右端的硬币编号。
第二行包含一个字符 < 或 > 或 =，用来描述重量比较结果：
< 表示左端硬币重量小于右端硬币重量。
> 表示左端硬币重量大于右端硬币重量。
= 表示左端硬币重量等于右端硬币重量。
输出格式
输出假币的编号，如果无法判断则输出 0。
数据范围
2≤N≤1000,
1≤K≤100,
1≤P≤N/2
输入样例
5 3
2 1 2 3 4
<
1 1 4
=
1 2 5
=
输出样例
3
思考
对每个硬币 i，分别假设：
硬币 i是假币且偏轻；
硬币 i是假币且偏重；
然后用所有实验去验证这个假设是否成立。只要有一种假设能解释全部实验，硬币
i就“可能是假币”。
最后统计所有“可能是假币”的硬币编号：
如果恰好只有一个编号，输出它；
否则输出 0。
验证一次实验的方法：
已知本次实验左盘和右盘的硬币编号，以及实际结果 <、>、=。
根据假设的假币类型和位置，推断本次实验“应该出现”的结果，再与实际结果比较。
假币偏轻：
假币在左盘，则应为 <；
假币在右盘，则应为 >;
假币不在两边，则应为 =。
假币偏重：
假币在左盘，则应为 >；
假币在右盘，则应为 <；
假币不在两边，则应为 =。
代码
#include<bits/stdc++.h>using namespace std;struct Experiment {vector<int> leftCoins;vector<int> rightCoins;char result;};// 检查假设 coin 是假币，且类型为 light 时，是否能解释所有实验boolcheck(int coin, bool light, const vector<Experiment>& exps){for (const auto& exp : exps) {bool inLeft = false;bool inRight = false;for (int x : exp.leftCoins) {if (x == coin) {inLeft = true;break;}}for (int x : exp.rightCoins) {if (x == coin) {inRight = true;break;}}char expected;if (!inLeft && !inRight) {expected = '=';} else if (inLeft) {// 假币在左盘expected = light ? '<' : '>';} else {// 假币在右盘expected = light ? '>' : '<';}if (expected != exp.result) {return false;}}return true;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int N, K;cin >> N >> K;vector<Experiment> exps(K);for (int i = 0; i < K; ++i) {int P;cin >> P;exps[i].leftCoins.resize(P);exps[i].rightCoins.resize(P);for (int j = 0; j < P; ++j) {cin >> exps[i].leftCoins[j];}for (int j = 0; j < P; ++j) {cin >> exps[i].rightCoins[j];}cin >> exps[i].result;}vector<int> possible;for (int coin = 1; coin <= N; ++coin) {// 假设假币偏轻if (check(coin, true, exps)) {possible.push_back(coin);continue;}// 假设假币偏重if (check(coin, false, exps)) {possible.push_back(coin);}}if (possible.size() == 1) {cout << possible[0] << '\n';} else {cout << 0 << '\n';}return 0;}