2025 团体程序设计天梯赛 L1-L2 题解（C++）

L1-3 高温补贴

高温补贴是为保证炎夏季节高温条件下经济建设和企业生产经营活动的正常进行，保障企业职工在劳动生产过程中的安全和身体健康进行的补贴。国家规定，用人单位安排劳动者在高温天气下（日最高气温达到 35° 以上），露天工作，以及不能采取有效措施将工作场所温度降低到 33° 以下的，应当向劳动者支付高温补贴。 给定当日最高气温、以及某用人单位的工作条件，请你写个程序判断，该单位员工能否获得高温补贴。

输入格式：

输入在一行中给出 3 个整数，即当日最高气温 T、工作场所状态 S、工作场所温度 t。其中温度为 [-40,50] 区间内的整数；工作场所状态为 1 表示露天，0 表示室内。

输出格式：

根据输入情况，如果可以获得高温补贴，则在一行中输出 Bu Tie（补贴），第二行输出 T 的值；否则输出不补贴的原因：如果室内外温度都超标，仅仅是因为室内工作就不补贴，则输出 Shi Nei（室内），第二行输出 T 的值；如果在室外工作但天气不热、或工作场所温度不高，则输出 Bu Re（不热），第二行输出 t 的值；如果天气不热、或工作场所温度不高，且在室内工作，则输出 Shu Shi（舒适），第二行输出 t 的值。

输入样例 1：

36 1 33 

输出样例 1：

Bu Tie 36 

输入样例 2：

36 0 33 

输出样例 2：

Shi Nei 36 

输入样例 3：

36 1 27 

输出样例 3：

Bu Re 27 

输入样例 4：

36 0 24 

输出样例 4：

Shu Shi 24

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int T, S, t;
    cin >> T >> S >> t;
    if (S == 1) {
        if (T > 35 && t >= 33) cout << "Bu Tie" << endl << T;
        else cout << "Bu Re" << endl << t;
    } else {
        if (T > 35 && t >= 33) cout << "Shi Nei" << endl << T;
        else cout << "Shu Shi" << endl << t;
    }
}

L1-4 零头就抹了吧

输入格式：

输入在一行中给出一个正整数 N（≤10^9），为客人应该付的钱。

输出格式：

在一行中输出老板抹掉零头后应收的钱。

输入样例：

258 

输出样例：

256 

样例说明：

256 在二进制中是 100 000 000，被程序员认为是个很'整'的数。所有二进制中最高位是 1 后面全是 0 的数字都是程序员世界里的'整'数。256 是小于 258 的最大的'整'数，所以老板收取这个数。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    int x = 1;
    while ((x << 1) <= n) x <<= 1;
    cout << x << endl;
}

L1-5 这是字符串题

因为每年天梯赛字符串题的解答率都不尽如人意，因此出题组从几年前开始决定：每年的天梯赛的 15 分一定会有一道字符串题，另外一道则一定不是字符串题。

小特决定给字符串的美观程度进行评分，具体而言，小特认为每个字符都有一个分数，一个字符串的美观分就是将这些字符的分数加起来。例如 s 是 -3 分、t 是 5 分、r 是 1 分的话，那么 str 的美观分就是 -3+5+1=3 分。对于一个给定的字符串 S，请你帮小特统计每个字符出现的次数，以及最后整个字符串的美观分是多少。

输入格式:

输入第一行是一个只包含小写字母的字符串 S (1≤∣S∣≤1000)，表示需要进行美观程度评分的字符串。字符串只包含小写字母。 接下来的一行有 26 个数，第 i 个数表示按字母表顺序的第 i 个小写字母的分数是多少。数字范围的绝对值不超过 100。

输出格式:

输出第一行是 26 个非负整数，用空格隔开，第 i 个数表示按字母表顺序的第 i 个小写字母在字符串里出现了多少次。注意行末不要输出多余的空格。 输出第二行是一个整数，表示字符串的美观分。

输入样例:

nibuhuijuedezhegezhenshizifuchuantiba -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 13 12 11 10 9 8 7 6 5 4 3 2 1 

输出样例:

2 2 1 1 5 1 1 5 5 1 0 0 0 3 0 0 0 0 1 1 5 0 0 0 0 3 -59

参考代码

#include <bits/stdc++.h>
using namespace std;
int w[123];
int main() {
    map<char, int> h;
    string s;
    cin >> s;
    for (int i = 'a'; i <= 'z'; i++) cin >> w[i];
    int ans = 0;
    for (int i = 0; i < s.size(); i++) {
        h[s[i]]++;
        ans += w[s[i]];
    }
    for (int i = 'a'; i <= 'z'; i++) {
        cout << h[i];
        if (i != 'z') cout << " ";
        else cout << endl;
    }
    cout << ans;
}

L1-6 这不是字符串题

因为每年天梯赛字符串题的解答率都不尽如人意，因此出题组从几年前开始决定：每年的天梯赛的 15 分一定会有一道字符串题，另外一道则一定不是字符串题。

小特现在有 N 个正整数 Ai，她打算'动'一下这些数字。具体而言，她希望做 M 次操作，每次是以下三种操作之一：

1. 在当前正整数序列里查找给定的连续正整数序列是否存在，如存在，则将其替换成另外一个正整数序列；
2. 对于当前整个正整数序列，如果相邻之间的数字和为偶数，则在它们中间插入它们的平均数；
3. 翻转当前正整数序列指定下标之间的一段数字。这里的翻转指的是对于一段数字序列 Ai,Ai+1,…,Aj−1,Aj，将其变为 Aj,Aj−1,…,Ai+1,Ai。

请你输出按输入顺序依次完成若干次操作后的结果。

输入格式:

输入第一行是两个正整数 N,M (1≤N,M≤10^3)，分别表示正整数个数以及操作次数。 接下来的一行有 N 个用一个空格隔开的正整数 Ai (1≤Ai≤26)，表示需要进行操作的原始数字序列。 紧接着有 M 部分，每一部分表示一次操作，你需要按照输入顺序依次执行这些操作。记 L 为当前操作序列长度（注意原始序列在经过数次操作后，其长度可能不再是 N）。每部分的格式与约定如下：

• 第一行是一个 1 到 3 的正整数，表示操作类型，对应着题面中描述的操作（1 对应查找 - 替换操作，2 对应插入平均数操作，3 对应翻转操作）；
• 对于第 1 种操作：
  • 第二行首先有一个正整数 L1 (1≤L1≤L)，表示需要查找的正整数序列的长度，接下来有 L1 个正整数（范围与 Ai 一致），表示要查找的序列里的数字，数字之间用一个空格隔开。查找时序列是连续的，不能拆分。
  • 第三行跟第二行格式一致，给出需要替换的序列长度 L2 和对应的正整数序列。如果原序列中有多个可替换的正整数序列，只替换第一个数开始序号最小的一段，且一次操作只替换一次。注意 L2 范围可能远超出 L。
  • 如果没有符合要求的可替换序列，则直接不进行任何操作。
• 对于第 2 种操作：
  • 没有后续输入，直接按照题面要求对整个序列进行操作。
• 对于第 3 种操作：
  • 第二行是两个正整数 l,r (1≤l≤r≤L)，表示需要翻转的连续一段的左端点和右端点下标（闭区间）。

每次操作结束后的序列为下一次操作的起始序列。

保证操作过程中所有数字序列长度不超过 100N。题目中的所有下标均从 1 开始。

输出格式:

输出进行完全部操作后的最终正整数数列，数之间用一个空格隔开，注意最后不要输出多余空格。

输入样例:

39 5 14 9 2 21 8 21 9 10 21 5 4 5 26 8 5 26 8 5 14 4 5 2 21 19 8 9 26 9 6 21 3 8 21 1 14 20 9 2 1 1 3 26 8 5 2 14 1 3 37 38 1 11 26 9 6 21 3 8 21 1 14 20 9 14 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 3 2 40 

输出样例:

14 9 8 7 6 5 4 3 2 1 5 9 8 19 20 21 2 5 4 9 14 5 8 17 26 1 14 5 4 5 13 21 10 9 15 21 8 21 2 9 10 11 12 13 14 1 2 

样例解释:

为方便大家理解题意和调试程序，以下为样例每一步的中间操作序列结果： 第 1 次操作结束后：

14 9 2 21 8 21 9 10 21 5 4 5 14 1 26 8 5 14 4 5 2 21 19 8 9 26 9 6 21 3 8 21 1 14 20 9 2 1 

注意这里只会替换第一次的序列。 第 2 次操作结束后：

14 9 2 21 8 21 9 10 21 5 4 5 14 1 26 8 5 14 4 5 2 21 19 8 9 26 9 6 21 3 8 21 1 14 20 9 1 2 

第 3 次操作结束后：

14 9 2 21 8 21 9 10 21 5 4 5 14 1 26 8 5 14 4 5 2 21 19 8 9 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 2 

第 4 次操作结束后：

14 9 2 21 8 21 15 9 10 21 13 5 4 5 14 1 26 17 8 5 14 9 4 5 2 21 20 19 8 9 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 2

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    string s;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s += char(x + 'A' - 1);
    }
    while (m--) {
        int x;
        cin >> x;
        if (x == 1) {
            int l1;
            cin >> l1;
            string s1;
            for (int i = 0; i < l1; i++) {
                int x;
                cin >> x;
                s1 += char(x + 'A' - 1);
            }
            int k = s.find(s1);
            int l2;
            cin >> l2;
            string s2;
            for (int i = 0; i < l2; i++) {
                int x;
                cin >> x;
                s2 += char(x + 'A' - 1);
            }
            if (k != -1) {
                s.erase(k, l1);
                s.insert(k, s2);
            }
        } else if (x == 2) {
            for (int i = 1; i < s.size(); i++) {
                int o = s[i] + s[i - 1];
                if (o % 2 == 0) {
                    string s3;
                    s3 += char(o / 2);
                    s.insert(i, s3);
                    i++;
                }
            }
        } else {
            int l, r;
            cin >> l >> r;
            reverse(s.begin() + l - 1, s.begin() + r);
        }
    }
    for (int i = 0; i < s.size(); i++) {
        if (i != 0) cout << " ";
        cout << s[i] - 'A' + 1;
    }
    cout << endl;
}

L1-7 大幂数

如果一个正整数可以表示为从 1 开始的连续自然数的非 0 幂次和，就称之为'大幂数'。例如 2025 就是一个大幂数，因为 2025=1^3+2^3+3^3+4^3+5^3+6^3+7^3+8^3+9^3。本题就请你判断一个给定的数字 n 是否大幂数，如果是，就输出其幂次和。 另一方面，大幂数的幂次和表示可能是不唯一的，例如 91 可以表示为 91=1^1+2^1+3^1+4^1+5^1+6^1+7^1+8^1+9^1+10^1+11^1+12^1+13^1，同时也可以表示为 91=1^2+2^2+3^2+4^2+5^2+6^2，这时你只需要输出幂次最大的那个和即可。

输入格式：

输入在一行中给出一个正整数 n（2<n<2^31）。

输出格式：

如果 n 是大幂数，则在一行中输出幂次最大的那个和，格式为：

1^k+2^k+...+m^k 

其中 k 是所有幂次和中最大的幂次。如果解不存在，则在一行中输出 Impossible for n.，其中 n 是输入的 n 的值。

输入样例 1：

91 

输出样例 1：

1^2+2^2+3^2+4^2+5^2+6^2 

输入样例 2：

2147483647 

输出样例 2：

Impossible for 2147483647. 

参考代码

#include <bits/stdc++.h>
using namespace std;
int a[100100];
long long n, t, s, w;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        s += i;
        if (s >= n) {
            t = i;
            break;
        }
    }
    for (int i = 1; i <= t; i++) a[i] = i;
    for (int i = 31; i >= 1; i--) {
        w = 0;
        for (int j = 1; j <= t; j++) {
            w += pow(a[j], i);
            if (w == n) {
                for (int k = 1; k <= j; k++) {
                    cout << k << "^" << i;
                    if (k != j) cout << "+";
                    else cout << endl;
                }
                return 0;
            } else if (w > n) break;
        }
    }
    cout << "Impossible for " << n << "." << endl;
}

L1-8 现代战争

在最新的《命运召唤：现代战争》中，你要扮演 B 国的一名战斗机飞行员，前往轰炸 A 国的高价值建筑。A 国的建筑群可视为一个由 n×m 个小方格组成的地图，每个小方格中有一幢建筑，并且你已经知道了所有建筑的价值。 作为一名优秀的战斗机飞行员，你打算轰炸 k 幢建筑，轰炸方式是：你选择当前所有还存在的建筑里最高价值的一幢投下炸弹，这个炸弹会将这个建筑所在的一整行和一整列都炸平。。随后系统将彻底抹除被炸平的建筑，将剩下的地块合并成 (n−1)×(m−1) 的地图。

例如对原始地图

1 2 3 7 9 8 6 5 4 

进行一次轰炸后，更新后的地图为：

1 3 6 4 

请你编写程序，输出你轰炸了 k 幢建筑后的地图。

注：游戏纯属虚构，如有雷同纯属巧合

输入格式：

输入第一行给出三个正整数 n、m（2≤n,m≤1000）和 k（<min{n,m}），依次对应地图中建筑的行数、列数，以及轰炸步数。随后 n 行，每行 m 个整数，为地图中对应建筑的价值。 题目保证所有元素在 [-2^30,2^30] 区间内，且互不相等。同行数字间以空格分隔。

输出格式：

输出轰炸 k 幢建筑后的地图。同行数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

4 5 2 3 8 6 1 10 28 9 21 37 5 4 11 7 25 18 15 23 2 17 14 

输出样例：

3 6 10 4 7 18 

参考代码

#include <bits/stdc++.h>
using namespace std;
int x[1010], y[1010];
int a[1010][1010];
priority_queue<array<int, 3>> p;
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            p.push({a[i][j], i, j});
        }
    while (k--) {
        auto q = p.top();
        while (x[q[1]] || y[q[2]]) {
            p.pop();
            q = p.top();
        }
        x[q[1]] = y[q[2]] = 1;
    }
    for (int i = 1; i <= n; i++) {
        if (x[i]) continue;
        int o = 0;
        for (int j = 1; j <= m; j++) {
            if (y[j]) continue;
            if (o == 0) {
                cout << a[i][j];
                o = 1;
            } else cout << " " << a[i][j];
        }
        cout << endl;
    }
}

L2-1 算式拆分

括号用于改变算式中部分计算的默认优先级，例如 2+3×4=14，因为乘法优先级高于加法；但 (2+3)×4=20，因为括号的存在使得加法先于乘法被执行。本题请你将带括号的算式进行拆解，按执行顺序列出各种操作。

注意：题目只考虑 +、-、*、/ 四种操作，且输入保证每个操作及其对应的两个操作对象都被一对圆括号 () 括住，即算式的通用格式为 (对象 操作 对象)，其中 对象 可以是数字，也可以是另一个算式。

输入格式：

输入在一行中按题面要求给出带括号的算式，由数字、操作符和圆括号组成。算式内无空格，长度不超过 100 个字符，以回车结束。题目保证给出的算式非空，且是正确可计算的。

输出格式：

按执行顺序列出每一对括号内的操作，每步操作占一行。 注意前面步骤中获得的结果不必输出。例如在样例中，计算了 2+3 以后，下一步应该计算 5*4，但 5 是前一步的结果，不必输出，所以第二行只输出 *4 即可。

输入样例：

(((2+3)*4)-(5/(6*7))) 

输出样例：

2+3 *4 6*7 5/ -

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    stack<char> h;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == ')') {
            int j = i - 1;
            while (s[j] != '(') {
                h.push(s[j]);
                j--;
            }
            s.erase(j, i - j + 1);
            while (!h.empty()) {
                cout << h.top();
                h.pop();
            }
            i = j - 1;
            cout << endl;
        }
    }
}

L2-2 三点共线

给定平面上 n 个点的坐标 (xi,yi)（i=1,⋯,n），其中 y 坐标只能是 0、1 或 2，是否存在三个不同的点位于一条非水平的直线上？ 本题就请你找出所有共线的解。

输入格式：

输入首先在第一行给出正整数 n（3≤n≤5×10^4），为所有点的个数。 随后 n 行，每行给出一个点的坐标：第一个数为 x 轴坐标，第二个数为 y 轴坐标。其中，x 坐标是绝对值不超过 10^6 的整数，y 坐标在 { 0，1，2 } 这三个数字中取值。同行数字间以空格分隔。

输出格式：

如果无解，则在一行中输出 -1。 如果有解，每一行输出共线的三个点坐标。每个点的坐标格式为 [x, y]，点之间用 1 个空格分隔，按照 y = 0、1、2 的顺序输出。 如果有多解，首先按照 y = 1 的 x 坐标升序输出；还有相同则按照 y = 0 的 x 坐标升序输出。 注意不能输出重复的解（即不能有两行输出是一样的内容）。题目保证任何一组测试的输出均不超过 10^5 组不同的解。

输入样例：

17 90 0 60 2 1 1 0 0 50 0 -30 2 79 2 50 0 -20 1 75 1 -10 1 -20 1 1 1 100 2 22 0 -10 0 -1 2 

输出样例：

[-10, 0] [-20, 1] [-30, 2] [50, 0] [75, 1] [100, 2] [90, 0] [75, 1] [60, 2] 

输入样例：

20 -1 2 1 1 -13 0 63 1 -29 1 17 2 -1 2 0 0 -22 0 53 2 1 1 97 1 -10 0 0 0 1 0 -11 1 -37 2 26 1 -18 2 69 0 

输出样例：

-1

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int f[2 * N + 10];
int main() {
    int n;
    cin >> n;
    vector<vector<int>> g(2);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        if (y == 2) f[x + N] = 1;
        else g[y].push_back(x);
    }
    for (int i = 0; i < 2; i++) {
        sort(g[i].begin(), g[i].end());
        g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());
    }
    bool ok = 0;
    for (int i = 0; i < g[1].size(); i++) {
        for (int j = 0; j < g[0].size(); j++) {
            int x = g[1][i] - g[0][j] + g[1][i];
            if (abs(x) <= N && f[x + N]) {
                if (ok != 0) cout << endl;
                else ok = 1;
                cout << "[" << g[0][j] << ", 0] [" << g[1][i] << ", 1] [" << x << ", 2]";
            }
        }
    }
    if (ok == 0) cout << "-1" << endl;
}

L2-3 胖达的山头

胖达是大熊猫的昵称。上图是著名的'西直门三太子'萌兰的一字马。 一只成年大熊猫需要有自己独立的生活区域，如果两只成年大熊猫在同一时间进入同一片区域，很可能会发生打斗事件。 大熊猫保护中心计划将保护区划分成若干座山头，让胖达们都过上没有冲突的安逸生活。当然如果为每位胖达分配一个山头是最理想的，但中心计划安置数十万只胖达 —— 这是个长远计划（截至 2024 年，世界上共有近 1900 只大熊猫），而保护区面积有限，这样做会使得每个山头面积过于局促。于是中心负责人找到了你，带着所有胖达的活跃时间表，请你帮助他们计算一下，如果让所有活跃时间段内的胖达都位于不同的山头，最少需要建设多少个山头？

输入格式：

输入在第一行给出正整数 n（≤10^5），为胖达数量。随后 n 行，每行给出一位胖达的活跃时间段（闭区间），格式为：

start finish 

其中 start 为胖达活跃的起始时间点，finish 为终止时间点。两个时间点均以 hh:mm:ss 的格式给出（hh 表示小时、mm 表示分钟、ss 表示秒，从 00:00:00 到 23:59:59，并且保证 start 早于 finish。

输出格式：

在一行中输出保护中心最少需要建设的山头的数量。注意：要求是任何一个山头任何时间点都不能存在超过一只处于活跃时间段的大熊猫。

输入样例：

4 16:30:00 23:00:00 04:50:00 11:25:59 11:25:59 22:00:00 11:26:00 15:45:23 

输出样例：

2 

样例解释：

第 3 位胖达独占一座山头，其他胖达们可以共享一座山头。

参考代码

#include <bits/stdc++.h>
using namespace std;
int a[86500];
int main() {
    int n;
    cin >> n;
    while (n--) {
        int h1, m1, s1, h2, m2, s2;
        scanf("%d:%d:%d %d:%d:%d", &h1, &m1, &s1, &h2, &m2, &s2);
        int k1, k2;
        k1 = h1 * 3600 + m1 * 60 + s1;
        k2 = h2 * 3600 + m2 * 60 + s2;
        a[k1]++;
        a[k2 + 1]--;
    }
    int ans = 0;
    for (int i = 0; i <= 86400; i++) {
        a[i] += a[i - 1];
        ans = max(a[i], ans);
    }
    cout << ans << endl;
}

L2-4 被 n 整除的 n 位数

'被 n 整除的 n 位数'是这样定义的：记这个 n 位数为 an⋯a2a1。首先 an 不为 0。从 an 开始从左到右扫描每一位数字，前 1 位数（即 an）能被 1 整除，前 2 位数 anan−1 能被 2 整除，以此类推…… 即前 i 位数能被 i 整除（i=1,⋯,n）。 例如 34285 这个 5 位数，其前 1 位数 3 能被 1 整除；前 2 位数 34 能被 2 整除；前 3 位数 342 能被 3 整除；前 4 位数 3428 能被 4 整除；前 5 位数 34285 能被 5 整除。所以 34285 是能被 5 整除的 5 位数。 本题就请你对任一给定的 n，求出给定区间内被 n 整除的 n 位数。

友情提示：被偶数整除的数字一定以偶数结尾；被 5 整除的数字一定以 5 或 0 结尾；被 10 整除的数字一定以 0 结尾。

输入格式：

输入在一行中给出 3 个正整数：n（1<n≤15），以及闭区间端点 a 和 b（1≤a≤b<10^15）。

输出格式：

按递增序输出区间 [a,b] 内被 n 整除的 n 位数，每个数字占一行。 若给定区间内没有解，则输出 No Solution。

输入样例 1：

5 34200 34500 

输出样例 1：

34200 34205 34240 34245 34280 34285 

输入样例 2：

4 1040 1050 

输出样例 2：

No Solution

参考代码

#include <bits/stdc++.h>
using namespace std;
long long n, l, r;
bool flag = 1;
void dfs(long long x, int d) {
    if (d == n + 1) {
        if (x <= r && x >= l) {
            flag = 0;
            cout << x << endl;
        }
        return;
    }
    for (int i = 0; i <= 9; i++) {
        if (d == 1 && i == 0) continue;
        long long t = x * 10 + i;
        if (t % d == 0) dfs(t, d + 1);
    }
}
int main() {
    cin >> n >> l >> r;
    dfs(0, 1);
    if (flag) cout << "No Solution" << endl;
}