2024 YAC Round 2 题解

A. 辉夜的最强密码

题目描述

输入多个字符串，判断每个字符串是否满足指定条件。满足条件输出“True\text{True}”；否则输出“False\text{False}”。「YAC Round 2」辉夜的最强密码

解题思路 （字符串模拟）

考察字符串的一些基本操作，按照题意模拟即可。

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
#include<bits/stdc++.h>
using namespace std;

int main(){
    int T; cin >> T;
    while(T -- ){
        string s; cin >> s;
        int n = (int)s.size(); 
        if(n < 7){ // 条件1
            cout << "False" << '\n';
            continue;
        }
        // 条件2
        vector<bool> flag(3, false);
        for(auto &ch : s){
            if(islower(ch)) flag[0] = true;
            else if(isupper(ch)) flag[1] = true;
            else flag[2] = true;
        }
        if(!flag[0] || !flag[1] || !flag[2]){
            cout << "False" << '\n';
            continue;
        }
        // 条件3
        bool ok = true;
        for(int i = 0; i < n - 1; i ++ )
            if(isdigit(s[i]) && isdigit(s[i + 1])){
                ok = false;
                break;
            }
        cout << (ok ? "True" : "False") << '\n';
    } 

    return 0;
}

B. Light 的有序排列

题目描述

将一个排列切割成若干段，重新组合变成一个有序排列，统计最少的切割次数。Light 的有序排列

解法一 （双指针）

为了使得切割次数最少，对于现有排列中的有序且连续的部分，我们不去考虑切割它们中间的位置，例如 [2,3,4][2, 3, 4] 或者 [7,6][7, 6]。

我们只需要让切割的次数最少，而不需要去考虑翻转、组合的次数有多少。显然，我们只需要将所有 单调且连续 的区间切割出来，然后再进行多次翻转组合即可得到有序的排列（升序或降序都可以）。

故我们可以采用双指针算法统计 单调连续 区间的个数 cntcnt，最后区间个数 −1-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
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;

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

int n, a[N];

int main(){
    ios;

    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    int cnt = 0, l = 1, r;
    while(l <= n){
        r = l + 1;
        int flag = 0;
        if(a[l] == a[r] - 1) flag = 1; // 单调连续上升
        else if(a[l] == a[r] + 1) flag = -1; // 单调连续下降
        else{  
            cnt ++ ; // 一个数单独切割出来
            l = r;
            continue; 
        }
        while(r <= n && a[r] == a[r - 1] + flag) r ++ ;
        cnt ++ ; // 统计单调连续上升区间和单调下降区间个数
        l = r;
    }
    cout << cnt - 1 << '\n';  // 连续区间个数-1即为答案

    return 0;
}

解法二 （思维）

我们可以发现，对于连续的部分我们不需要进行切割；对于不连续的部分，我们需要切割出来进行重组。基于排列的性质，显然可以总结出：当 ∣ai−ai+1∣>1|a_i - a_{i + 1}| > 1 时，需要进行切割。故最终答案为排列中 ∣ai−ai+1∣>1|a_i - a_{i + 1}| > 1 出现的次数。

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

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

int n, a[N], res;

int main(){
    ios;

    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    for(int i = 1; i < n; i ++ ) res += (abs(a[i] - a[i + 1]) > 1);
    cout << res << '\n';

    return 0;
}

C. 八云蓝的 gcd 问题

题目描述

给定一个数字 nn，求 gcd(1,n)\text{gcd}(1, n) 一直到 gcd(n,n)\text{gcd}(n, n) 的 异或和，即 ⊕i=1ngcd(i,n)\oplus_{i=1}^n \text{gcd}(i, n)，⊕\oplus 表示按位异或。八云蓝的 gcd 问题

解题思路 （数学）

对于求解最大公约数，除了辗转相除法，还有一个方法称为 更相减损术，其用到了以下结论：

gcd(a,b)=gcd(b−a,b)\text{gcd}(a, b) = \text{gcd}(b - a, b)

在本题中也就是：

gcd(i,n)=gcd(n−i,n)\text{gcd}(i, n) = \text{gcd}(n - i, n)

而异或操作有一个特性，为 两个相同的数异或之后相互抵消，即变为 00 ，也就是 x⊕x=0x \oplus x = 0 。

按位异或运算是 满足交换律的，显然，在求异或和时，gcd(i,n)⊕gcd(n−i,n)=0\text{gcd}(i, n) \oplus \text{gcd}(n - i, n) = 0。所以我们可以得出如下结论：

当 nn 为 奇数，经过两两抵消后，最后只剩 gcd(n,n)\text{gcd}(n, n)，也就是 nn。故 nn 为奇数直接输出本身；

当 nn 为 偶数，经过抵消后，最后剩下 gcd(n2,n)\text{gcd}(\frac{n}{2}, n) 和 gcd(n,n)\text{gcd}(n, n)。故 nn 为偶数输出 n⊕gcd(n2,n)n \oplus \text{gcd}(\frac{n}{2}, n) 。（当然，其实这题甚至没必要去用gcd，因为 nn 为偶数时 gcd(n2,n)=n2\text{gcd}(\frac{n}{2}, n) = \frac{n}{2}，所以偶数输出 n⊕n2n \oplus \frac{n}{2} 即可）

PS：求解最大公约数若调用函数需要注意 C++ 版本。C++ 14 开始引入 __gcd 函数（注意是两个下划线），C++ 17 开始引入 gcd 库函数。 当然也可以自己手写一个 gcd 函数，代码中提供递归写法。

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

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

ll gcd(ll a, ll b){return b ? gcd(b, a % b) : a;} // 手写 gcd

int main(){
    ios;

    int T; cin >> T;
    while(T -- ){
        ll x; cin >> x; // gcd(i, n) == gcd(n - i, n) 异或后抵消
        cout << ((x & 1) ? x : (x ^ __gcd(x >> 1, x)))  << '\n'; 
    }

    return 0;
}

D. 蕾娜的基地扩张

题目描述

给定一个网格图，网格图上有若干的点，每个点每经过一个时刻会向四周扩张一次。两个点扩张的区域有重复的点即视为连通，求最早什么时刻所有点连通（即形成一个连通块）。「YAC Round 2」蕾娜的基地扩张

解法一 （二分 + 并查集）

每个点 每经过一个时刻会向四周扩张一次，显然两点之间的 曼哈顿距离 小于等于 两倍的时间 才会使得两点连通。故我们可以二分答案（扩张的时间），然后两两枚举图上的点，用 并查集 将曼哈顿距离小于等于当前时间两倍的两点进行合并，每次二分 check\text{check} 判断是否只有一个连通块即可。

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
#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 = 60;

pii p[N];
int n, fa[N];

int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);};
void merge(int x, int y){fa[find(x)] = find(y);};

bool check(int t){
    for(int i = 1; i <= n; i ++ ) fa[i] = i;
    for(int i = 1; i <= n; i ++ ){
        auto [x1, y1] = p[i];
        for(int j = i + 1; j <= n; j ++ ){
            auto [x2, y2] = p[j];
            int d = abs(x1 - x2) + abs(y1 - y2); // 曼哈顿距离
            if(d <= 2 * t) merge(i, j); 
        }
    }
    int f = find(1);
    for(int i = 2; i <= n; i ++ ) 
        if(find(i) != f) return false; // 判断是否有其他领头存在
    return true; // 连通块个数为1
}

解法二 （kruskal 最小生成树）

我们可以贪心地去求解这个问题，在网格图上的点两两之间建立一条边（长度即曼哈顿距离）。通过 krusakl\text{krusakl} 算法使得图中所有点构成一个最小生成树，此时也所有点也变成一个连通块。krusakl\text{krusakl} 算法过程中合并两点时的曼哈顿距离即为当前两点连通所需的最小距离。

故我们只需要知道 最小生成树中的最大边长度 dd 即可，最后输出 ⌈d2⌉\left \lceil \frac{d}{2} \right \rceil 即为最少需要的时间。

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
#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 = 60;

struct node{int u, v, w;}e[N * N];
pii p[N];
int n, m, fa[N];

int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);};

int kruskal(){
    for(int i = 1; i <= n; i ++ ) fa[i] = i;
    sort(e + 1, e + m + 1, [](node &a, node &b){
        return a.w < b.w;
    });
    int res = 0;  // 记录最后一个刚好使得所有点形成一个连通块的边长度
    for(int i = 1; i <= m; i ++ ){
        auto [u, v, w] = e[i];
        int fx = find(u), fy = find(v);
        if(fx == fy) continue;
        fa[fx] = fy;
        res = w;
    }
    return res;
}

int main(){
    ios;

    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> p[i].fi >> p[i].se;
    for(int i = 1; i <= n; i ++ ){
        auto [x1, y1] = p[i];
        for(int j = i + 1; j <= n; j ++ ){ // 建边
            auto [x2, y2] = p[j];
            int d = abs(x1 - x2) + abs(y1 - y2);
            e[ ++ m] = node{i, j, d};
        }
    }

    cout << ((kruskal() + 1) / 2) << '\n'; // 向上取整

    return 0;
}

解法三 （类Floyd算法）

我们还可以考虑用类似 Floyd\text{Floyd} 算法的思路来求解这个问题。设 dijd_{ij} 表示点 ii 和 点 jj 连通需要的最短时间（此时间不是最终答案，指的是需要的最短的曼哈顿距离）。采用类 Floyd\text{Floyd} 算法，kk 作为中间点，则 ii 和 jj 可以借助中间点 kk 连接从而连通。

假设 ii 和 kk 连通所需时间 dikd_{ik} 与 kk 和 jj 连通所需时间 dkjd_{kj} 的较大者为 tt。最后 ii 和 jj 连通所需的最少时间 dijd_{ij} 即本身与 tt 之间的较小者。 由此得到更新表达式：

d[i][j]=min⁡(d[i][j],max⁡(d[i][k],d[k][j]))d[i][j] = \min(d[i][j], \max(d[i][k], d[k][j]))

最后找出最大的 dd，输出 ⌈d2⌉\left \lceil \frac{d}{2} \right \rceil 即为答案。

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)
#define fi first
#define se second
typedef pair<int, int> pii;
const int N = 60;

pii p[N];
int d[N][N], n;

void floyd(){
    for(int k = 1; k <= n; k ++ )
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], max(d[i][k], d[k][j])); 
}

int main(){
    ios;

    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> p[i].fi >> p[i].se;
    for(int i = 1; i <= n; i ++ ){ // 建边
        auto [x1, y1] = p[i];
        for(int j = 1; j <= n; j ++ ){
            auto [x2, y2] = p[j];
            d[i][j] = abs(x1 - x2) + abs(y1 - y2);
        }
    }

    floyd();

    int res = 0;
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ )
            res = max(res, d[i][j]);   // 寻找最大边

    cout << ((res + 1) / 2) << '\n';

    return 0;
}

E. Kurisu 的不降数组

题目描述

给定一个长度为 nn 且只包含 −1,0,1-1, 0, 1 的数组 aa，每次操作可以 ai←ai+ai−1a_i \leftarrow a_i + a_{i - 1}，求使得数组 aa 单调不降的 最少操作次数。「YAC Round 2」Kurisu 的不降数组

解题思路 （状态机 DP）

显然我们可以用动态规划求解这个问题。我们可以用 dp[i][j]dp[i][j] 表示状态:

  • dp[i][0]dp[i][0] 表示前 ii 个数字，且第 ii 个数字为 00 时，使得 a[1…i]a[1 \ldots i] 不降的最少操作次数；

  • dp[i][1]dp[i][1] 表示前 ii 个数字，且第 ii 个数字为 11 时，使得 a[1…i]a[1 \ldots i] 不降的最少操作次数；

  • dp[i][2]dp[i][2] 表示前 ii 个数字，且第 ii 个数字为 −1-1 时，使得 a[1…i]a[1 \ldots i] 不降的最少操作次数。

PS：当然状态表示不是唯一的，以上只是提供了我自己的方式


由此我们可以得到状态转移方程如下：

  • 当 a[i]=0a[i] = 0 时：

    • 不对当前位置进行操作。前面可以是 −1-1 或 00，满足不降。

    dp[i][0]=min⁡(dp[i−1][0],dp[i−1][2])dp[i][0] = \min(dp[i - 1][0], dp[i - 1][2])

    • 当前位置的 00 经过 一次 操作后变成 11，前面一个位置要求为 11 。 此时满足不降。

    dp[i][1]=dp[i−1][1]+1dp[i][1] = dp[i - 1][1] + 1

    • 当前位置的 00 经过 一次 操作后变成 −1-1，前面一个位置要求为 −1-1 。 此时满足不降。

    dp[i][2]=dp[i−1][2]+1dp[i][2] = dp[i - 1][2] + 1

  • 当 a[i]=1a[i] = 1 时：

    • 当前位置的 11 经过 一次 操作后变成 00，前面要求为 −1-1。此时满足不降。

    dp[i][0]=dp[i−1][2]+1dp[i][0] = dp[i - 1][2] + 1

    • 不对当前位置进行操作。前面可以是 −1-1 或 00 或 11，满足不降。

    dp[i][1]=min⁡(dp[i−1][0],dp[i−1][1],dp[i−1][2])dp[i][1] = \min(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2])

    • 当前位置的 11 经过 两次 操作后变成 −1-1，前面要求为 −1-1。此时满足不降。

    dp[i][2]=dp[i−1][2]+2dp[i][2] = dp[i - 1][2] + 2

  • 当 a[i]=−1a[i] = -1 时：

    • 前面为 11，可以经过一次操作使得当前位置变为 00，但是此时 不满足不降性质，所以 dp[i][0]dp[i][0] 不进行状态转移。

    • 当前位置的 −1-1 经过 两次次 操作后变成 11，前面要求为 11。此时满足不降。

    dp[i][1]=dp[i−1][1]+2dp[i][1] = dp[i - 1][1] + 2

    • 不对当前位置进行操作。前面可以是 −1-1，满足不降。

    dp[i][2]=dp[i−1][2]dp[i][2] = dp[i - 1][2]


求解的是最小次数，故 dpdp 数组全部初始化为 inf\text{inf}，dp[1][c]=0dp[1][c] = 0。经过状态转移后，最后枚举结尾数字 −1,0,1-1, 0, 1，输出最小值；若最小值为 inf\text{inf}，则说明无法使得数组不降，输出 “BRAK”。

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
#include<bits/stdc++.h>
using namespace std;

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

int dp[N][3], a[N], n; 

int main(){
    ios;

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

    memset(dp, 0x3f, sizeof dp);
    dp[1][a[1] >= 0 ? a[1] : 2] = 0;
    for(int i = 2; i <= n; i ++ ){
        int x = a[i];
        if(x == 0){
            dp[i][0] = min(dp[i - 1][0], dp[i - 1][2]);
            dp[i][1] = dp[i - 1][1] + 1;
            dp[i][2] = dp[i - 1][2] + 1;
        }else if(x == 1){
            dp[i][0] = dp[i - 1][2] + 1;
            dp[i][1] = min({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]});
            dp[i][2] = dp[i - 1][2] + 2;
        }else{
            dp[i][1] = dp[i - 1][1] + 2;
            dp[i][2] = dp[i - 1][2];
        }
    }

    int res = inf;
    for(int i = 0; i <= 2; i ++ ) res = min(res, dp[n][i]);
    if(res == inf) puts("BRAK");
    else cout << res << '\n';

    return 0;
}

当然，每一层关系只与前面一层有关，我们可以使用滚动数组进行空间优化。

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
#include<bits/stdc++.h>
using namespace std;

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

int dp[2][3], a[N], n; 

int main(){
    ios;

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

    memset(dp, 0x3f, sizeof dp);
    dp[1][a[1] >= 0 ? a[1] : 2] = 0;
    for(int i = 2; i <= n; i ++ ){
        int x = a[i];
        for(int j = 0; j <= 2; j ++ ) dp[i & 1][j] = inf;
        if(x == 0){
            dp[i & 1][0] = min(dp[(i - 1) & 1][0], dp[(i - 1) & 1][2]);
            dp[i & 1][1] = dp[(i - 1) & 1][1] + 1;
            dp[i & 1][2] = dp[(i - 1) & 1][2] + 1;
        }else if(x == 1){
            dp[i & 1][0] = dp[(i - 1) & 1][2] + 1;
            dp[i & 1][1] = min({dp[(i - 1) & 1][0], dp[(i - 1) & 1][1], dp[(i - 1) & 1][2]});
            dp[i & 1][2] = dp[(i - 1) & 1][2] + 2;
        }else{
            dp[i & 1][1] = dp[(i - 1) & 1][1] + 2;
            dp[i & 1][2] = dp[(i - 1) & 1][2];
        }
    }

    int res = inf;
    for(int i = 0; i <= 2; i ++ ) res = min(res, dp[n & 1][i]);
    if(res == inf) puts("BRAK");
    else cout << res << '\n';

    return 0;
}

F. 妖梦的麻薯之行

题目描述

11 号点 到 NN 号点的最短路长为 dd，给定一个 KK，求有向图中 11 到 NN 长度 ≤d+K\le d + K 的路线数量。「YAC Round 2」妖梦的麻薯之行

解题思路 （最短路 + 记忆化搜索）

首先我们需要求得 11 到 NN 的最短路距离 dd，这里采用堆优化 dijkstra\text{dijkstra} 。

然后我们需要用动态规划来求解距离长度 ≤d+K\le d + K 的路线数量。dp[u][k]dp[u][k] 表示从 11 到 uu 的且路径长度为 kk 的方案数量，由此有如下状态转移方程：

dp[u][k]=∑(u,v)∈Gdp[v][k−w(u,v)]dp[u][k] = \sum_{(u,v)\in G} dp[v][k - w(u, v)]

其中 w(u,v)w(u,v) 为边 (u,v)(u, v) 的长度。但是，距离有可能很大，所以这样进行状态表示无疑会内存超限。因此我们需要优化设计状态表示。

显然，11 到任何一个点 uu 最短路的距离 d[u]d[u] 是不会变化的，因此我们可以用 dp[u][k]dp[u][k] 来表示 11 到 uu 且路径长度为 d[u]+kd[u] + k 的路线方案数量。 这样可以避免内存超限的问题。

假设 dp[u][k]dp[u][k] 可以由 dp[v][x]dp[v][x] 进行状态转移得到，有如下状态转移方程：

dp[u][k]=∑(u,v)∈Gdp[v][x]dp[u][k] = \sum_{(u, v) \in G}dp[v][x]

dp[v][x]dp[v][x] 为 11 到 vv 且路径长度为 d[v]+xd[v] + x 的路线方案数量。通过边 (u,v)(u, v) （PS：在实际图中对应边 (v,u)(v, u) ）得到 11 到 uu 的长度为 d[u]+kd[u] + k 的路线，即 d[v]+x+w(u,v)=d[u]+kd[v] + x + w(u, v) = d[u] + k。经过移项后：

x=d[u]+k−d[v]−w(u,v)x = d[u] + k - d[v] - w(u,v)

故最终状态转移如下：

dp[u][k]=∑(u,v)∈Gdp[v][d[u]+k−d[v]−w(u,v)]dp[u][k] = \sum_{(u,v)\in G} dp[v][d[u] + k - d[v] - w(u,v)]

最终的答案为 ∑i=0Kdp[N][i]\sum_{i=0}^K dp[N][i]，我们可以用记忆化搜索，自底向上得出每个 dp[N][i]dp[N][i]。由于是自底向上的求解过程，由前面的点得到当前点的状态，故我们需要另外建立一个反向图，在反向图上进行记忆化搜索。

对于判断是否有无数条路径，主要原因在于图中会存在若干长度为 00 的边，有可能会构成一个长度为 00 的环路。我们可以在记忆化搜索的过程中记录是否会导致无数条满足条件的路线数量。用一个二维 visvis 数组，vis[u][k]vis[u][k] 表示 dp[u][k]dp[u][k] 的状态是否更新过，再用一个 flagflag 记录是否导致无数条满足条件的路线。如果当前 $dp[u][k] $更新过的前提下，经过 00 环继续更新 dp[u][k]dp[u][k] 的状态，此时就表明会出现无数条满足条件的路线，之后置 flagflag 为 true\text{true} 同时停止递归即可。

还有一个需要注意的是，求解 dp[N][i]dp[N][i] 的记忆化搜索过程中，无法处理起点 11 到 11 可能存在的长度为 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
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
#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define MP make_pair
#define pque priority_queue
typedef pair<int, int> pii;
const int N = 1e5 + 10, M = (N << 1), inf = 0x3f3f3f3f;

int h[N], e[M], ne[M], w[M], idx; // 正向图 用于求最短路
vector<pii> edge[N];  // 反向图 用于记忆化搜索
int n, m, K, P;

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

int dist[N];
bool st[N];
// 堆优化dijkstra求最短路
void dijkstra(){
    for(int i = 1; i <= n; i ++ ) dist[i] = inf, st[i] = false;
    dist[1] = 0;
    pque<pii, vector<pii>, greater<pii> > q;
    q.push(MP(dist[1], 1));

    while(q.size()){
        auto [d, u] = q.top();
        q.pop();

        if(st[u]) continue;
        st[u] = true;

        for(int i = h[u]; i; i = ne[i]){
            int v = e[i], c = w[i];
            if(dist[v] > d + c){
                dist[v] = d + c;
                q.push(MP(dist[v], v));
            }
        }
    }
}

bool flag;        // 用于标记合法路径中是否走到过0边，有则有无数条路径
bool vis[N][51];  // 用于标记是否访问过，若访问过则说明是从0边过来的
int f[N][51];     // f[u][k] 表示 1 -> u 的长度为 dist[u] + k 的路径数量
// 记忆化搜索
int dp(int u, int k){
    if(k < 0) return 0;
    if(vis[u][k]){ // 若更新过再次更新 则表明是从0环过来的
        flag = true;
        return 0;
    }
    if(f[u][k]) return f[u][k];

    vis[u][k] = true;
    int res = 0;
    for(auto &[v, w] : edge[u]){
        res = (res + dp(v, dist[u] + k - dist[v] - w)) % P; // 状态转移
        if(flag) return 0;
    }
    vis[u][k] = false;

    return f[u][k] = res;
}

void clr(){
    idx = 0;
    for(int i = 1; i <= n; i ++ ) edge[i].clear(), h[i] = 0;
    flag = false;
    memset(f, 0, sizeof f);
    memset(vis, 0, sizeof vis);
}

int main(){
    ios;

    int T = 1; scanf("%d", &T);
    while(T -- ){
        
        scanf("%d%d%d%d", &n, &m, &K, &P);
        while(m -- ){
            int u, v, c; scanf("%d%d%d", &u, &v, &c);
            add(u, v, c);
            edge[v].push_back(MP(u, c));
        }

        dijkstra();  // 求最短路
        dp(1, 0);    // 记忆化搜索处理1到1的0环 若存在则flag=true
        f[1][0] = 1;

        int res = 0;
        for(int i = 0; i <= K; i ++ ) res = (res + dp(n, i)) % P;

        if(flag) puts("-1"); // 路径上存在 0 环，则表明有无数条路径
        else printf("%d\n", res);

        clr(); // 清空 
    }

    return 0;
}
咏唱光芒 > YAC 扬州大学算法练习赛
#C++ #算法 #算法竞赛 #Luogu #YAC
2024 YAC Round 2 题解
https://marisamagic.github.io/2024/12/14/YAC_Round_2/
作者
MarisaMagic
发布于
2024年12月14日
许可协议