2024 扬州大学与南通大学 GPLT 联谊选拔赛题解

文章大图来源: pixiv_id=70531218

L1-1 抓兔子，捣年糕

题意描述

给定一个连续字符串，只包含小写英文字母，找出字符串中最小的字符。「2024 扬大GPLT选拔赛」L1-1 抓兔子，捣年糕

解题方法

很简单的签到题，直接枚举每个字符取最小字符即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;

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

int main(){
    ios;

    string s; cin >> s;
    char res = s[0];
    for(auto &ch : s) res = min(res, ch);
    cout << res << '\n';

    return 0;
}

L1-2 期初考试

题意描述

给定 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n，求出这 nn 个整数的平均值。（结果保留 44 位小数） 「2024 扬大GPLT选拔赛」L1-2 期初考试

解题方法

非常简单的签到题，求出总和最后除以数量 nn 即可。注意输出结果保留 44 位小数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;

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

int main(){
    ios;

    double sum = 0;
    int n; cin >> n;
    for(int i = 1, x; i <= n; i ++ ) cin >> x, sum += x;
    printf("%.4lf\n", sum / n);

    return 0;
}

L1-3 慧音老师的银杏叶

题意描述

给定 nn 个学生的三门课成绩，第 ii 个学生学号为 ii。先按照成绩总分从高到低排序，若总分一样再按照第一门课从高到低排序，若第一门课一样则按照学号从小到大排序。最终输出前 55 名学生的学号和总分。「2024 扬大GPLT选拔赛」L1-3 慧音老师的银杏叶

解题方法 结构体排序

本题考察结构体排序，我们可以用结构体存储每个学生的第一门课分数、三门课总分以及学号，使用 sort\text{sort} 结合 lambda\text{lambda} 表达式进行多关键字排序，当然也可以另写一个 cmp\text{cmp} 函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 310;

int n;
struct node{int a, sum, id;}p[N];

int main(){
    ios;

    cin >> n;
    for(int i = 1, a, b, c; i <= n; i ++ ){
        cin >> a >> b >> c;
        p[i] = node{a, a + b + c, i};
    }

    sort(p + 1, p + n + 1, [](node &x, node &y){ // lambda
        if(x.sum != y.sum) return x.sum > y.sum;
        if(x.a != y.a) return x.a > y.a;
        return x.id < y.id;
    });

    for(int i = 1; i <= 5; i ++ ){
        auto [a, sum, id] = p[i];
        cout << id << ' ' << sum << '\n';
    }

    return 0;
}

L1-4 反射Master

题意描述

一个 nn 等分的圆，圆上有 nn 个等分点 a0,a1,a2,…,an−1a_0, a_1, a_2, \ldots, a_{n-1}。从 a0a_0 向 apa_p 射出一条光线，求经过 kk 次反射后，最终光线射到圆上的点 ata_t。「2024 扬大GPLT选拔赛」L1-4 反射Master

解题方法 数学

由基本的对称性质，经过第一次反射后，到达了 apa_p；经过第二次反射后，到达了 a2×pa_{2\times p} … 此时可以发现，光线所到点移动的步长就是 pp，而需要反射 kk 次意味着需要经过 kk 次，移动的总长度就是 k×pk \times p。由于是在一个 nn 等分的圆上移动，故最终的答案就是 k×pk \times p mod\text{mod} nn 。（注意需要开 long long\text{long long}）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;

int main(){
    ios;

    ll n, p, k; cin >> n >> p >> k;
    cout << (k * p) % n << "\n";

    return 0;
}

L1-5 幻想乡程序设计大赛

题意描述

给定一个起始年份 yly_l， nn 个年份 a1,a2,…,ana_1, a_2, \ldots , a_n，从 yly_l 年开始，第 a1,a2,…,ana_1, a_2, \ldots , a_n 年没有举办比赛，其他年份每年举办一次。问 yry_r 年是自 yly_l 年开始第几次举办比赛。（yly_l 年记为第一次，保证 yl≤yry_l \le y_r，yl<aiy_l < a_i） 「2024 扬大GPLT选拔赛」L1-5 幻想乡程序设计大赛

解法一 枚举

从 yly_l 年开始到 yry_r 年共有 sum=yr−yl+1sum = y_r - y_l + 1 年。由于所给年份 aia_i 是升序的，故我们可以顺序枚举统计小于 yry_r 的没有举办比赛的年份 aia_i，最后用 sumsum 减去统计的年份数量即为答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;

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

int main(){
    ios;

    int T; cin >> T;
    while(T -- ){
        int l, r, n;
        cin >> l >> n;
        vector<int> a(n + 1);
        for(int i = 1; i <= n; i ++ ) cin >> a[i];
        cin >> r;

        int cnt = 0;
        for(int i = 1; i <= n && a[i] < r; i ++ , cnt ++ );
        cout << r - l + 1 - cnt << '\n';
    }

    return 0;
}

解法二 二分

由于 aia_i 原本就是升序的，我们可以考虑用二分查找找到 aia_i 中第一个大于 yry_r 的年份 aka_k，而 ak−1a_{k-1} 就是最后一个小于 yry_r 的年份，故比 yry_r 小的年份数量就是 k−1k - 1。最后用年份总数 sum−(k−1)sum - (k-1) 即为答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;

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

int main(){
    ios;

    int T; cin >> T;
    while(T -- ){
        int l, r, n;
        cin >> l >> n;
        vector<int> a(n + 1);
        for(int i = 1; i <= n; i ++ ) cin >> a[i];
        cin >> r;

        int k = upper_bound(a.begin() + 1, a.end(), r) - a.begin();
        cout << r - l + 1 - (k - 1) << '\n';
    }

    return 0;
}

L1-6 惊人的秘密

题意描述

给定一个长度为 nn 的字符串，字符出中只包含 ABCD\text{ABCD}。现在可以修改一些字符，求使得字符串中只包含 BC\text{BC} 且相邻字符都不相同的最少修改次数。「2024 扬大GPLT选拔赛」L1-6 惊人的秘密

解题方法 思维

字符串只包含 BC\text{BC} 且相邻字符都不相同显然只有两种可能。要么是 BCBCBC...\text{BCBCBC...} 的形式，也就是奇数位为 B\text{B}，偶数位为 C\text{C}；要么是 CBCBCB...\text{CBCBCB...} 的形式，也就是奇数位为 C\text{C}，偶数位为 B\text{B}。故只需要统计这两种情况下，枚举统计每一位是否需要修改，最终取两种情况下的较小操作次数即为答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;

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

int main(){
    ios;

    int n; cin >> n;
    string s; cin >> s;
    s = " " + s;
    int cnt1 = 0, cnt2 = 0;
    for(int i = 1; i <= n; i ++ ){
        char c = s[i];
        if(i & 1){
            if(c != 'B') cnt1 ++ ;
            if(c != 'C') cnt2 ++ ;
        }else{
            if(c != 'C') cnt1 ++ ;
            if(c != 'B') cnt2 ++ ;
        }
    }
    cout << min(cnt1, cnt2) << '\n';

    return 0;
}

L1-7 贤者的变量替换

题意描述

给定 nn 个变量，每个变量有一个名称和值。给定 mm 个句子，将每个句子中的 {变量名称} 替换成对应的值。「2024 扬大GPLT选拔赛」L1-7 贤者的变量替换

解题方法 哈希映射 + 字符串操作

由于输入的字符串是带空格的，所以需要在读入字符串时使用 getline(cin, s);

如果在使用 getline(cin, s) 之前使用了 cin ，会剩余一个 \n 在缓冲区中，而此时直接使用 getline(cin, s) 则会导致读入了一个 \n。故在使用 getline(cin, s) 之前，可以使用 cin.ignore() 清除这个换行符 \n 。

对于每个变量，我们可以用 unordered_map 去存储，为了方便替换，我们可以在存储时就将 {} 加到名称中。数据较小，故我们可以枚举每个变量，用 find() 找出变量出现的位置，将其 replace() 掉即可（如果不知道 replace()，也可以进行字符串切割）。但是需要注意到字符串中可能多次出现一个变量，所以枚举变量时需要 while 循环找出所有的当前变量出现的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;

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

unordered_map<string, string> mp;
string s, x;
int n, m;

int main(){
    ios;

    cin >> n >> m;
    while(n -- ){
        cin >> s >> x;
        s = "{" + s + "}";
        mp[s] = x;
    }

    cin.ignore();
    while(m -- ){
        getline(cin, s);
        for(auto &[t, val] : mp){
            int pos = s.find(t), len = t.size();
            while(pos != -1){
                s = s.substr(0, pos) + val + s.substr(pos + len);
                pos = s.find(t);
            }
        }   
        cout << s << '\n';
    }

    return 0;
}

L1-8 上海蓬莱

题意描述

给定 nn 个区间 [li,ri][l_i, r_i]，表示在这个区间内有人浇花。求出最长的至少有一个人浇花的连续时间段长度 和 最长度无人浇花的连续时间段长度。「2024 扬大GPLT选拔赛」L1-8 上海蓬莱

解法一 区间合并

我们可以用区间合并的思维来解决这个问题。先将所有区间按照左端点从小到大排序，记录当前有人浇花区间的左端点 lastl\text{lastl} 和右端点 lastr\text{lastr}。

顺序枚举每个区间，如果区间左端点小于等于当前的 lastr\text{lastr}，则需要合并到前一个区间中，此时更新 lastr\text{lastr}；否则，我们更新最长有人浇花的连续时间段和最长无人浇花的连续时间段，随后将 lastl\text{lastl} 和 lastr\text{lastr} 更新为当前的区间即可。

注意循环结束后还有最后一个有人浇花的区间，所以需要再更新一次最长有人浇花的连续时间段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define fi first
#define se second
typedef pair<int, int> pii;

int main(){
    ios;

    int n; cin >> n;
    vector<pii> a(n + 1);
    for(int i = 1; i <= n; i ++ ) cin >> a[i].fi >> a[i].se;
    sort(a.begin() + 1, a.end());

    int res1 = 0, res2 = 0;
    int lst_l = a[1].fi, lst_r = a[1].se;
    for(int i = 2; i <= n; i ++ ){
        auto [l, r] = a[i];
        if(lst_r >= l) lst_r = max(lst_r, r); // 合并区间
        else{
            res1 = max(res1, lst_r - lst_l);
            res2 = max(res2, l - lst_r);
            lst_l = l, lst_r = r;
        }
    }
    res1 = max(res1, lst_r - lst_l); // 最后一个区间

    cout << res1 << ' ' << res2 << '\n';

    return 0;
}

解法二 差分

可以用差分来解决这个问题。但是要注意一个比较坑的点，题目中一个区间 [200,1000][200, 1000] 表示浇花的时间长度为 800800，而非 801801，因此，我们应将 [l,r−1][l, r - 1] 范围内都进行 +1+1，即 b[l]++,b[r]−−b[l] ++ , b[r] -- 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define fi first
#define se second
typedef pair<int, int> pii;
const int N = 1e6 + 10;

int b[N], n;

int main(){
    ios;

    cin >> n;
    int left = 1e9, right = 0; // 记录左右边界
    while(n -- ){
        int l, r; cin >> l >> r;
        left = min(left, l);
        right = max(right, r);
        b[l] ++ , b[r] -- ;
    }

    int res1 = 0, res2 = 0, len1 = 0, len2 = 0;
    for(int i = left; i < right; i ++ ){  // 注意范围
        b[i] += b[i - 1];   // 还原数组
        if(b[i] > 0) len1 ++ , len2 = 0;
        else len2 ++ , len1 = 0;
        res1 = max(res1, len1);
        res2 = max(res2, len2);
    }

    cout << res1 << ' ' << res2 << '\n';

    return 0;
}

L2-1 蕾米莉亚巡逻记

题意描述

给定一个长度为 nn 的数组 aa，求最长的区间内每个数字不重复出现的区间长度。「2024 扬大GPLT选拔赛」L2-1 蕾米莉亚巡逻记

解题方法 双指针

我们可以用双指针维护一个数字不重复出现的窗口。定义一个 unordered_map 记录每个数字出现的次数。

双指针遍历时，右指针 rr 先动，同时更新数字出现次数，若出现 mp[a[r]]mp[a[r]] 大于 11 时，此时需要将左指针 ll 向右移动，在移动的同时更新数字出现次数，直到 mp[a[r]]=1mp[a[r]] = 1 为止。每次双指针移动过后，更新最长区间长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;

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

unordered_map<int, int> mp; // 记录数字出现次数

int main(){
    ios;

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

    int res = 0;
    for(int l = 1, r = 1; r <= n; r ++ ){ // 双指针维护数字只出现一次的窗口
        mp[a[r]] ++ ;
        while(mp[a[r]] > 1) mp[a[l ++ ]] -- ; // a[l]次数-1，l向右移动
        res = max(res, r - l + 1); // 更新答案
    }

    cout << res << '\n';

    return 0;
}

L2-2 月光团子

题意描述

有 nn 次操作，操作分为两种：

1 l r：表示将价值为 l,l+1,…,rl, l + 1, \ldots , r 的团子依次放入栈中；

2 k：表示取出栈顶的前 kk 团子，计算这 kk 个团子的总价值并输出。

「2024 扬大GPLT选拔赛」L2-2 月光团子

解题方法 栈

根据题目 “宽度却恰好只可以容得下一个月光团子”，“每次从箱子中取团子 只能取走箱子最顶部的一个团子” 的条件，我们显然可以用 栈 来模拟两种操作。

如果在模拟过程中，每次放团子操作都一个一个放，需要进行 r−l+1r - l + 1 次入栈；每次取出团子操作，需要进行 kk 次出栈。这显然是会消耗大量时间的，因此我们需要优化存储数据的方式。

我们可以用二元组 (l,r)(l, r) 作为栈中存储的元素。

  • 对于放团子的操作，我们直接将二元组 (l,r)(l, r) 压入栈中；

  • 对于取团子的操作，我们可以观察此时栈顶的二元组长度 r−l+1r - l + 1 是否超过了当前所需团子数量 kk。

    如果超过了，用等比数列求和得出 getsum(r−k+1,r)\text{getsum}(r - k + 1, r) 累加答案，同时需要更新栈顶的右区间 rr 为 r−kr - k，所需数量 kk 置为 00；

    否则，求出栈顶二元组的等比数列求和 getsum(l,r)\text{getsum}(l, r) 累加答案，并且当前栈顶二元组直接出栈，所需数量 kk 减去区间长度。

    当所需数量 kk 减为 00 时，退出循环，输出答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;
const int N = 5e5 + 10;

int top;
struct node{ll l, r;}st[N];

ll get_sum(ll l, ll r){ return (r - l + 1) * (l + r) / 2; } 
ll get_len(ll l, ll r){ return r - l + 1; }

int main(){
    ios;

    int n; cin >> n;
    while(n -- ){
        int op; cin >> op;
        if(op == 1){
            int l, r; cin >> l >> r;
            st[ ++ top] = node{l, r};
        }else{
            ll k; cin >> k;
            ll res = 0;
            while(k > 0){
                auto [l, r] = st[top];
                if(k < get_len(l, r)){  // k不满栈顶团子的总数
                    res += get_sum(r - k + 1, r);
                    st[top].r -= k;     // 更新栈顶的 r
                    k = 0;
                }else{
                    res += get_sum(l, r);
                    k -= get_len(l, r); // 减去栈顶团子总数 
                    top -- ;            // 栈顶出栈
                }
            }
            cout << res << '\n';
        }
    }

    return 0;
}

L2-3 你存在的价值

题意描述

有 nn 个人，每个人有一个 aia_i 和一个价值 valival_i。如果有 aua_u xor\text{xor} av>max⁡(au,av)a_v > \max(a_u, a_v)，那么 uu 和 vv 之间相互认识（认识关系具有传递性）。求每个人所属连通块的总价值。「2024 扬大GPLT选拔赛」L2-3 你存在的价值

解题方法 并查集 + 位运算

我们可以用并查集来维护 nn 个点的连通性以及连通块的总价值。如果暴力枚举 aua_u 和 ava_v 是否满足题中所需条件来合并集合，显然会超时。

aa 的大小不超过 230−12^{30} - 1，我们可以考虑从二进制位入手。

  • 设 digit(num,k)\text{digit}(num, k) 为数字 numnum 第 kk 位二进制位的值。

  • 设 highbit(num)\text{highbit}(num) 为数字 numnum 的最高的非零位。

假定 max⁡(au,av)=au\max(a_u, a_v) = a_u 并且这对 (au,av)(a_u, a_v) 是满足条件的。将其分解为二进制。假设分解后结果如下：

au=101011a_u = 101011

av=000101a_v = 000101

我们此时可以答案猜测一下结论。ava_v 的最高位为 highbit(av)\text{highbit}(a_v)，当 aua_u 的第 highbit(av)\text{highbit}(a_v) 位为 00 时，才会使得 aua_u xor\text{xor} av>aua_v > a_u 。

也就是 digit(au,highbit(av))=0\text{digit}(a_u, \text{highbit}(a_v)) = 0，才有 aua_u xor\text{xor} av>aua_v > a_u。

接下来我们尝试用反证法来证明。

如果 digit(au,highbit(av))=1\text{digit}(a_u, \text{highbit}(a_v)) = 1，那么 aua_u xor\text{xor} ava_v 后第 highbit(av)\text{highbit}(a_v) 位就会变为 00，此时得到的结果显然是小于 aua_u 的。因此，digit(au,highbit(av))=1\text{digit}(a_u, \text{highbit}(a_v)) = 1 与 aua_u xor\text{xor} av>aua_v > a_u 互为充要条件。

所以，我们可以枚举二进制位 kk 作为 highbit\text{highbit}，令 mid=2k+1mid = 2^{k + 1}，找到所有第 kk 位为 00 的，并且值 大于等于 midmid 的所有的 aua_u；之后，找到所有 highbit\text{highbit} 为 kk 的，也就是第 kk 位为 11，并且值 小于 midmid 的所有的 ava_v。

对于每个二进制位 kk，找到的这些 aua_u 和 ava_v 都满足 digit(au,highbit(av))=0\text{digit}(a_u, \text{highbit}(a_v)) = 0，故需要将这些 aua_u 和 ava_v 全部合并。

二进制位全部枚举完后，最后依次输出每个人所属连通块的总价值。

（注意数据范围，连通块价值需要开 long long\text{long long}）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;
const int N = 1e5 + 10;

int fa[N], a[N], n;
ll s[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) fa[fx] = fy, s[fy] += s[fx];
}

int get_k(int x, int k){ return ((x >> k) & 1); }

int main(){
    ios;

    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    for(int i = 1; i <= n; i ++ ) fa[i] = i, cin >> s[i];

    for(int k = 29; k >= 0; k -- ){
        int mid = (1 << (k + 1));
        vector<int> v; // 存储 a[u] 和 a[v]
        vector<bool> flag(2, false); // flag[0] 记录是否有 a[u], flag[1] 是否有 a[v]
        
        for(int i = 1; i <= n; i ++ )
            if(!get_k(a[i], k) && a[i] >= mid)
                v.push_back(i), flag[0] = true;

        for(int i = 1; i <= n; i ++ )
            if(get_k(a[i], k) && a[i] < mid)
                v.push_back(i), flag[1] = true;

        if(flag[0] && flag[1]){
            int x = v[0];
            for(auto &y : v) merge(x, y); // 合并
        }
    }

    for(int i = 1; i <= n; i ++ ) cout << s[find(i)] << '\n';

    return 0;
}

L2-4 梦想天生

题意描述

给定一个大小为 n×mn \times m 的地图，只包含小写英文字符。地图为八连通，移动的路径只能为 m→x→t→s→m→x→…\text{m} \rightarrow \text{x} \rightarrow \text{t} \rightarrow \text{s} \rightarrow \text{m} \rightarrow \text{x} \rightarrow \ldots 的形式，也就是按照循环字符串 mxts 的顺序。判断能否从 (1,1)(1, 1) 移动到 (n,m)(n, m) 。「2024 扬大GPLT选拔赛」L2-4 梦想天生

解题思路 BFS

比较典型的 BFS\text{BFS} 模板题。我们可以用一个 unordered_map 记录每个字符的下一个字符，比如 ′m′'\text{m}' 后面必须是 ′x′'\text{x}'，即 mp[′m′]mp['\text{m}'] == ′x′'\text{x}' 。其余的部分就是基本的广度优先搜索模板了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define MP make_pair
typedef pair<int, int> pii;
const int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
const int dy[8] = {0, 0, 1, -1, 1, -1, 1, -1};
const int N = 110;

unordered_map<char, char> mp = {
    {'m', 'x'}, {'x', 't'}, {'t', 's'}, {'s', 'm'}
};

int n, m;
char g[N][N];
bool vis[N][N];

bool bfs(){
    memset(vis, 0, sizeof vis);
    queue<pii> q;
    q.push(MP(1, 1));
    vis[1][1] = true;

    while(q.size()){
        auto [x, y] = q.front();
        q.pop();

        if(x == n && y == m) return true;

        for(int k = 0; k < 8; k ++ ){
            int nx = x + dx[k], ny = y + dy[k];
            if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
            if(vis[nx][ny] || g[nx][ny] != mp[g[x][y]]) continue;
            
            q.push(MP(nx, ny));
            vis[nx][ny] = true;
        }
    }

    return false;
}

int main(){
    ios;

    int T; cin >> T;
    while(T -- ){
        cin >> n >> m;
        for(int i = 1; i <= n; i ++ ) cin >> (g[i] + 1);
        cout << (bfs() ? "Yes" : "No") << '\n';
    }

    return 0;
}

L3-1 风神少女的祝福

题意描述

给定一个 nn 个点，mm 条有向边的 DAG\text{DAG}。每次可以走到一个点当且仅当能够到达这个点的所有点都已经被走过（ 拓扑排序 ）。每走到一个 比之前走过的所有点编号都大 的点，有一定概率得到祝福，也有一定概率收到攻击。

求解两个问题：

  • 最优情况下（每次都得到祝福），采取最优行走策略得到的祝福次数。

  • 最坏情况下（每次都收到攻击），采取最优行走策略收到的攻击次数。

「2024 扬大GPLT选拔赛」L3-1 风神少女的祝福

解题方法 拓扑排序 + 贪心

对于第一个问题，显然我们只需要采取每次都选取 编号最小的入度为 00 的点扩展的贪心策略即可。我们可以用 小根堆 替换队列来进行拓扑排序，即 priority_queue<int, vector<int>, greater<int> >。每次出队的时候，更新走过的最大点并记录答案即可。

对于第二个问题，我们可以先尝试采取每次都选取 编号最大的入度为 00 的点扩展的贪心策略，也就是直接用大根堆进行拓扑排序。然而，这是错误的。

例如下面的示例：

如果直接按照 每次选取最大的点扩展，那么我们会得到一个行走策略为：

2→3→1→42 \rightarrow 3 \rightarrow 1 \rightarrow 4

此时的答案为： 33 。

然而，我们完全可以得到一个更优的策略：

2→1→4→32 \rightarrow 1 \rightarrow 4 \rightarrow 3

此时的答案为： 22 。

我们可以假设当前未到达的可达点为 a1,a2,…,aka_1, a_2, \ldots , a_k，先前走过的最大点为 mxmx，那么，对于 ai<mxa_i < mx 的点，我们可以优先走这些点，不受到任何一次攻击。

上面走到最后，如果剩下的全是 >mx> mx 的点，我们此时再选择这些点中最大的点进行扩展。这样可以减少一些攻击次数。

我们用大根堆来实现整体的拓扑排序，同时定义一个备选队列来存储当前的编号大于先前走过的最大点的点。具体的实现过程见代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 5e5 + 10;

int n, m;
int h[N], e[N], ne[N], ind[N], tmp[N], idx;

void add(int a, int b){
    e[ ++ idx] = b, ne[idx] = h[a], h[a] = idx;
    ind[b] ++ ;
}

// 最优情况下获得尽可能多的祝福次数
int topo1(){
    int mx = 0, res = 0;
    priority_queue<int, vector<int>, greater<int> > q; // 小根堆
    for(int i = 1; i <= n; i ++ ) if(!ind[i]) q.push(i);

    while(q.size()){
        int u = q.top();
        q.pop();

        if(u > mx){
            mx = u;  // 更新先前走过的最大的点
            res ++ ;
        }

        for(int i = h[u]; i; i = ne[i]){
            int v = e[i];
            if(!( -- ind[v])) q.push(v);
        }
    }

    return res;
}

// 最坏情况下获得尽可能少的攻击次数
int topo2(){
    int mx = 0, res = 0, cnt = 0;
    priority_queue<int> q; // 大根堆 获取可达的最大的点扩展
    queue<int> wait;       // 存储当前可达的大于先前最大点的点
    for(int i = 1; i <= n; i ++ ) if(!ind[i]) q.push(i);

    while(cnt < n){
        while(q.size()){
            int u = q.top();
            q.pop();

            cnt ++ ;    // 统计走到的点的个数
            if(u > mx){  
                mx = u; // 更新
                res ++ ;
            }

            for(int i = h[u]; i; i = ne[i]){
                int v = e[i];
                if(!( -- ind[v])){
                    if(v > mx) wait.push(v); // 如果大于先前最大点 放入备选中
                    else q.push(v);  // 否则，放入优先队列，先扩展（贪心）
                }
            }
        }

        while(wait.size()){  // 优先队列没有可扩展的了，再选备选队列中的
            q.push(wait.front());
            wait.pop();  
        }
    }

    return res;
}

int main(){
    ios;

    cin >> n >> m;
    while(m -- ){
        int u, v; cin >> u >> v;
        add(u, v);
    }

    // task 1
    memcpy(tmp, ind, sizeof ind);
    cout << topo1() << "\n";

    // task 2
    memcpy(ind, tmp, sizeof tmp);
    cout << topo2() << "\n";

    return 0;
}

L3-2 七曜魔法使

题意描述

给定 nn 个左部点和 mm 个右部点，每次可以取走一对点（一个是左部点、一个是右部点）当且仅当两个点的权值满足 gcd⁡(ai,bj)>1\gcd(a_i, b_j) > 1。求最多可以取走多少对点。「2024 扬大GPLT选拔赛」L3-2 七曜魔法使

解题方法 最大流 + 质因数分解

很显然这是一个二分图。初始的想法是，两两枚举左部点和右部点，判断是否满足 gcd⁡(ai,bj)>1\gcd(a_i, b_j) > 1 建边，然后跑一下二分图最大匹配。虽然建边理论上不会超时，但是建完边后，边的个数 kk 最多会有 500×500500 \times 500 条，而二分图最大匹配的时间复杂度为 O(nk)O(nk)，所以这样的图建模方式跑二分图最大匹配大概率是会超时的。（也可以用网络流建模求解二分图最大匹配，但还是会超时）

可以发现，两个数的 gcd⁡\gcd 大于 11，意味着两个数至少有一个公共质因子。我们可以根据这个性质来进行建模。

我们可以先筛一下 10710^7 范围以内的质数，然后对每个 aia_i 和 bib_i 进行质因数分解（或者直接试除法），将所有出现的质因数看作是图中的一个点。对于每个 aia_i，将其向自己的质因数都连一条容量为 11 的边；对于每个 bib_i，将自己的质因数向自己连一条容量为 11 的边。在进行此部分连边时，我们还需要更新一下用到的质数个数，来更新汇点。

质因数分解部分连边结束后，再从源点向所有左部点连一条容量为 11 的边，从所有右部点向汇点连一条容量为 11 的边。最后跑一下最大流算法即可得到答案。

最终图中的点编号如下为：

  • 源点：00

  • 左部点：1∼n1 \sim n

  • 右部点：n+1∼n+mn + 1 \sim n + m

  • 中间的质因数：n+m+1∼n+m+cntn + m + 1 \sim n + m + cnt

  • 汇点：n+m+cnt+1n + m + cnt + 1

其中 cntcnt 为使用到的质因数个数。

题解中采用的是 dinic\text{dinic} 算法，加了当前弧优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 1e5 + 10, M = 2e6 + 10, K = 1e7 + 2, inf = 0x3f3f3f3f;

int n, m, src, des;
int h[N], e[M], ne[M], w[M], idx;

void add(int a, int b, int c){
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
    e[idx] = a, ne[idx] = h[b], w[idx] = 0, h[b] = idx ++ ;
}

// dinic 最大流
int d[N], now[M]; // 当前弧优化

bool bfs(){
    memset(d, -1, sizeof d);
    queue<int> q;
    q.push(src);
    d[src] = 0, now[src] = h[src];

    while(q.size()){
        int u = q.front();
        q.pop();

        for(int i = h[u]; ~i; i = ne[i]){
            int v = e[i], c = w[i];
            if(!c || ~d[v]) continue;

            q.push(v);
            d[v] = d[u] + 1, now[v] = h[v];

            if(v == des) return true;
        }
    }

    return false;
}

int dfs(int u, int flow){
    if(u == des) return flow;
    int used = 0;
    for(int i = now[u]; ~i && used < flow; i = ne[i]){
        now[u] = i;
        int v = e[i], c = w[i];
        if(c && d[v] == d[u] + 1){
            int f = dfs(v, min(c, flow - used));
            w[i] -= f, w[i ^ 1] += f;
            used += f;
        }
    }
    return used;
}

int dinic(){
    int res = 0;
    while(bfs()) res += dfs(src, inf);
    return res;
}

// 线性筛质数
int prime[K], cnt;
bool st[K];

void work(int n){
    st[1] = true;
    for(int i = 2; i <= n; i ++ ){
        if(!st[i]) prime[ ++ cnt] = i;
        for(int j = 1; prime[j] <= n / i; j ++ ){
            st[i * prime[j]] = true;
            if(i % prime[j] == 0) break;
        }
    }
}

// 质因数分解 建边
// 左部点连质因数
void add_a(int x, int u){
    for(int i = 1; i <= cnt && prime[i] <= x; i ++ ){
        if(x % prime[i] == 0){
            add(u, n + m + i, 1);
            des = max(des, n + m + i);
            while(x % prime[i] == 0) x /= prime[i];
        }
    }
}
// 右部点连质因数
void add_b(int x, int u){
    for(int i = 1; i <= cnt && prime[i] <= x; i ++ ){
        if(x % prime[i] == 0){
            add(n + m + i, u, 1);
            des = max(des, n + m + i);
            while(x % prime[i] == 0) x /= prime[i];
        }
    }
}

int main(){
    ios;

    work(K - 1);

    int T; cin >> T;
    while(T -- ){
        src = des = 0;
        memset(h, -1, sizeof h), idx = 0;
        cin >> n >> m;
        for(int i = 1, x; i <= n; i ++ ) cin >> x, add_a(x, i); 
        for(int i = 1, x; i <= m; i ++ ) cin >> x, add_b(x, n + i); 
        des ++ ;
        for(int i = 1; i <= n; i ++ ) add(src, i, 1);
        for(int i = 1; i <= m; i ++ ) add(n + i, des, 1);

        cout << dinic() << '\n';
    }

    return 0;
}

L3-3 信仰是为了虚幻之人

题意描述

一棵树，每个点有一个颜色和权值。操作有包括：求树上两点之间唯一路径上颜色为 cc 的点权之和或最大值，修改 xx 点的颜色或权值。「2024 扬大GPLT选拔赛」L3-3 信仰是为了虚幻之人

解题方法 树链剖分 + 动态开点线段树

对于这样的树上询问和区间修改问题，我们一般都会用树链剖分来解决。

由于在询问的时候，需要知道 留宿过的 地区的区间最值/区间和，因此，我们需要对每个宗教都开一个线段树，即每个宗教都有一个线段树的根。由于空间的限制，我们需要采用 动态开点线段树 。

对于修改宗教的操作，我们需要先对 xx 点原先宗教的线段树上将这个点清除，然后转移到新宗教的线段树上。其他大部分地方…也就和树链剖分板子差不多吧（逃

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 2e5 + 10, M = (N << 1), inf = 0x3f3f3f3f;

int n, q, root[N];
int h[N], e[M], ne[M], idx;
int w[N], cri[N]; // 评级 宗教
struct node{ int ls, rs, sum, mx; }tr[N << 3];
int son[N], dfn[N], fa[N], dep[N], siz[N], top[N], num, tot;

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

//--------------线段树----------------
void pushup(int &u){
    tr[u].sum = tr[tr[u].ls].sum + tr[tr[u].rs].sum;
    tr[u].mx = max(tr[tr[u].ls].mx, tr[tr[u].rs].mx);
}

void update(int &u, int l, int r, int k, int x){
    if(!u) u = ++ tot;
    if(l == r) {tr[u].sum = tr[u].mx = x; return;}
    int mid = l + r >> 1;
    if(k <= mid) update(tr[u].ls, l, mid, k, x);
    else update(tr[u].rs, mid + 1, r, k, x);
    pushup(u);
}

void remov(int &u, int l, int r, int k){
    if(!u) return;
    if(l == r) {tr[u].sum = tr[u].mx = 0; return;}
    int mid = l + r >> 1;
    if(k <= mid) remov(tr[u].ls, l, mid, k);
    else remov(tr[u].rs, mid + 1, r, k);
    pushup(u);
}

int query(int &u, int l, int r, int ql, int qr){
    if(!u) return 0;
    if(ql <= l && r <= qr) return tr[u].sum;
    int mid = l + r >> 1, res = 0;
    if(ql <= mid) res += query(tr[u].ls, l, mid, ql, qr);
    if(qr > mid) res += query(tr[u].rs, mid + 1, r, ql, qr);
    return res;
}

int querymx(int &u, int l, int r, int ql, int qr){
    if(!u) return -inf;
    if(ql <= l && r <= qr) return tr[u].mx;
    int mid = l + r >> 1, res = -inf;
    if(ql <= mid) res = max(res, querymx(tr[u].ls, l, mid, ql, qr));
    if(qr > mid) res = max(res, querymx(tr[u].rs, mid + 1, r, ql, qr));
    return res;
}

//-----------------------------------
// 询问路径权值和
int qRange(int x, int y){
    int ans = 0, res, c = cri[x];
    while(top[x] ^ top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        res = query(root[c], 1, n, dfn[top[x]], dfn[x]);
        ans += res;
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    res = query(root[c], 1, n, dfn[x], dfn[y]);
    ans += res;
    return ans;
}

// 询问路径最大值
int qMx(int x, int y){
    int ans = -inf, res, c = cri[x];
    while(top[x] ^ top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        res = querymx(root[c], 1, n, dfn[top[x]], dfn[x]);
        ans = max(ans, res);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    res = querymx(root[c], 1, n, dfn[x], dfn[y]);
    ans = max(ans, res);
    return ans;
}

void dfs1(int u, int f, int depth){
    dep[u] = depth, fa[u] = f, siz[u] = 1;
    int mxson = -1;
    for(int i = h[u]; ~i; i = ne[i]){
        int v = e[i];
        if(v == f) continue;
        dfs1(v, u, depth + 1);
        siz[u] += siz[v];
        if(siz[v] > mxson) son[u] = v, mxson = siz[v];
    }
}

void dfs2(int u, int topf){
    dfn[u] = ++ num, top[u] = topf;
    if(!son[u]) return;
    dfs2(son[u], topf);
    for(int i = h[u]; ~i; i = ne[i]){
        int v = e[i];
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    } 
}

int main(){
    ios;

    memset(h, -1, sizeof h);
    cin >> n >> q;
    for(int i = 1; i <= n; i ++ ) cin >> w[i] >> cri[i];
    for(int i = 1, u, v; i < n; i ++ ) cin >> u >> v, add(u, v), add(v, u);

    dfs1(1, -1, 1);
    dfs2(1, 1);

    // 每个宗教开一个线段树
    for(int i = 1; i <= n; i ++ ) update(root[cri[i]], 1, n, dfn[i], w[i]);
    while(q -- ){
        string s; cin >> s;
        if(s == "CC"){
            int x, c; cin >> x >> c;
            remov(root[cri[x]], 1, n, dfn[x]);    // 清除
            update(root[c], 1, n, dfn[x], w[x]);  // 全部转移到宗教为c的线段树
            cri[x] = c;
        }else if(s == "CW"){
            int x, nw; cin >> x >> nw;
            update(root[cri[x]], 1, n, dfn[x], nw); // 评级改为nw
            w[x] = nw;
        }else if(s == "QS"){
            int x, y; cin >> x >> y;
            cout << qRange(x, y) << endl;
        }else if(s == "QM"){
            int x, y; cin >> x >> y;
            cout << qMx(x, y) << endl;
        }
    }

    return 0;
}
咏唱光芒 > 扬大校内选拔赛
#C++ #算法 #算法竞赛 #Luogu #YAC #选拔赛 #GPLT #团体天梯赛
2024 扬州大学与南通大学 GPLT 联谊选拔赛题解
https://marisamagic.github.io/2024/12/16/2024YZUGPLT/
作者
MarisaMagic
发布于
2024年12月16日
许可协议