2025 扬州大学 GPLT 团体天梯赛校内选拔赛题解

L1-1 成分复杂的出题人

题意简述

输出 Steins;Gate, Monogatari or Touhou?

解题思路（语法）

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

void marisa(){
    puts("Steins;Gate, Monogatari or Touhou?");
}

int main(){
    ios;

    int T = 1; // cin >> T;
    while(T -- ) marisa();

    return 0;
}

L1-2 蛋糕除了姆Q人人有份

题意简述

给定一个整数 $n$ ，判断是否在 $100 \sim 110$ 范围内。

解题思路（语法）

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

void marisa(){
    int n; cin >> n;
    if(n < 100) cout << "Nobody can stop me!!!" << "\n";
    else if(n <= 110) cout << "Just one piece, please." << "\n";
    else cout << "It is impossible!!!" << "\n";
}

int main(){
    ios;

    int T = 1; cin >> T;
    while(T -- ) marisa();

    return 0;
}

L1-3 寒冬无玉絮

题意简述

一个长方形四角坐标为 $(0, 0), (x, 0), (0, y), (x, y)$ ，内部一圆的圆心位于 $(a, b)$ ，求圆半径最大可以是多少。

解题思路（数学）

取圆心到四个边界距离的最小值即可，即 $\min(a, b, x - a, y - b)$ 。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

void marisa(){
    int x, y, a, b; cin >> x >> y >> a >> b;
    cout << min({a, b, x - a, y - b}) << "\n";
}

int main(){
    ios;

    int T = 1; // cin >> T;
    while(T -- ) marisa();

    return 0;
}

L1-4 春眠猫之梦

题意简述

给定一个序列 $a_1, a_2, \ldots, a_n$ 和一个整数 $m$ ，序列 $a$ 包含若干个 $0,1$ 和一个 $2$ 。判断 $2$ 前面的 $1$ 的个数是否小于 $m$ ，并求出 $1$ 和 $2$ 个数之和超过 $m$ 多少。

解题思路（模拟）

写法很多，此处提供一种很简单的写法。遍历整个序列，忽略不买的（ $a = 0$ ）；当遍历到买的人（ $a \ge 1$ ），更新 $m -= 1$ ；如果遍历到 $a = 2$ ，特别判断一下此时是否还有柠檬茶（ $m > 0$ ）并输出第一小问答案即可；最终 $\max(0, -m)$ 就是买不到的人数（ $-m$ 即超额卖出的数量，也有可能最后没有超额卖出，取一下与 $0$ 的较大值）。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

void marisa(){
    int n, m; cin >> n >> m;
    for(int i = 1, a; i <= n; i ++ ){
        cin >> a;
        if(!a) continue; // 忽略不买的
        if(a == 2){ // 判断妖梦是否可以买到
            cout << (m > 0 ? "You love me, I love u~" : "baka!") << "\n";
        }
        m -- ;
    }
    cout << max(0, -m) << "\n"; // max(0, -m) 就是买不到的人数
}

int main(){
    ios;

    int T = 1; // cin >> T;
    while(T -- ) marisa();

    return 0;
}

L1-5 茶与金平糖

题意简述

给定一个序列 $c_1, c_2, \ldots, c_n$ ，可以进行无限次选择一个 $c_i$ 加上 $k$ 的操作，求是否可以使得所有 $c_i$ 一样，若可以，求出最少需要的次数。

解题思路（模拟，数学，贪心）

每个 $c_i$ 加上若干个 $k$ 使得全部相等，当且仅当每个 $c_i$ 除以 $k$ 的余数相等。记 $\left \lfloor \frac{c_i}{k} \right \rfloor$ 为 $t_i$ ， $c_i \mod k$ 为 $r_i$ ，每个 $c_i$ 可以被看作是 $t_i \times k + r_i$ 。由于 $r_i < k$ 而每次操作只能加 $k$ ，故只有所有 $r_i$ （即 $c_i \mod k$ ）相等时，才可以使得所有 $c_i$ 相等。

我们要使得总操作次数尽可能少，只需要求出 $c_i$ 中的最大值 $c_{max}$ ，每个 $c_i$ 所需操作次数即 $\frac{c_{max} - c_i}{k}$ ，累加答案即可。注意需要开 long long。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

void marisa(){
    int n, k; cin >> n >> k;
    vector<int> c(n + 1);
    int mx = 0;
    for(int i = 1; i <= n; i ++ ) cin >> c[i], mx = max(mx, c[i]);
    long long ans = 0;
    for(int i = 1; i <= n; i ++ ){
        if(mx % k != c[i] % k){ // 需要所有余数一样
            cout << "Stay with me, Reimu." << "\n";
            return;
        }
        ans += (mx - c[i]) / k; // 累加答案
    }
    cout << "Marisa needs " << ans << " times." << "\n";
}

int main(){
    ios;

    int T = 1; cin >> T;
    while(T -- ) marisa();

    return 0;
}

L1-6 团体天梯2077

题意简述

有 $n$ 条过题记录，格式为 小时:分钟题目等级-题目编号，求赛时（ $16:30$ 及之前）通过多少道题目，赛后（ $16:30$ 之后）通过了多少道 赛时没通过 的题目。

解题思路（模拟，集合）

做法很多，此处提供一个 unordered_set 集合做法。对于输入的时间，可以获取其分钟数来判断是否为赛时通过还是赛后通过，也可直接借助 string 判断与 “16:30” 的字典序关系。通过的每个记录放入集合 unordered_set 中（自带去重），集合 $s_1$ 记录赛时通过的题，集合 $s_2$ 记录赛后通过的题。统计一下集合 $s_1$ 中各阶段题目即可解决第一小问；遍历 $s_2$ 中的每个题目，统计 $s_1$ 中未出现过的题目即可解决第二小问。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

void marisa(){
    int n; cin >> n;
    unordered_set<string> s1, s2; // 集合自带去重
    for(int i = 1; i <= n; i ++ ){
        string s, t; cin >> s >> t; // 时间 题目
        if(s <= "16:30") s1.insert(t); // 赛时做出的题目
        else s2.insert(t); // 赛后通过的题目
    }
    vector<int> cnt(4); // 统计各个阶段做出的题目数
    for(const auto& s : s1) cnt[s[1] - '0'] ++ ;
    cout << cnt[1] << ' ' << cnt[2] << ' ' << cnt[3] << "\n";
    int res = 0; // 赛后补做的题目，去除赛时通过的
    for(const auto& s : s2) res += (!s1.count(s));
    cout << res << "\n";
}

int main(){
    ios;

    int T = 1; // cin >> T;
    while(T -- ) marisa();

    return 0;
}

L1-7 怎么还有初音未来啊？

题意简述

将字符串 $s$ 中所有 “easy”（不区分大小写）替换为 “miku”，保持大小写一致。若没有 “easy”（不区分大小写），输出 Not Easy.。

解题思路 1 （模拟，字符串基础）

由于字符串 $s$ 有空格，需要使用 getline 函数读取；前面进行了 cin 读入数据，需要额外读取一个换行符（使用 cin.ignore() 或 getchar() 均可）。

替换的 “easy” 和 “miku” 长度均为 $4$ ，可以检查连续的 $4$ 个位置是否构成 “easy” 然后替换即可，注意维持大小写。

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

int main(){
    int n; cin >> n;
    cin.ignore();
    for(int i = 1; i <= n; i ++ ){
        string s; getline(cin, s);
        bool has_easy = false;
        for(int j = 0; j + 3 < (int)s.size(); j ++ ){
            string t = s.substr(j, 4);
            for(auto& ch : t) ch = tolower(ch); 
            if(t == "easy"){
                has_easy = true;
                s[j] = (s[j] == 'E' ? 'M' : 'm');
                s[j + 1] = (s[j + 1] == 'A' ? 'I' : 'i');
                s[j + 2] = (s[j + 2] == 'S' ? 'K' : 'k');
                s[j + 3] = (s[j + 3] == 'Y' ? 'U' : 'u');
            }
        }
        cout << (has_easy ? s : "Not Easy.") << "\n";
    }

    return 0;
}

解题思路 2 （模拟，std::string）

记录每个位置的大小写情况 $up_i$ ，并将所有字符小写化，方便后续查找 “easy”。使用 s.find() 实现查找 “easy”（用法可见 std::string::find），结合 s.replace() 替换掉 “easy” 的部分为 “miku”（用法可见 std::string::replace）。借助先前记录的大小写情况 $up_i$ 最终输出一下替换后的字符串。

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

int main(){
    int n; cin >> n;
    cin.ignore();
    for(int i = 1; i <= n; i ++ ){
        string s; getline(cin, s);
        vector<bool> up((int)s.size(), false);
        for(int j = 0; j < (int)s.size(); j ++ ){
            up[j] = isupper(s[j]); // 记录一下原先是否大写
            s[j] = tolower(s[j]); // 全部小写化
        }
        int pos = s.find("easy"); // 第一个easy的首位置
        if(pos == -1){ // 没有 easy
            cout << "Not Easy." << "\n"; 
            continue;
        }
        while(pos != -1){
            s.replace(pos, 4, "miku"); // 替换 pos ~ pos + 3 为miku
            pos = s.find("easy", pos + 4); // 从pos + 4开始找下一个easy的首位置
        }
        for(int j = 0; j < (int)s.size(); j ++ ){
            if(up[j]) s[j] = toupper(s[j]);
        }
        cout << s << "\n";
    }

    return 0;
}

L1-8 文文的大新闻！

题意简述

给定一个 $n \times m$ 的 $01$ 矩阵，判断有多少个子矩阵满足：

是一个 $5 \times 5$ 的子矩阵；
第 $1$ 行和第 $5$ 行中第一个和最后一个位置是 $1$ ；
第 $2$ 行和第 $4$ 行中第二、三和第四个位置是 $1$ ；
第 $3$ 行中第二个和第四个位置是 $1$ ；
其余位置均为 $0$ 。

以化简分数形式输出满足条件 $5 \times 5$ 子矩阵个数占总 $5 \times 5$ 子矩阵个数的比率。

解题思路（模拟）

可以发现，满足条件的子矩阵形如：

直接暴力判断统计和这个一样的子矩阵个数 $a$ 。总子矩阵个数为 $b = (n - 4) \times (m - 4)$ ，将两数除以 $a$ 和 $b$ 的最大公约数 $gcd(a, b)$ 约分即可。特别的，若 $a = 0$ 或 $a = b$ ，输出整数 $0$ 或 $1$ 。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)


vector<string> tmp = {
    "10001",
    "01110",
    "01010",
    "01110",
    "10001"
};

void marisa(){
    int n, m; cin >> n >> m;
    vector<string> g(n);
    for(int i = 0; i < n; i ++ ) cin >> g[i];

    auto check = [&](int x, int y){
        for(int i = 0; i < 5; i ++ )
            for(int j = 0; j < 5; j ++ )
                if(g[x + i][y + j] != tmp[i][j]) return false;
        return true;
    };

    int a = 0, b = (n - 4) * (m - 4);
    for(int i = 0; i + 4 < n; i ++ )
        for(int j = 0; j + 4 < m; j ++ )
            if(check(i, j)) a ++ ;

    if(a == 0 || a == b){ // 特判
        cout << a / b << "\n";
        return;
    }

    int gg = gcd(a, b);
    a /= gg, b /= gg;
    cout << a << "/" << b << "\n";
}

int main(){
    ios;

    int T = 1; // cin >> T;
    while(T -- ) marisa();

    return 0;
}

L2-1 七色的甜蜜魔法

题意简述

给定一个数组 $a_1, a_2, \ldots, a_n$ ，可以选取一个区间 $a_l, a_{l + 1}, \ldots, a_r$ 全部变为 $b$ ，也可不操作，求数组和最大值。

解题思路（动态规划）

实际上就是求选一段子数组全部变为 $b$ 数组和最大可以提升多少，我们可以将 $a_i$ 转换为 $b - a_i$ ，求出每个 $a_i$ 变为 $b$ 会提升多少。然后在新数组上求 最大子数组和，最后加上原始数组和即可。时间复杂度 $\mathcal{O}(n)$ 。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

using ll = long long;

void marisa(){
    int n, b; cin >> n >> b;
    vector<int> a(n + 1);
    ll sum = 0;
    for(int i = 1; i <= n; i ++ ){
        cin >> a[i], sum += a[i];
        a[i] = b - a[i]; // 转换为每个数变为b提升多少
    }
    ll dp = -1e18, mx = 0;
    for(int i = 1; i <= n; i ++ ){ // 最大子数组和
        dp = max(dp, 0ll) + a[i];
        mx = max(mx, dp);
    }
    cout << sum + mx << "\n";
}

int main(){
    ios;

    int T = 1; // cin >> T;
    while(T -- ) marisa();

    return 0;
}

L2-2 天狗卡牌游戏

题意简述

给定一个序列 $a_1, a_2, \ldots, a_n$ ，构建一个新序列：

若 $a_i = 1$ ，将一个 M 放到序列末尾；
若 $a_i = 2$ ，将一个 H 放到序列末尾；
若 $a_i = 3$ ，将一个 A 放到序列末尾，并判断是否出现子序列 MHA。

若出现子序列 MHA，删除序列中第一个使得出现子序列的 M 和 H，并删除当前 A。

求最终序列，以及每次删除的 M，H，A 对应序列 $a$ 中的下标。

解题思路（队列、模拟）

用两个队列 $q_m$ 和 $q_h$ 分别存储每个轮次 M 和 H 的下标。当 $a_i = 1$ 或 $a_i = 2$ ，直接将 M 或 H 对应下标存到队列中。

当 $a_i = 3$ ，队列中的下标显然都是小于 $i$ 的，序列中会出现子序列 MHA 当且仅当队列 q_m 和 q_h 中分别存在一个 $i_m$ 和 $i_h$ 满足 $i_m < i_h$ 。

对于第一个使得出现子序列 MHA 的 M，显然就是当前队列 $q_m$ 的队首，记为 $i_m$ ；

对于第一个使得出现子序列 MHA 的 H， $q_h$ 中小于 $i_m$ 的元素都是没用的，后续也不可能作为答案，故直接将这些元素出队即可。若之后 $q_h$ 中还有元素，那么此时 $q_h$ 的队首就是 $i_m$ 后第一个 $i_h$ 。故当前删除操作的 M，H 和 A 下标即 $i_m$ ， $i_h$ 和 $i$ 。

标记一下每次删除的下标，并将删除的下标存储到答案中。最后根据标记构造序列，并输出答案即可。时间复杂度为 $\mathcal{O}(n)$ 。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)


void marisa(){
    int n; cin >> n;
    vector<int> a(n + 1);
    queue<int> qm, qh;
    vector<tuple<int, int, int>> ans;
    vector<bool> vis(n + 1);
    for(int i = 1; i <= n; i ++ ){
        cin >> a[i];
        if(a[i] == 1) qm.emplace(i);
        else if(a[i] == 2) qh.emplace(i);
        else{
            if(qm.size() && qh.size()){ // 是否有 i_m 和 i_h
                while(qh.size() && qh.front() < qm.front()){
                    qh.pop(); // 所有 i_h < i_m 都是没用的
                }
                if(qh.size()){ // 若还有 i_h，取队首即第一个 H
                    int im = qm.front(); qm.pop();
                    int ih = qh.front(); qh.pop();
                    ans.emplace_back(im, ih, i); // 存储答案
                    vis[im] = vis[ih] = vis[i] = true; // 标记下标
                }
            }
        }
    }
    string s = "";
    for(int i = 1; i <= n; i ++ ){ // 构造序列
        if(vis[i]) continue;
        if(a[i] == 1) s += 'M';
        else if(a[i] == 2) s += 'H';
        else s += 'A';
    }
    cout << (s.empty() ? "Ayayayaya" : s) << "\n";
    cout << ans.size() << "\n";
    for(const auto& [a, b, c] : ans){ // 输出答案
        cout << a << ' ' << b << ' ' << c << "\n"; 
    }
}

int main(){
    ios;

    int T = 1; // cin >> T;
    while(T -- ) marisa();

    return 0;
}

L2-3 我的朋友很少

题意简述

$n$ 个人，每个人名字为 $s_i$ ，有 $c_i$ 个喜欢的东西 $t_1, t_2, \ldots, t_{c_i}$ 。拥有同一个喜欢的东西的人属于一个集合。求集合个数、每个集合大小以及每个集合最小编号的人。

解题思路（并查集）

我们可以用一个 unordered_map<string, vector<int>> 存储每个东西喜欢的人的编号。使用并查集将每个 mp[t] 中的人合并（选取第一个人依次和后面的合并即可），合并过程中优先将编号较小的作为首领。最后将所有集合首领存入答案，并按照题意排序输出即可（集合首领就是集合中最小编号的人）。假设每个东西喜欢的人数为 $k_i$ ， $\sum k_i$ 为 $10^6$ 量级，并查集每次合并的时间复杂度为 $\mathcal{O}(\log n)$ ，可以通过本题。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

const int N = 1010;

int fa[N], sz[N];
int find(int x){ return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int x, int y){
    int fx = find(x), fy = find(y);
    if(fx == fy) return;
    if(fx > fy) swap(fx, fy); // 编号小优先作为首领
    fa[fy] = fx, sz[fx] += sz[fy]; 
}

void marisa(){
    int n; cin >> n;
    vector<string> s(n + 1);
    for(int i = 1; i <= n; i ++ ){
        cin >> s[i];
        fa[i] = i, sz[i] = 1;
    }
    unordered_map<string, vector<int>> mp;
    for(int i = 1, c; i <= n; i ++ ){
        cin >> c; 
        for(int j = 1; j <= c; j ++ ){
            string t; cin >> t; 
            mp[t].emplace_back(i);
        }
    }
    for(const auto& [_, v] : mp){
        for(int i = 1; i < (int)v.size(); i ++ ){
            merge(v[0], v[i]); // 合并同一喜欢东西的角色
        }
    }
    vector<int> ans;
    for(int i = 1; i <= n; i ++ ) if(fa[i] == i) ans.emplace_back(i);
    sort(begin(ans), end(ans), [&](const int& a, const int& b){
        if(sz[a] != sz[b]) return sz[a] > sz[b]; // 按照数量非递增
        return a < b; // 按照最小编号递增
    });
    cout << ans.size() << "\n";
    for(const auto& x : ans) cout << sz[x] << ' ' << s[x] << "\n";
}

int main(){
    ios;

    int T = 1; // cin >> T;
    while(T -- ) marisa();

    return 0;
}

L2-4 数学代课老师教历史的？

题意简述

给定一个字符串 $s$ ，还原一个合法排列 $p_1, p_2,\ldots, p_n$ ，保证有解且 $n \leq 50$ 。

解题思路（dfs，爆搜）

首先记字符串长度为 $l$ ，我们可以发现排列中数字的长度只可能为 $1$ 或 $2$ ：

当 $l \leq 9$ ，所有数都是一位数，故 $n = 9$ ；
当 $l > 9$ ，除了 $1 \sim 9$ 其他都是两位数，故 $n = 9 + \frac{l - 9}{2}$ 。

从字符串第一个位置开始爆搜枚举，每次枚举可以取一个字符作为一个数，也可以取两个连续的字符作为一个数，判断构成的数在 $1 \sim n$ 范围内且未使用过即可进行下一步搜索。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

void marisa(){
    string s; cin >> s;
    int l = s.size();
    int n = (l < 10 ? l : 9 + (l - 9) / 2); // 排列长度
    
    vector<bool> vis(n + 1);
    vector<int> ans, v;
    function<void(int)> dfs = [&](int k){
        if(!ans.empty()) return; // 已经有解
        if(k >= l){ ans = v; return; } // 得到一个解
        int num = s[k] - '0'; // 取一个字符凑一个数
        if(1 <= num && num <= n && !vis[num]){
            vis[num] = true;
            v.push_back(num);
            dfs(k + 1);
            v.pop_back(); // 回溯
            vis[num] = false;
        }
        if(k + 1 < l){ // 取两个字符凑一个数
            num = num * 10 + (s[k + 1] - '0');
            if(1 <= num && num <= n && !vis[num]){
                vis[num] = true;
                v.push_back(num);
                dfs(k + 2);
                v.pop_back(); // 回溯
                vis[num] = false;
            }
        }
    };

    dfs(0);

    for(const auto& x : ans) cout << x << ' ';
}

int main(){
    ios;

    int T = 1; // cin >> T;
    while(T -- ) marisa();

    return 0;
}

L3-1 泽之川建筑工程师

题意简述

给定一个 $n$ 个点 $m$ 条边的带权无向图，拆除一些边且保持 $1 \rightarrow s_1$ 和 $1 \rightarrow s_2$ 的最短路长度分别不超过 $d_1$ 和 $d_2$ 。求最多可以拆除的边长度之和。

解题思路（最短路，dijkstra）

为了拆除尽可能多长度的边，显然我们要保留的边是 $1 \rightarrow s_1$ 和 $1 \rightarrow s_2$ 最短路径上的边。如果路径不重合，那么答案就是总边权长度减去 $1 \rightarrow s_1$ 和 $1 \rightarrow s_2$ 最短路的长度。关键在于 $1 \rightarrow s_1$ 和 $1 \rightarrow s_2$ 最短路径上可能出现重合部分。

假设 $1 \rightarrow s_1$ 和 $1 \rightarrow s_2$ 有最后一个重合的点为 $x$ ，只可能出现如下图的情况：

即 $1 \rightarrow x$ 的路径都是重合的。若 $1 \rightarrow x$ 中间有一点 $y$ ，使得 $y \rightarrow x$ 的路径不重合，显然不可能。即便有两条路径，页只可能出现这两条 $y \rightarrow x$ 的最短路长度一样的情况，而最短路只需要选取其中一条，故 $1 \rightarrow x$ 的路径都是重合的。

故我们可以将保留的路径分为三个部分： $1 \rightarrow x$ ， $x \rightarrow s_1$ 和 $x \rightarrow s_2$ 。问题转换为找出一点 $x$ 使得三部分路径长度和最小。如果枚举 $x$ 求到其他点距离，需要 $n$ 次 $dijktra$ ，会超时。

由于图是无向的，故我们转变为求 $1 \rightarrow x$ ， $s_1 \rightarrow x$ ， $s_2 \rightarrow x$ 三部分长度。我们 只需要三次 $dijkstra$ 算法分别求出 $1$ 、 $s_1$ 和 $s_2$ 到所有点的距离。

由于我们枚举的 $x$ 肯定是在最短路径上的，对于 $dist_{1 \rightarrow s_1}$ 和 $dist_{1 \rightarrow s_2}$ 分别不超过 $d_1$ 和 $d_2$ ，只需要提前判断一下 $1$ 到两点最短距离是否满足条件即可。

最后枚举重合点 $x$ ，找出需要保留的最短路径长度和，进而求出最大可拆除边权和即可。

时间复杂度 $\mathcal{O}((n + m)\log n)$ 。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

void marisa(){
    int n, m; cin >> n >> m;
    vector<vector<pii>> e(n + 1);
    ll sum = 0;
    for(int i = 1, u, v, w; i <= m; i ++ ){
        cin >> u >> v >> w;
        e[u].emplace_back(v, w);
        e[v].emplace_back(u, w);
        sum += w;
    }
    int s1, d1, s2, d2; cin >> s1 >> d1 >> s2 >> d2;

    vector<vector<ll>> dist(3, vector<ll>(n + 1, 1e18));
    auto dijkstra = [&](int src, vector<ll>& dist){
        vector<bool> st(n + 1, false);
        priority_queue<pll, vector<pll>, greater<pll>> q;
        q.emplace(dist[src] = 0, src);
        while(q.size()){
            auto [d, u] = q.top();
            q.pop();
            if(st[u]) continue;
            st[u] = true;
            for(const auto& [v, w] : e[u]){
                if(dist[v] > d + w){
                    q.emplace(dist[v] = d + w, v);
                }
            }
        }
    };

    dijkstra(1, dist[0]);  // 1 到所有点距离
    dijkstra(s1, dist[1]); // s1 到所有点距离
    dijkstra(s2, dist[2]); // s2 到所有点距离

    if(dist[0][s1] > d1 || dist[0][s2] > d2){ // 提前判断即可
        cout << "What can I say, bba out." << "\n";
        return;
    }

    ll ans = 0;
    for(int x = 1; x <= n; x ++ ) // 枚举x
        ans = max(ans, sum - dist[0][x] - dist[1][x] - dist[2][x]);
    cout << ans << "\n";
}

int main(){
    ios;

    int T = 1; // cin >> T;
    while(T -- ) marisa();

    return 0;
}

L3-2 我是卖报的小行家

题意简述

给定一个 $n$ 节点的树，有 $k$ 个关键点。每次询问从 $s$ 出发经过所有关键点至少一次后到 $t$ 的最短距离。

解题思路（倍增，LCA）

考虑 $s = t$ ， $k = n$ 的情况。所有点都是关键点， $s$ 和 $t$ 自然也在关键点之中，且 $s$ 和 $t$ 是同一个点。我们需要从一点出发绕过所有点回到起点，所有边都要来回走一遍，故此时的答案就是 所有边的边权和 $\times 2$ 。

考虑 $s \neq t$ ， $k = n$ 的情况。我们可以类似于上面的情况将所有边都来回走一遍，但发现并不需要从终点 $t$ 走回到 $s$ ，从 $s \rightarrow t$ 路径上的边只需要走一遍即可。我们必然可以找到一种方案从 $s$ 经过所有关键点到 $t$ 结束，故此时答案为 所有边的边权和 $\times 2$ 减去 $s \rightarrow t$ 的距离。

考虑 $s \neq t$ ， $k \neq n$ ，但 $s, t$ 都是关键点 的情况。我们可以在树上找出一个 包含 $k$ 个关键点的最小连通块，这个连通块上的边就是 $k$ 个关键点两两之间路径的并集。为了方便处理，我们可以 选取一个关键点作为根 进行搜索，一个点位于最小连通块内 当且仅当 该点子树含有关键点。故此时答案为 包含 $k$ 个关键点的最小连通块边权和 $\times 2$ 减去 $s \rightarrow t$ 的距离。

考虑一般情况。我们可以分别在 包含 $k$ 个关键点的最小连通块 种距离 $s$ 和 $t$ 最近的点 $s_{nc}$ 和 $t_{nc}$ ，那么答案变为三个部分：

第一部分为 $s \rightarrow s_{nc}$ 的距离，这部分可以倍增预处理求 LCA 解决；
第二部分为 $s_{nc} \rightarrow t_{nc}$ 的距离，这部分类似于情况 $s \neq t$ ， $k \neq n$ ，但 $s, t$ 都是关键点。故此部分答案为 包含 $k$ 个关键点的最小连通块边权和 $\times 2$ 减去 $s_{nc} \rightarrow t_{nc}$ 的距离；
第三部分为 $t_{nc} \rightarrow t$ 的距离，也可以求 LCA 解决。

对于如何找到在 最小连通块 中距离最近的点 $s_{nc}$ 和 $t_{nc}$ ，可以借助倍增解决。如果一点 $u$ 向上 $2^{i}$ 步可达的点为根的子树不包含关键点，那么令 $u = f[u][i]$ 继续倍增，直到最后 $u$ 的父节点就是距离 最小连通块 最近的点。特别的，如果 $s$ 或 $t$ 本身就在 最小连通块 内，距离最近的点就是其本身。

时间复杂度 $\mathcal{O}(n \log n)$ 。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

using pii = pair<int, int>;
const int N = 1e5 + 10;

int n, m, q, c[N], sz[N]; // sz[u]: 子树u中关键点个数
int dep[N], dist[N]; // dist[u]: rt -> u 的距离
int f[N][22]; // f[u][k]: u 向上走2^k步到达的点
vector<pii> e[N];

void dfs(int u, int fa){ // 倍增预处理点的深度等
    sz[u] = c[u];
    f[u][0] = fa, dep[u] = dep[fa] + 1;
    for(int k = 1; k <= 20; k ++ )
        f[u][k] = f[f[u][k - 1]][k - 1];
    for(const auto& [v, w] : e[u]){
        if(v == fa) continue;
        dist[v] = dist[u] + w;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

int lca(int x, int y){ // 两点最近公共祖先
    if(dep[x] < dep[y]) swap(x, y);
    for(int k = 20; ~k; k -- )
        if(dep[f[x][k]] >= dep[y]) x = f[x][k];
    if(x == y) return x;
    for(int k = 20; ~k; k -- )
        if(f[x][k] != f[y][k]) x = f[x][k], y = f[y][k];
    return f[x][0];
}

inline int get_dist(int x, int y){ // 两点距离
    return dist[x] + dist[y] - 2 * dist[lca(x, y)];
}

inline int get_nc(int u){ // 倍增向上找到最近关键点
    if(sz[u]) return u; // 在连通块内，不需要到达一个最近关键点
    for(int k = 20; ~k; k -- ) 
        if(f[u][k] && !sz[f[u][k]]) u = f[u][k];
    return f[u][0]; 
}   

void marisa(){
    cin >> n >> q >> m;
    for(int i = 1, u, v, w; i < n; i ++ ){
        cin >> u >> v >> w;
        e[u].emplace_back(v, w);
        e[v].emplace_back(u, w);
    }
    int rt = 0; // 选取一个关键点的作为根节点
    for(int i = 1; i <= m; i ++ ){
        cin >> rt;
        c[rt] = 1;
    }

    dfs(rt, 0);
    
    int sum = 0; // 包含所有关键点最小连通块两倍边权和
    for(int u = 1; u <= n; u ++ ){
        for(const auto& [v, w] : e[u]){
            if(sz[u] && sz[v]) sum += w;
        }
    }

    for(int i = 1, s, t, u, v; i <= q; i ++ ){
        cin >> s >> t, u = get_nc(s), v = get_nc(t);
        int ans = sum - get_dist(u, v); // s -> u -> v -> t
        ans += get_dist(s, u) + get_dist(v, t);
        cout << ans << "\n";
    }
}

int main(){
    ios;

    int T = 1; // cin >> T;
    while(T -- ) marisa();

    return 0;
}

L3-3 东风夜放花千树

题意简述

平面直角坐标系有 $n$ 个不重叠的矩形和一个 $m$ 点的凸边形，求凸边形从时间 $t_1$ 至 $t_2$ 以 $v$ 单位/分钟沿着 $s \rightarrow e$ 直线移动过程种 覆盖到的矩形面积总和。

解题思路（计算几何、凸包、半平面交）

本题思路简单，但所涉及知识点较难。魔法阵是一个凸边形，平移所经过的整个区域也是凸边形，问题在于如何求这个经过区域构成的凸边形。

可以将魔法阵平移后的 $m$ 个点和起始魔法阵的 $m$ 个点加到一起，然后求一下这 $2 \times m$ 个点的凸包，从而求得整个经过区域构成的凸边形。

我们知道了魔法阵整个经过的区域，然后枚举每个矩形（矩形都是不重叠的）求与其半平面交，累加每个半平面交面积即可。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

namespace Geo { // 计算几何二维模板，仅保留凸包、半平面交部分
    template<typename T>
    class Point;    // 点

    template<typename T>
    class Line;     // 线

    template<typename T>
    class Polygon;  // 多边形

    template<typename T>
    using Vector = Point<T>;     // 向量

    const double eps = 1e-8;     // 误差 

    // 判断数值正负
    template<typename T>
    int sgn(T x){ 
        if(abs(x) < eps) return 0; // 等于0
        return x > 0 ? 1 : -1; // 1: 正数，2: 负数
    }

    // 向量的模（长度，需要 operator*）
    template<typename T>
    double len(const Vector<T>& A){ return (double)sqrt(A * A); }

    // 两个向量的叉积（cross，需要 operator^）
    // \vec a \cdot \vec b = |a||b|\sin{\theata}
    // \theata: \vec a 旋转到 \vec b 经过的夹角
    template<typename T>
    T cross(const Vector<T>& A, const Vector<T>& B){ return A ^ B; }

    // 单位向量
    template<typename T>
    Vector<T> unit_vector(const Vector<T>& A){ return A / len(A); }

    // 两个向量构成平行四边形有向面积，输入三点ABC
    // 得到向量 AB 和 AC，A为公共点，B、C点需逆时针输入
    template<typename T>
    T area_parallelogram(const Point<T>& A, const Point<T>& B, const Point<T>& C){
        return cross(B - A, C - A);
    }

    // 两条直线的交点（要先判断两直线是否相交）
    template<typename T>
    Point<T> cross_point_line_line(const Line<T>& v1, const Line<T>& v2){
        auto a = v1.s, b = v1.t; // 直线 a - b
        auto c = v2.s, d = v2.t; // 直线 c - d
        double s1 = cross(b - a, c - a);
        double s2 = cross(b - a, d - a);
        return Point<T>(c.x * s2 - d.x * s1, c.y * s2 - d.y * s1) / (s2 - s1);
    }

    // 凸多边形：是指所有内角大小都在 [0, 180] 范围内的简单多边形
    // 凸包: 在平面上能包含所有给定点的最小凸多边形叫做凸包
    template<typename T>
    Polygon<T> convex_hull(vector<Point<T>> p){
        // Andrew 法
        // 先对所有点排序，求上下凸包 (查每个边相较于上一条边的拐弯方向)
        // 然后合并，最后得到的点为逆时针顺序
        Polygon<T> ch;
        if(p.size() <= 2){
            for(auto& x : p) ch.push_back(x);
            return ch;
        }
        int n = p.size();
        n = unique(p.begin(), p.end()) - p.begin(); // 去除重复的点
        ch.resize(2 * n);
        sort(p.begin(), p.end()); // operator<
        int tp = 0;
        // 求下凸包，若 p[i] 是右拐弯的，这个点不在凸包上，往回退
        for(int i = 0; i < n; i ++ ){
            while(tp > 1 && sgn(cross(ch[tp - 1] - ch[tp - 2], p[i] - ch[tp - 1])) <= 0)
                tp -- ;
            ch[tp ++ ] = p[i];
        }
        // 求上凸包
        for(int i = n - 1, j = tp; i >= 0; i -- ){
            while(tp > j && sgn(cross(ch[tp - 1] - ch[tp - 2], p[i] - ch[tp - 1])) <= 0)
                tp -- ;
            ch[tp ++ ] = p[i];
        }
        ch.resize(tp - 1);
        return ch;
    }

    // 判断 b 和 c 的交点是否在 a 的右侧（用于求解半平面交）
    template<typename T> 
    inline bool on_right(const Line<T>& a, const Line<T>& b, const Line<T>& c){
        auto o = cross_point_line_line(b, c); // 求b和c的交点o
        return sgn(area_parallelogram(a.s, a.t, o)) < 0;
    }

    // 半平面交
    template<typename T>
    double half_plane_intersection(vector<Line<T>>& v){
        // 对向量进行极角排序
        sort(v.begin(), v.end(), [&](const Line<T>& a, const Line<T>& b){
            if(sgn(a.polar_angle() - b.polar_angle()) == 0){  // 角度相同
                return area_parallelogram(a.s, a.t, b.t) < 0; // 面积为负，更左 
            }
            return a.polar_angle() < b.polar_angle();
        }); 
        // 自定义去重
        v.erase(unique(v.begin(), v.end(), [&](const Line<T>& a, const Line<T>& b){
            return sgn(a.polar_angle() - b.polar_angle()) == 0;
        }), v.end()); // 角度相同的直线只考虑最靠左的一条,靠近左边的是有效的
        int n = v.size();
        deque<int> deq; // 双端队列，存储边的下标
        for(int i = 0; i < n; i ++ ){
            // 删除队尾没有贡献的线段
            while(deq.size() > 1 && on_right(v[i], v[deq[deq.size() - 2]], v[deq.back()])){
                deq.pop_back();
            }
            // 删除队头没有贡献的线段
            while(deq.size() > 1 && on_right(v[i], v[deq[0]], v[deq[1]])){
                deq.pop_front();
            }
            deq.push_back(i); // 如果可以构成轮廓，将当前直线加入队列
        }
        // 队头、队尾相互更新，还要确保队尾和队头都是有效的
        while(deq.size() > 1 && on_right(v[deq[0]], v[deq[deq.size() - 2]], v[deq.back()])){
            deq.pop_back();
        }
        while(deq.size() > 1 && on_right(v[deq.back()], v[deq[0]], v[deq[1]])){
            deq.pop_front();
        }
        deq.push_back(deq.front()); // 轮廓闭合
        Polygon<T> res; // 轮廓所有顶点，存到一个多边形中（凸包）
        for(int i = 0; i < deq.size() - 1; i ++ ){
            res.push_back(cross_point_line_line(v[deq[i]], v[deq[i + 1]]));
        }
        return res.area(); // 求半平面交的面积，即这个凸包的面积
    }

    // 1. 点与向量: Point(x, y) 为点，Vector(x, y) 为向量
    template<typename T>
    class Point {
    public:
        T x, y; 
        Point(T _x = 0, T _y = 0): x(_x), y(_y) {}

        Point operator- (const Point& B) const { return Point(x - B.x, y - B.y); }
        Point operator+ (const Point& B) const { return Point(x + B.x, y + B.y); }
        T operator^ (const Point<T>& B) const { return x * B.y - y * B.x; }
        T operator* (const Point<T>& B) const { return x * B.x + y * B.y; }
        Point operator* (const double& b) const { return Point(x * b, y * b); }
        Point operator/ (const double& b) const { return Point(x / b, y / b); }
        bool operator< (const Point& B) const { return x < B.x || (x == B.x && y < B.y); }
        bool operator> (const Point& B) const { return x > B.x || (x == B.x && y > B.y); }
        bool operator== (const Point& B) const { return !sgn(x - B.x) && !sgn(y - B.y); }
        bool operator!= (const Point& B) const { return sgn(x - B.x) || sgn(y - B.y); }
    };

    // 2. 直线与线段: Line 直线，Segment 线段
    template<typename T>
    class Line {
    public:
        Point<T> s, t; // 线上两点，s - t
        Line() {} 
        Line(const Point<T>& p1, const Point<T>& p2): s(p1), t(p2) {}

        // 直线的极角，用于半平面交
        double polar_angle() const { return atan2(t.y - s.y, t.x - s.x); }
    };

    // 3. 多边形
    template<typename T>
    class Polygon: public vector<Point<T>> { // 继承自std::vector
    public:
        Polygon() {}
        Polygon(int n): vector<Point<T>>(n) {}

        // 凸多边形面积
        double area() const {
            double ans = 0;
            int n = this->size();
            if(n < 3) return 0.0; // 重要，否则可能出现nan
            for(int i = 0; i < n; i ++ ){ // 外面的面积抵消
                ans += cross((*this)[i], (*this)[(i + 1) % n]);
            }
            return abs(ans) / 2.0;
        }
    };
}

using namespace Geo;

void marisa(){
    int n; cin >> n;
    vector<Polygon<double>> rects; // 每个房屋

    auto get_rect = [&](int x1, int y1, int x2, int y2){ // 获取矩形
        Polygon<double> rect;
        int mnx = min(x1, x2), mxx = max(x1, x2);
        int mny = min(y1, y2), mxy = max(y1, y2);
        rect.push_back(Point<double>(mnx, mny)); // 逆时针放入矩形四个点
        rect.push_back(Point<double>(mxx, mny));
        rect.push_back(Point<double>(mxx, mxy));
        rect.push_back(Point<double>(mnx, mxy));
        return rect;
    };

    for(int i = 0, x1, y1, x2, y2; i < n; i ++ ){ // 读入每个矩形
        cin >> x1 >> y1 >> x2 >> y2;
        rects.push_back(get_rect(x1, y1, x2, y2));
    }

    int m; cin >> m;
    vector<Point<double>> cloud; // 存储魔法阵的 m 个顶点
    for(int i = 0, x, y; i < m; i ++ ){
        cin >> x >> y;
        cloud.push_back(Point<double>(x, y));
    }

    auto get_time = [&](const string& s){ // 获取分钟
        int h = (s[0] - '0') * 10 + (s[1] - '0');
        int m = (s[3] - '0') * 10 + (s[4] - '0');
        return h * 60 + m;
    };

    Point<double> st, ed; // 起点和终点
    cin >> st.x >> st.y >> ed.x >> ed.y;
    int speed; string t1, t2; // 速度，起止时间 
    cin >> speed >> t1 >> t2;
    double d = speed * (get_time(t2) - get_time(t1)); // 移动的距离
    for(int i = 0; i < m; i ++ ){
        Point<double> moved = cloud[i] + unit_vector(ed - st) * d; // 单位向量 * 移动距离   
        cloud.push_back(moved); // 存入每个平移后的点
    }    
    cloud = convex_hull(cloud); // 求凸包得到整个魔法阵经过部分的凸边形

    // 求魔法阵经过部分和每个矩形的半平面交，累加答案
    double ans = 0;
    int cnt = cloud.size(); // 魔法阵经过区域的凸包点个数
    vector<Line<double>> lines; 
    for(const auto& rect : rects){
        lines.clear();
        for(int i = 0; i < cnt; i ++ ){
            lines.push_back(Line<double>(cloud[i], cloud[(i + 1) % cnt]));
        }
        for(int i = 0; i < 4; i ++ ){
            lines.push_back(Line<double>(rect[i], rect[(i + 1) % 4]));
        }
        ans += half_plane_intersection(lines); // 累加每个半平面交
    }
    printf("%.1lf\n", ans);
}

int main(){
    ios;

    int T = 1; cin >> T;
    while(T -- ) marisa();

    return 0;
}

咏唱光芒 > 扬大校内选拔赛

#C++ #算法 #算法竞赛 #Luogu #YAC #选拔赛 #GPLT #团体天梯赛

2025 扬州大学 GPLT 团体天梯赛校内选拔赛题解

https://marisamagic.github.io/2025/03/01/2025YZUGPLT/

作者

MarisaMagic

发布于

2025年3月1日

许可协议

2025 扬州大学 ACM-ICPC 选拔赛题解上一篇

2025 YAC Round 4 题解下一篇

2025 扬州大学 GPLT 团体天梯赛校内选拔赛题解

题意简述

解题思路 （语法）

题意简述

解题思路 （语法）

题意简述

解题思路 （数学）

题意简述

解题思路 （模拟）

题意简述

解题思路 （模拟，数学，贪心）

题意简述

解题思路 （模拟，集合）

题意简述

解题思路 1 （模拟，字符串基础）

解题思路 2 （模拟，std::string）

题意简述

解题思路 （模拟）

题意简述

解题思路 （动态规划）

题意简述

解题思路 （队列、模拟）

题意简述

解题思路 （并查集）

题意简述

解题思路 （dfs，爆搜）

题意简述

解题思路 （最短路，dijkstra）

题意简述

解题思路 （倍增，LCA）

题意简述

解题思路 （计算几何、凸包、半平面交）

解题思路（语法）

解题思路（语法）

解题思路（数学）

解题思路（模拟）

解题思路（模拟，数学，贪心）

解题思路（模拟，集合）

解题思路（模拟）

解题思路（动态规划）

解题思路（队列、模拟）

解题思路（并查集）

解题思路（dfs，爆搜）

解题思路（最短路，dijkstra）

解题思路（倍增，LCA）

解题思路（计算几何、凸包、半平面交）