2025年天梯题解（L1-8 + L2）

L1-112 当代战争

题目
既然是从大到小轰炸，将全部点存储为三元组（value, x, y）。
排序之后, 记载行列被轰炸的编号，进行 k 次挑选即可。

1. #include <bits/stdc++.h>
2. using namespace std;
4. constexpr int MAXN = 1000;
5. struct Node { int val, r, c; };
6. static Node v[MAXN*MAXN + 5];
7. static int  mat[MAXN+5][MAXN+5];
8. static bool row_boom[MAXN+5], col_boom[MAXN+5];
10. int main(){
11.     ios::sync_with_stdio(false);
12.     cin.tie(nullptr);
14.     int n, m, k;
15.     cin >> n >> m >> k;
17.     // 1) 读入矩阵，扁平化到 v[]
18.     int tot = 0;
19.     for(int i = 1; i <= n; i++){
20.         for(int j = 1; j <= m; j++){
21.             cin >> mat[i][j];
22.             v[tot++] = { mat[i][j], i, j };
23.         }
24.     }
26.     // 2) 按值从大到小排序
27.     sort(v, v + tot, [](auto &A, auto &B){
28.         return A.val > B.val;
29.     });
31.     // 3) 选 k 个“炸弹”行列
32.     int cnt = 0;
33.     for(int i = 0; i < tot && cnt < k; i++){
34.         int rr = v[i].r, cc = v[i].c;
35.         if(!row_boom[rr] && !col_boom[cc]){
36.             row_boom[rr] = true;
37.             col_boom[cc] = true;
38.             cnt++;
39.         }
40.     }
42.     // 4) 输出剩余元素
43.     for(int i = 1; i <= n; i++){
44.         if(row_boom[i]) continue;
45.         bool first = true;
46.         for(int j = 1; j <= m; j++){
47.             if(col_boom[j]) continue;
48.             if(!first) cout << ' ';
49.             cout << mat[i][j];
50.             first = false;
51.         }
52.         if(!first) cout << '\n';
53.     }
54.     return 0;
55. }

复制代码

L2-051 满树的遍历

题目
先将输入的全括号算式分析成一棵二叉树，然后做后序遍历——即先处理左子树、再处理右子树、末了输出当前节点的利用。输出时，假如左右子节点是叶子数字，就打印该数字；否则不打印。这样完全符合题目要“只输出数字+利用符”的格式要求。

1. #include <bits/stdc++.h>
2. using namespace std;
4. struct Node {
5.     // 如果 isLeaf，则 val 存数字字符串；否则存操作符 op，以及左右子节点指针
6.     bool isLeaf;
7.     string val;
8.     char op;
9.     Node *l, *r;
10.     Node(string v): isLeaf(true), val(move(v)), op(), l(nullptr), r(nullptr) {}
11.     Node(char c, Node* L, Node* R): isLeaf(false), val(), op(c), l(L), r(R) {}
12. };
14. string s;
15. int pos;
17. // 解析函数：根据语法 expr = '(' expr op expr ')' | number
18. Node* parse() {
19.     if (s[pos] == '(') {
20.         ++pos; // skip '('
21.         Node* L = parse();
22.         char oper = s[pos++];
23.         Node* R = parse();
24.         ++pos; // skip ')'
25.         return new Node(oper, L, R);
26.     } else {
27.         // 读数字
28.         int start = pos;
29.         while (pos < (int)s.size() && isdigit(s[pos])) ++pos;
30.         return new Node(s.substr(start, pos - start));
31.     }
32. }
34. // 后序遍历，按题目要求输出每一步
35. void dfs(Node* cur) {
36.     if (cur->isLeaf) return;
37.     dfs(cur->l);
38.     dfs(cur->r);
39.     // 下面输出：如果左是叶子，先打印数字；然后打印操作符；如果右是叶子，再打印数字
40.     if (cur->l->isLeaf) cout << cur->l->val;
41.     cout << cur->op;
42.     if (cur->r->isLeaf) cout << cur->r->val;
43.     cout << "\n";
44. }
46. int main(){
47.     ios::sync_with_stdio(false);
48.     cin.tie(nullptr);
50.     // 读入整行
51.     if (!getline(cin, s)) return 0;
52.     pos = 0;
53.     Node* root = parse();
54.     dfs(root);
55.     return 0;
56. }

复制代码

L2-054 三点共线

题目
可以使用 bitset 优化枚举过这道题。
功能bitsetunordered_set<int>插入/查询速率O(1) （硬件位利用）O(1) 均派（有哈希冲突）空间占用1 bit/值（非常省）至少 8 字节/值 + 哈希桶是否能负数索引❌ 必要 偏移量映射✅ 不限定值域

• bitset 的根本用法
  

1. #include <bitset>
3. bitset<10> b;      // 创建一个包含10位的bitset，默认全是0
4. b[3] = 1;          // 将第4位设为1（下标从0开始）
5. b.set(5);          // 将第6位设为1
6. b.reset(3);        // 将第4位设为0
7. b.flip();          // 所有位取反
8. bool x = b.test(5); // 判断第6位是否为1（返回true/false）
9. int cnt = b.count(); // 返回有多少位是1

复制代码

• Code
  

1. #include <bits/stdc++.h>
2. using namespace std;
4. const int D = 1e6;  // 坐标偏移量
5. bitset<2000010> pos; // 存储y=2的点
7. int main() {
8.     ios::sync_with_stdio(false);
9.     cin.tie(nullptr);
10.    
11.     vector<vector<int>> layers(2);  // layers[0]:y=0, layers[1]:y=1
12.     int n, xpmclzjkln = 0;  // 题目要求的中间变量
13.    
14.     cin >> n;
15.     for (int i = 0; i < n; ++i) {
16.         int x, y;
17.         cin >> x >> y;
18.         if (y == 2) {
19.             pos.set(x + D);  // 坐标偏移防止负数
20.         } else {
21.             layers[y].push_back(x);
22.         }
23.     }
25.     // 去重排序
26.     for (auto& layer : layers) {
27.         sort(layer.begin(), layer.end());
28.         layer.erase(unique(layer.begin(), layer.end()), layer.end());
29.     }
31.     vector<pair<int, int>> ans;
32.     for (int x0 : layers[0]) {
33.         for (int x1 : layers[1]) {
34.             int x2 = 2 * x1 - x0;
35.             if(x2 < -1E6 || x2 > 1E6) continue;
36.             if (pos.test(x2 + D)) {
37.                 ans.emplace_back(x0, x1);
38.             }
39.         }
40.     }
42.     // 按要求排序
43.     sort(ans.begin(), ans.end(), [](auto& a, auto& b) {
44.         return tie(a.second, a.first) < tie(b.second, b.first);
45.     });
47.     // 输出结果
48.     if (ans.empty()) {
49.         cout << -1;
50.     } else {
51.         for (auto& [x0, x1] : ans) {
52.             printf("[%d, 0] [%d, 1] [%d, 2]\n",
53.                   x0, x1, 2*x1 - x0);
54.         }
55.     }
56.     return 0;
57. }

复制代码

L2-055 胖达的山头

差分取 max

1. #include <bits/stdc++.h>
2. using namespace std;
3. using ll = long long;
5. int parse_time(const string &s) {
6.     // "hh:mm:ss" -> 秒数
7.     int hh = stoi(s.substr(0,2));
8.     int mm = stoi(s.substr(3,2));
9.     int ss = stoi(s.substr(6,2));
10.     return hh*3600 + mm*60 + ss;
11. }
13. int main(){
14.     ios::sync_with_stdio(false);
15.     cin.tie(nullptr);
17.     int n;
18.     cin >> n;
19.     vector<pair<int,int>> events;
20.     events.reserve(2*n);
22.     string s_start, s_end;
23.     for(int i = 0; i < n; i++){
24.         cin >> s_start >> s_end;
25.         int st = parse_time(s_start);
26.         int ed = parse_time(s_end);
27.         // [st, ed] 包含端点，故在 ed+1 时做 −1
28.         events.emplace_back(st, +1);
29.         events.emplace_back(ed+1, -1);
30.     }
32.     // 按时间排序
33.     sort(events.begin(), events.end(),
34.          [](auto &a, auto &b){
35.              if(a.first != b.first)
36.                  return a.first < b.first;
37.              return a.second < b.second; // +1 也可以先后都累加
38.          });
40.     int cur = 0, ans = 0;
41.     for(auto &e : events){
42.         cur += e.second;
43.         ans = max(ans, cur);
44.     }
46.     cout << ans << "\n";
47.     return 0;
48. }

复制代码

L2-056 被n整除的n位数

题目

• DFS 构造每一位
  

• 用 dfs(pos, prefix) 表现我们已经确定了前 pos-1 位，当前前缀值为 prefix（十进制整数）。
  
• 若 pos > n，阐明前 n 位都已满足条件，检查这个 prefix 是否在区间 [a, b] 内，假如则生存。
  

• 剪枝条件
  

• 对于第 pos 位（1-based，下同），我们尝试的数字 d 必须使得：
  

                                         (                            p                            r                            e                            f                            i                            x                            ×                            10                            +                            d                            )                                                    m                                  o                                  d                                                  p                            o                            s                            =                            0.                                  (prefix \times 10 + d) \bmod pos = 0.                     (prefix×10+d)modpos=0.

• 别的，第 1 位 pos=1 只能枚举 1..9（最高位不能为 0）；后续可枚举 0..9，但按照提示：若 pos=n，即剩下末了一位，还要满足「能被 n 整除」，同样由上式天然保证。
  

• 数值范围
  

• n <= 14 时，深度 DFS 的分支被整除条件严酷限定，一般仅产生几十到几百个候选，远小于暴力                                         1                                       0                               n                                            10^n                     10n。
  
• 用 long long 存前缀、比力区间，安全无溢出。
  

1. #include <bits/stdc++.h>
2. using namespace std;
3. using ll = long long;
5. int n;
6. ll A, B;
7. vector<ll> answer;
9. // DFS 生成
10. void dfs(int pos, ll prefix) {
11.     if (pos > n) {
12.         // 构造了 n 位数，检查区间
13.         if (prefix >= A && prefix <= B) {
14.             answer.push_back(prefix);
15.         }
16.         return;
17.     }
18.     int start = (pos == 1 ? 1 : 0);
19.     for (int d = start; d <= 9; d++) {
20.         ll nxt = prefix * 10 + d;
21.         // 前 pos 位能被 pos 整除
22.         if (nxt % pos == 0) {
23.             dfs(pos + 1, nxt);
24.         }
25.     }
26. }
28. int main(){
29.     ios::sync_with_stdio(false);
30.     cin.tie(nullptr);
32.     cin >> n >> A >> B;
33.     answer.clear();
35.     // n 位数的最小与最大
36.     ll low = 1;
37.     for (int i = 1; i < n; i++) low *= 10;
38.     ll high = low * 10 - 1;
39.     // 如果 [A,B] 与 n 位数区间无交集，直接无解
40.     if (B < low || A > high) {
41.         cout << "No Solution\n";
42.         return 0;
43.     }
44.     // 交集后再 DFS，会节省一点无谓判断
45.     A = max(A, low);
46.     B = min(B, high);
48.     dfs(1, 0LL);
50.     if (answer.empty()) {
51.         cout << "No Solution\n";
52.     } else {
53.         sort(answer.begin(), answer.end());
54.         for (ll x : answer) {
55.             cout << x << "\n";
56.         }
57.     }
58.     return 0;
59. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。