题解 | #信息学院2026天梯赛组队选拔赛#

L1-1无用之人成就无人能成之事

直接输出即可。

#include <bits/stdc++.h>

using namespace std;

void solve() {
    cout << "Sometimes it's the very people who no one imagines anything of who do the things no one can imagine." << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();

    return 0;
}

L1-2彩票

我们需要检查前三位数字之和是否等于后三位数字之和。这可以通过扫描输入字符串来实现，然后使用 if 语句和加法运算比较前三个字符的和与后三个字符的和。

#include <bits/stdc++.h>

using namespace std;

void solve() {
    string s;
    cin >> s;
    if(s[0]+s[1]+s[2] == s[3]+s[4]+s[5]) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();

    return 0;
}

L1-3火车票

本题是一个典型的多分支条件判断问题。根据题目描述的优惠规则，优先级如下：

年龄优先：年龄小于 $12$ 岁直接获得“儿童优惠”；年龄大于等于 $60$ 岁直接获得“老年优惠”。这两种情况无需考虑学生和购票状态。
年龄在 $12$ ~ $59$ 岁之间时，再根据是否学生、是否提前购票的组合判断：
- 既是学生又提前购票 → 学生提前优惠
- 是学生但未提前购票 → 学生优惠
- 不是学生但提前购票 → 提前优惠
- 其余情况（非学生且未提前购票） → 无优惠

注意输出格式：第一行为优惠类型的英文短语（注意大小写和空格），第二行为输入的年龄值。

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int a, s, e;
    cin >> a >> s >> e;
    if (a < 12) {
        cout << "Child Discount" << endl << a << endl;
    }
    else if (a >= 60) {
        cout << "Senior Discount" << endl << a << endl;
    }
    else {
        if (s && e) {
            cout << "Student Early Discount" << endl << a << endl;
        }
        else if (s && !e) {
            cout << "Student Discount" << endl << a << endl;
        }
        else if (!s && e) {
            cout << "Early Discount" << endl << a << endl;
        }
        else {
            cout << "No Discount" << endl << a << endl;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();

    return 0;
}

L1-4这是一个字符串题

由于数据范围较小，直接模拟即可满足要求。

操作1：查找并替换

调用 s.find(s1) 获取第一次出现的位置，若找到pos != npos，则用 s.replace(pos, s1size(), s2) 进行替换。

操作2：删除最长连续相同字符块

用l和r记录当前连续块的边界，tmp记录s[l...r]，若tmp的长度大于ms，把ms更新为tmp，最后使用find()和erase()函数即可完成删除。

操作3：翻转子串

使用 reverse(s.begin() + l - 1, s.begin() + r) 翻转闭区间 [l, r]。

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int len1, len2;
            string s1, s2;
            cin >> len1 >> s1 >> len2 >> s2;
            size_t pos = s.find(s1);
            if (pos != string::npos) {
                s.replace(pos, s1.size(), s2);
            }
        }
        else if (op == 2) {
            if (s.empty()) {
                continue;
            }
            int l = 0, r = 0;
            string ms;
            while (l < s.size()) {
                string tmp;
                while (r < s.size() && s[r] == s[l]) {
                    tmp += s[r];
                    r++;
                }
                if (tmp.size() > ms.size()) {
                    ms = tmp;
                }
                l = r;
            }
            s.erase(s.find(ms), ms.size());
        }
        else {
            int l, r;
            cin >> l >> r;
            reverse(s.begin() + l - 1, s.begin() + r);
        }
    }
    cout << s << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();

    return 0;
}

L1-5小明搬家

两人相遇时是否交接箱子不影响最终答案。

二分法求答案：

#include <bits/stdc++.h>

using namespace std;

void solve() {
    long long n, k, m;
    cin >> n >> k >> m;
    vector<long long> a(k), b(k);
    for (int i = 0; i < k; i++) {
        cin >> a[i] >> b[i];
    }
    function<bool(long long)> check = [&](long long mid) {
        long long cnt = 0;
        for (int i = 0; i < k; i++) {
            if (b[i] == 0) {
                cnt += (mid - (n - a[i])) / ((n - 1) * 2);
            }
            else {
                cnt += (mid + (n - a[i])) / ((n - 1) * 2);
            }
        }
        return cnt >= m;
    };
    long long l = 0, r = 1e18;
    while (l < r) {
        long long mid = l + r >> 1;
        if (check(mid)) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    cout << l << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();

    return 0;
}

L2-1二零二六

在这里，请注意 $(x,y)$ 对在 $x^{2}+y^{2}\leq N$ 范围内进行检查。这表明我们可以枚举 $(x,y)$ 而不设置固定的 $n$ 。也就是说，我们可以构建下面的算法：
    首先，假设 $c=(c_{1},c_{2},…,c_{N})$ 是一个充满零的数组。
    对于 $x=1,2,…$ ，当 $x^{2}≤N$ 时，执行以下操作：
        对于 $y=x+1,x+2,…$ , 当 $x^{2} + y^{2}≤N$ 时，执行以下操作：

            将 $c_{x^{2}+y^{2}}$ 增 1。

    最后，好的整数是 $c_{n}=1$ 的 $n$ ，因此枚举这样的 $n$ 。

时间复杂度为 $O(\sqrt{N}\times\sqrt{N})=O(N)$ 。

#include <bits/stdc++.h> using namespace std; void solve() {     int N;     cin >> N;     vector<int> c(N + 1);     for (int x = 1; x * x <= N; x++) {         for (int y = x + 1; x * x + y * y <= N; y++) {             c[x * x + y * y]++;         }     }     vector<int> ans;     for (int n = 1; n <= N; n++) {         if (c[n] == 1) ans.push_back(n);     }     cout << ans.size() << "\n";     for (int i = 0; i < (int)ans.size(); i++) {         cout << ans[i] << " \n"[i + 1 == (int)ans.size()];     } } int main() {     ios::sync_with_stdio(0);     cin.tie(0);     solve();     return 0; }

L2-2小杨放羊

可以使用滑动窗口技术解决问题。

当 $L$ 固定时

当 $L$ 固定时，我们来分析 $R$ 需要满足的条件。
如果 $(L,R)$ 不满足条件，那么必然存在 $i$ 和 $j$ ，使得 $L\leq i< j \leq R$ 且 $\left| c_{i} - c_{j} \right| < D$ 。由于这对 $(i,j)$ 的存在，任何 $(L,R+\alpha)$ （其中 $\alpha \geq 1$ ）都无法满足条件。

也就是说，存在一个 $f(L)$ ，使得 $(L,L),(L,L+1),…,(L,f(L))$ 满足条件，而 $(L,f(L)+1),…,(L,N)$ 不满足条件。

对所有 $L$ 求解 $f(L)$

当 $f(L)$ 已知时，我们来考虑如何求 $f(L+1)$ 。因为 $(L,f(L))$ 满足条件，那么 $(L+1,f(L))$ 也必然满足条件（因为约束对变少了）。因此 $f(L)\leq f(L+1)$ ，我们只需要从 $f(L)$ 开始 “继续推进” 来找到 $f(L+1)$ 。这样，我们就可以执行如下伪代码所示的滑动窗口算法：

ans = 0
R = 1
for L in 1..N:
  while (L, R) satisfies the condition:
    R <- R+1
  ans <- ans+(R-L)

快速解决判定问题
为了让这个算法高效运行，我们需要快速判定 $(L,R)$ 是否满足条件。
当 $(L,R−1)$ 满足条件时， $(L,R)$ 满足条件当且仅当对于所有 $L\leq i<R$ ，都有 $\left| c_{i} - c_{R} \right| \geq D$ 。这等价于：

$c_{L} ,..., c_{R - 1}$ 中的最小值 $\geq c_{R}+D$ ，或者

$c_{L} ,..., c_{R - 1}$ 中的最大值 $\leq c_{R}-D$ 。
因此，我们只需要一个支持以下操作的数据结构：
插入元素
删除元素
检索大于或等于 $x$ 的最小元素
检索小于或等于 $x$ 的最大元素
set可以在 $O(logN)$ 时间内支持这些操作，因此整个问题的时间复杂度为 $O(NlogN)$ 。

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, d;
    cin >> n >> d;
    vector<int> c(n);
    for (auto& x : c) {
        cin >> x;
    }
    long long ans = 0;
    set<long long> s({(long long)-1e9, (long long)2e9});
    int r = 0;
    for (int l = 0; l < n; l++) {
        while (r < n) {
            auto it = s.lower_bound(c[r]);
            if (*it - c[r] < d) {
                break;
            }
            it--;
            if (c[r] - *it < d) {
                break;
            }
            s.insert(c[r]);
            r++;
        }
        ans += r - l;
        s.erase(c[l]);
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();

    return 0;
}

L2-3放风筝

首先，第 $i$ 个人和第 $j$ 个人 $(i \ne j)$ 可以同时放风筝，当且仅当以下条件之一成立：

$A_{i}< A_{j}$ 且 $B_{i} < B_{j}$
$A_{i}> A_{j}$ 且 $B_{i} > B_{j}$

我们我们按照 $A_{i}$ 升序排序线段 $AB$ ， $A$ 的值相等的线段再按 $B$ 的值降序排列这些 $AB$ ，问题就转化为了求 $B_{1},B_{2},...,B_{N}$ 的最长递增子序列，下面分别给出动态规划求法和树状数组求法：

动态规划求法：

#include <bits/stdc++.h>

using namespace std;

struct p
{
    int a, b;
};

void solve() {
    int n;
    cin >> n;
    vector<p> c(n);
    for (int i = 0; i < n; i++) {
        cin >> c[i].a >> c[i].b;
    }
    sort(c.begin(), c.end(), [&](p x, p y) {
        if(x.a == y.a) return x.b > y.b;
        return x.a < y.a;
    });
    vector<int> dp;
    for (int i = 0; i < n; i++) {
        int idx = lower_bound(dp.begin(), dp.end(), c[i].b) - dp.begin();
        if (idx >= dp.size()) {
            dp.push_back(c[i].b);
        }
        else {
            dp[idx] = c[i].b;
        }
    }
    cout << dp.size() << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();

    return 0;
}

树状数组求法：

#include <bits/stdc++.h>

using namespace std;

struct p {
    int a, b;
};

vector<int> tr(200005, 0);

int lowbit(int x) {
    return x & -x;
}

int query(int x) {
    int res = 0;
    for(; x; x -= lowbit(x)) {
        res = max(res, tr[x]);
    }
    return res;
}

void change(int x, int k) {
    for(; x < 200005; x += lowbit(x)) {
        tr[x] = max(tr[x], k);
    }
}

void solve() {
    int n;
    cin >> n;
    vector<p> ab(n);
    for (int i = 0; i < n; i++) {
        cin >> ab[i].a >> ab[i].b;
    }
    sort(ab.begin(), ab.end(), [&](p x, p y) {
        if(x.a == y.a) return x.b > y.b;
        return x.a < y.a;
        });
    map<int, int> used;
    for (int i = 0; i < n; i++) {
        used[ab[i].b] = 1;
    }
    int now = 1;
    for (auto& [x, y] : used) {
        y = now++;
    }
    for (int i = 0; i < n; i++) {
        ab[i].b = used[ab[i].b];
    }
    for (auto [a, b] : ab) {
        change(b, query(b - 1) + 1);
    }
    cout << query(200000) << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();

    return 0;
}

L3-1走出迷宫

定义节点 $p$ 包含状态：坐标 $x$ 、坐标 $y$ 、剩余卷轴 $k$ 和行走距离 $d$ 。

用数三维组 $v$ 记录节点对应的 $x$ ， $y$ 和 $k$ 是否已访问

使用 $bfs$ 算法遍历图，当下一步遇到墙时，检查当前的节点是否有剩余卷轴，若有且该状态未被标记过， $k$ 减去 $1$ 并将其加入到队列中，最终即可求出能否到达终点和最短路径。

#include <bits/stdc++.h>

using namespace std;

struct p {
    int x, y, k, d;
};

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<vector<bool>>> v(n + 1, vector<vector<bool>>(m + 1, vector<bool>(k + 1, 0)));
    vector<vector<char>> g(n + 1, vector<char>(m + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
        }
    }
    queue<p> q;
    p st;
    st.x = 1, st.y = 1, st.k = k, st.d = 0;
    q.push(st);
    v[1][1][k] = 1;
    while (!q.empty()) {
        p now = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            p next;
            next.x = now.x + dx[i];
            next.y = now.y + dy[i];
            if (next.x < 1 || next.x > n || next.y < 1 || next.y > m) {
                continue;
            }
            if (g[next.x][next.y] == '#') {
                if (now.k > 0) {
                    next.k = now.k - 1;
                }
                else {
                    continue;
                }
            }
            else {
                next.k = now.k;
            }
            next.d = now.d + 1;
            if (v[next.x][next.y][next.k]) {
                continue;
            }
            q.push(next);
            v[next.x][next.y][next.k] = true;
            if (next.x == n && next.y == m) {
                cout << next.d << endl;
                return;
            }
        }
    }
    cout << -1 << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();

    return 0;
}

L3-2早餐

首先进行贪心，如果一个人要去其中某个食堂的话，那他一定会购买 $b$ 个包子和 $e$ 个鸡蛋。
可以计算出最少需要几人次进行购买，即 $max(\left[ \frac{n}{b} \right],\left[ \frac{m}{e} \right])$ 向上取整。
首先对于每个人，枚举每个食堂其是否前往，以及其前往顺序。
得到每个人买 $0$ ~ $3$ 次的最短路径长度。
然后就可以直接进行 $dp$ 。设 $f_{i, j}$ 表示考虑到第 $i$ 个人时，一共去了 $j$ 次食堂的最短路径。

时间复杂度 $O(kn)$ 。这里的 $n$ 指需要购买的数量。

#include <bits/stdc++.h>

using namespace std;

double dist(pair<int, int> a, pair<int, int> b) {
    return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}

void solve() {
    int n, m, k, b, e, c;
    cin >> n >> m >> k >> b >> e;
    c = max((n + b - 1) / b, (m + e - 1) / e);
    vector<pair<int, int>> a(4), s(k);
    for (auto& it : a) {
        cin >> it.first >> it.second;
    }
    for (auto& it : s) {
        cin >> it.first >> it.second;
    }
    vector<double> dp(c + 1, 1e9);
    dp[0] = 0;
    for (int i = 0;i < k; i++) {
        vector<double> f(4, 1e9);
        f[0] = 0;
        vector<int> vis(3, 0);
        function<void(pair<int, int>, int, double)> dfs = [&](pair<int, int> now, int cnt, double dis) {
            f[cnt] = min(f[cnt], dist(now, a[3]) + dis);
            for (int j = 0; j < 3; j++) {
                if(vis[j]) {
                    continue;
                }
                vis[j] = 1;
                dfs(a[j], cnt + 1, dist(now, a[j]) + dis);
                vis[j] = 0;
            }
        };
        dfs(s[i], 0, 0);
        for (int j = c; j > 0; j--) {
            for (int p = 1; p <= min(j, 3); p++) {
                dp[j] = min(dp[j - p] + f[p], dp[j]);
            }
        }
    }
    printf("%.10f\n", dp[c]);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();

    return 0;
}