2025 团体程序设计天梯赛（无 10、15）

1 / L1-1

#include <bits/stdc++.h>
using namespace std;

int main() {
    cout << "Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live.";
    return 0;
}

2 / L1-2

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    cout << a + b + c << endl;
    return 0;
}

3 / L1-3

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if (b && a >= 35 && c >= 33) {
        cout << "Bu Tie" << endl << a;
    } else if (!b && a >= 35 && c >= 33) {
        cout << "Shi Nei" << endl << a;
    } else if (b) {
        cout << "Bu Re" << endl << c;
    } else {
        cout << "Shu Shi" << endl << c;
    }
    return 0;
}

4 / L1-4

#include <bits/stdc++.h>
using namespace std;

int main() {
    int x;
    cin >> x;
    cout << (1 << __lg(x)) << endl;
    return 0;
}

5 / L1-5

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    string s;
    cin >> s;

    ll sum = 0;
    for (int i = 0; i < 26; i++) {
        int cnt = count(s.begin(), s.end(), 'a' + i);
        cout << cnt << " \n"[i == 25];
        int x;
        cin >> x;
        sum += x * cnt;
    }
    cout << sum << endl;

    return 0;
}

6 / L1-6

样例的数字按 A1Z26 翻译成字母其实是拼音，在嘲讽「你不会真以为这不是字符串题吧？」

其实多数字符串算法也不局限于字符串，比如后缀数组、马拉车这些，复杂度与字符集大小$\Sigma$ 无关，就可以推广。有些不行是因为要求字符集较小，如字典树空间是$\operatorname{O}(n\Sigma)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

string read(int n) {
    string s;
    while (n--) {
        int x;
        cin >> x;
        s += x + 'a' - 1;
    }
    return s;
}

int main() {
    int n, m;
    cin >> n >> m;

    string s = read(n);

    while (m--) {
        int op;
        cin >> op;

        if (op == 1) {
            int n;
            cin >> n;
            string x = read(n);
            cin >> n;
            string y = read(n);
            if (s.find(x) != -1) {
                int i = s.find(x);
                s = s.substr(0, i) + y + s.substr(i + x.size());
            }
        } else if (op == 2) {
            string t;
            t += s[0];
            for (int i = 1; i < s.size(); i++) {
                if ((s[i] - 'a') + (s[i - 1] - 'a') & 1 ^ 1) {
                    t += s[i] + s[i - 1] >> 1;
                }
                t += s[i];
            }
            s = t;
        } else {
            int l, r;
            cin >> l >> r;
            l--;
            string t = s.substr(l, r - l);
            s = s.substr(0, l) + string(t.rbegin(), t.rend()) + s.substr(r);
        }
    }

    for (int i = 0; i < s.size(); i++) {
        cout << s[i] - 'a' + 1 << " \n"[i == s.size() - 1];
    }

    return 0;
}

7 / L1-7

指数$k$ 不会超过 32，倒序枚举。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr ll inf = 0x3f3f3f3f3f3f3f3f;

ll powq(int x, int n) {
    ll res = 1;
    while (n--) {
        res *= x;
        if (res > inf) return inf;
    }
    return res;
}

int main() {
    ll n;
    cin >> n;

    bool ok = false;
    for (int i = 30; i >= 1; i--) {
        ll res = 0;
        if (ok) {
            break;
        }
        for (int j = 1; ; j++) {
            res += ll(powq(j, i));
            if (res > n) {
                break;
            }
            if (res == n) {
                ok = true;
                for (int k = 1; k <= j; k++) {
                    cout << k << "^" << i << "+\n"[k == j];
                }
                break;
            }
        }
    }
    if (!ok) {
        cout << "Impossible for " << n << ".";
    }

    return 0;
}

8 / L1-8

每次都循环找最大值期望复杂度$\operatorname{O}(kmn)$，会 TLE。

降序枚举，同时标记这一行列已经被删除，如果枚举到被删除的就跳过。不算离散化的复杂度$\operatorname{O}[k(m+n)+mn]$。

输出不能有行末空格好烦……

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    int n, m, k;
    cin >> n >> m >> k;

    vector a(n, vector<int>(m));
    vector<int> alls;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            alls.push_back(a[i][j]);
        }
    }
    sort(alls.begin(), alls.end());
    vector<pair<int, int>> id(n * m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            a[i][j] = lower_bound(alls.begin(), alls.end(), a[i][j]) - alls.begin();
            id[a[i][j]] = { i, j };
        }
    }

    while (k) {
        auto [imax, jmax] = id.back();
        id.pop_back();
        if (a[imax][jmax] == -1) continue;
        k--;
        for (int i = 0; i < n; i++) {
            a[i][jmax] = -1;
        }
        for (int j = 0; j < m; j++) {
            a[imax][j] = -1;
        }
    }
    for (int i = 0; i < n; i++) {
        int fst = true;
        for (int j = 0; j < m; j++) {
            if (a[i][j] == -1) {
                continue;
            }
            if (fst) {
                fst = 0;
            } else {
                cout << " ";
            }
            cout << alls[a[i][j]];
        }
        if (!fst) cout << endl;
    }
    return 0;
}

9 / L2-1

反复找最内层的括号，小数据范围无需考虑复杂度。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    while (!s.empty()) {
        int l = -1, r = -1;
        for (int i = 0; i < s.size(); i++) {
            auto c = s[i];
            if (c == '(') {
                l = i;
            }
            if (c == ')' && l != -1) {
                r = i;
                cout << s.substr(l + 1, r - l - 1) << endl;
                s = s.substr(0, l) + s.substr(r + 1);
                break;
            }
        }
    }
    return 0;
}

*10 / L2-2

（三点一线）

拼尽全力启发式枚举，还是 T 了两个点。

UPD：应该用普通数组存每个地方有没有点，不能用 set 或 map，多个 log 就不行了。

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
constexpr ll mod = 998244353;
constexpr int N = 1000008;

bitset<2 * N> mp;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a[3];
    while (n--) {
        int x, y;
        cin >> x >> y;
        a[y].push_back(x);
    }

    for (int i = 0; i < 3; i++) {
        sort(a[i].begin(), a[i].end());
        a[i].erase(unique(a[i].begin(), a[i].end()), a[i].end());
    }

    vector<array<int, 3>> res;
    if (a[0].size() < a[2].size() && a[1].size() < a[2].size()) {
        for (auto x : a[2]) {
            mp.set(x + N);
        }
        for (auto x : a[1]) {
            for (auto y : a[0]) {
                if (2 * x - y > N) break;
                if (mp.test(2 * x - y + N)) {
                    int z = 2 * x - y;
                    res.push_back({ x, y, z });
                }
            }
        }
    } else if (a[2].size() < a[0].size() && a[1].size() < a[0].size()) {
        for (auto x : a[0]) {
            mp.set(x + N);
        }
        for (auto x : a[1]) {
            for (auto y : a[2]) {
                if (2 * x - y > N) break;
                if (mp.test(2 * x - y + N)) {
                    int z = 2 * x - y;
                    res.push_back({ x, z, y });
                }
            }
        }
    } else {
        for (auto x : a[1]) {
            mp.set(x + N);
        }
        for (auto x : a[0]) {
            for (auto y : a[2]) {
                if ((x + y) % 2 == 0 && mp.test((x + y) / 2 + N)) {
                    int z = (x + y) / 2;
                    res.push_back({ z, x, y });
                }
            }
        }
    }

    if (res.size()) {
        sort(res.begin(), res.end());
        for (auto [x, y, z] : res) {
            cout << "[" << y << ", 0] ";
            cout << "[" << x << ", 1] ";
            cout << "[" << z << ", 2]\n";
        }
    } else {
        cout << -1 << endl;
    }

    return 0;
}

11 / L2-3

差分。

#include <bits/stdc++.h>
using namespace std;

int read() {
    int x, y, z;
    char c;
    cin >> x >> c >> y >> c >> z;
    return (x * 60 + y) * 60 + z;
}

int main() {
    int n;
    cin >> n;

    vector<int> diff(24 * 60 * 60 + 1);
    for (int i = 0; i < n; i++) {
        int l = read(), r = read();
        r++;
        diff[l]++;
        diff[r]--;
    }
    for (int i = 0; i < 24 * 60 * 60; i++) {
        diff[i + 1] += diff[i];
    }
    cout << *max_element(diff.begin(), diff.end()) << endl;
    
    return 0;
}

12 / L2-4

从最高位开始枚举。时间复杂度是答案的数量。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int N;
    ll l, r;
    cin >> N >> l >> r;

    vector<ll> pow(N + 1);
    pow[0] = 1;
    for (int i = 1; i <= N; i++) {
        pow[i] = pow[i - 1] * 10;
    }

    bool out = false;
    auto dfs = [&](auto&& dfs, ll x, int n) -> void {
        if (n == -1) {
            cout << x << endl;
            out = true;
            return;
        }
        for (int i = 0; i <= 9; i++) {
            if (i == 0 && N - n == 1) continue;   // first not 0
            ll y = x + i * pow[n];
            if (y / pow[n] % (N - n) == 0 && y / pow[n] >= l / pow[n] && y / pow[n] <= r / pow[n]) {
                dfs(dfs, y, n - 1);
            }
        }
    };
    dfs(dfs, 0, N - 1);

    if (!out) {
        cout << "No Solution";
    }

    return 0;
}

13 / L3-1

拼劲全力 +1，还手搓了个快读。

每次询问跑 dij 不行，需要 Floyd 预处理全源最短路，复杂度$\operatorname{O}(n^{3}+qn)$。

#include <bits/stdc++.h>
using namespace std;

constexpr int inf = 0x3f3f3f3f;

inline int read() {
    int res = 0, fu = 1;
    char c = getchar();
    while (c > '9' || c < '0') {
        if (c == '-') {
            fu = -1;
        }
        c = getchar();
    }
    while (c <= '9' && c >= '0') {
        res = (res << 1) + (res << 3) + c - '0';
        c = getchar();
    }
    return res;
}

struct node {
    int w, d;
};
node operator + (const node& l, const node& r) {
    return {
        min(inf, l.w + r.w),
        l.d + r.d
    };
};
node min(const node& l, const node& r) {
    if (l.w < r.w) {
        return l;
    }
    if (l.w > r.w) {
        return r;
    }
    return { l.w, max(l.d, r.d) };
}

int main() {
    int b = read(), n = read(), m = read(), k = read();

    vector dis(n, vector<node>(n, node{ inf, 0 }));
    for (int u = 0; u < n; u++) {
        dis[u][u] = {0,0};
    }
    while (m--) {
        int u = read(), v = read(), w = read(), d = read();
        u--;
        v--;
        dis[u][v] = dis[v][u] = node{ w, d };
    }
    for (int k = 0; k < n; k++) {
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                dis[u][v] = min(dis[u][v], dis[u][k] + dis[k][v]);
            }
        }
    }

    while (k--) {
        int s = read();
        s--;

        vector<int> res;
        for (int i = 0; i < n; i++) {
            if (dis[s][i].w <= b && i != s) {
                res.push_back(i);
            }
        }

        if (res.empty()) {
            cout << "T_T" << endl;
        } else {
            int maxval = 0;
            bool fst = true;
            for (auto u : res) {
                if (fst) {
                    fst = false;
                } else {
                    cout << " ";
                }
                cout << u + 1;
                maxval = max(maxval, dis[s][u].d);
            }
            cout << endl;
            fst = true;
            for (auto u : res) {
                if (dis[s][u].d == maxval) {
                    if (fst) {
                        fst = false;
                    } else {
                        cout << " ";
                    }
                    cout << u + 1;
                }
            }
            cout << endl;
        }
    }

    return 0;
}

14 / L3-2

拆成左上、左、左下、下……八个方向分别算。

其实只需要考虑左上怎么算就行，递推，$(i,j)$ 左上方（不含正上正左）的距离和 =$(i-1,j-1)$ 左上方（含正上正左）的距离和 +$(i,j)$ 左上方的方格数量。

预处理好 pre 数组，对于每个数$\operatorname{O}(1)$ 查询。

复杂度$\operatorname{O}(mn)$。多循环一次就会 T。

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
constexpr ll inf = 0x3f3f3f3f3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int n, m;
    cin >> n >> m;

    auto cal = [&](int i) {
        return (i * (i + 1ll) / 2);
    };

    vector pre(n, vector<ll>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            pre[i][j] = cal(j) + cal(i);
            if (i && j) pre[i][j] += pre[i - 1][j - 1] + 1ll * i * j;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            ll x;
            cin >> x;
            cout << x * (pre[i][j] + pre[n - 1 - i][j] + pre[i][m - 1 - j] + pre[n - 1 - i][m - 1 - j] - cal(j) - cal(m - 1 - j) - cal(i) - cal(n - 1 - i)) << " \n"[j == m - 1];
        }
    }

    return 0;
}

*15 / L3-3

不会，打了个$\operatorname{O}(n!\cdot n^{2})$（可能还不止）的暴力骗了点分。

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
constexpr ll mod = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int n;
    cin >> n;

    vector<vector<int>> E(n);
    for (int i = 1; i < n; i++) {
        int p;
        cin >> p;
        p--;
        E[p].push_back(i);
    }

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    ll sum = 0;
    vector<pair<vector<int>, ll>> viss;
    do {
        ll res = 1;
        vector<int> vis(n);
        int cnt = 0;
        vector<int> b;
        for (auto s : p) {
            if (vis[s]) continue;
            b.push_back(s);
            auto dfs = [&](auto&& dfs, int u) -> void {
                vis[u] = 1;
                res *= a[cnt];
                res %= mod;
                for (auto v : E[u]) {
                    dfs(dfs, v);
                }
            };
            dfs(dfs, s);
            cnt++;
        }
        viss.push_back({ b, res });
    } while (next_permutation(p.begin(), p.end()));

    sort(viss.begin(), viss.end());
    viss.erase(unique(viss.begin(), viss.end()), viss.end());
    for (auto [_, res] : viss) {
        sum += res;
        sum %= mod;
    }
    cout << sum << endl;

    return 0;
}