Atcoder Beginner Contest 386 + 387 题解

发表于 更新于 分类于 阅读次数： 本文字数： 7.8k
Atcoder 每场之间的难度差异真大啊。

Atcoder Beginner Contest 386 题解

Atcoder Beginner Contest 387 题解

C

题意

一个不小于 10 的正整数，其十进制表示法的首位（最重要的一位）严格大于该数的其他各位，叫做蛇形数。例如， 31 和 201 是蛇形数，但 35 和 202 不是。

求在 L 和 R 之间（包括首尾两个数）有多少个蛇形数。

题解

数位 dp 采用记忆化搜索即可，本题需要维护最高位的数字（不能为 0 ），在 DFS 中加入参数 first ，并注意处理前导零，遇到不成立的情况需要 continue 。具体可见 https://www.incrediblej.cool/2025/03/21/%E6%95%B0%E4%BD%8Ddp%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/。

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

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

i64 dp[20][10];
int nums[20], sz;
i64 dfs(int pos, int first, bool sta, bool limit) {
    if (pos == sz + 1) {
        return 1;
    }
    if (!limit && dp[pos][first] != -1) {
        return dp[pos][first];
    }
    int up = limit ? nums[pos] : 9;
    i64 ans = 0;
    for (int i = 0; i <= up; i++) {
        if (sta == false && i >= first) {
            continue;
        }
        if (i == 0 && sta) {
            ans += dfs(pos + 1, 0, true, limit && i == up);
        } else {
            ans +=
                dfs(pos + 1, (first == 0 ? i : first), false, limit && i == up);
        }
    }
    if (!limit && !sta) {
        dp[pos][first] = ans;
    }
    return ans;
}

i64 get(i64 x) {
    string s = to_string(x);
    sz = s.size();
    s = " " + s;
    for (int i = 1; i <= sz; i++) {
        nums[i] = s[i] - '0';
    }
    for (int i = 0; i <= 19; i++) {
        for (int j = 0; j <= 9; j++) {
            dp[i][j] = -1;
        }
    }
    return dfs(1, 0, true, true);
}

void solve() {
    i64 l, r;
    cin >> l >> r;
    cout << get(r) - get(l - 1) << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D

题意

给定一个含有障碍的迷宫，求起点到终点的最短距离，要求每一步必须是横纵交替进行。

题解

考虑 BFS，但是我们需要在队列中额外记录上一次的方向，一个细节是最小值数组由于方向，不能直接 dis = min(dis) 来更新，要么最小值数组开两维，代表以横/纵方向到达的最小值，要么不取最小值，直接距离为上一次加 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
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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] = " " + a[i];
    }
    vector<vector<int>> dis(n + 1, vector<int>(m + 1, 1e18));
    vector<vector<array<int, 2>>> vis(n + 1, vector<array<int, 2>>(m + 1));
    queue<tuple<int, int, int>> q;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == 'S') {
                q.push({i, j, 0});
                q.push({i, j, 1});
                vis[i][j][0] = true, vis[i][j][1] = true;
                dis[i][j] = 0;
                break;
            }
        }
    }
    int ans = 1e18;
    while (!q.empty()) {
        auto [x, y, d] = q.front();
        q.pop();
        if (a[x][y] == 'G') {
            ans = min(ans, dis[x][y]);
            break;
        }
        int dx[] = {0, 0, 1, -1};
        int dy[] = {1, -1, 0, 0};
        for (int z = 0; z < 4; z++) {
            if (d == 1 && z < 2) {
                continue;
            }
            if (d == 0 && z > 1) {
                continue;
            }
            int fx = x + dx[z], fy = y + dy[z];
            auto check = [&](int x, int y, int z) {
                if (x < 1 || x > n || y < 1 || y > m) {
                    return false;
                }
                if (vis[x][y][z] || a[x][y] == '#') {
                    return false;
                }
                return true;
            };
            if (check(fx, fy, z < 2)) {  // 1 : 竖直 0 ： 水平
                q.push({fx, fy, z < 2});
                dis[fx][fy] = dis[x][y] + 1;
                // dis[fx][fy] = min(dis[x][y] + 1, dis[fx][fy]); 错误的
                vis[fx][fy][z < 2] = true;
            }
        }
    }
    if (ans == 1e18) {
        ans = -1;
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E

题意

给定一个数 \(N\)，在 \([N,2N-1]\) 中找到一个数 \(a\) ，满足 \(a\) 的数位和整除 \(a\)，\(a+1\) 的数位和整除 \(a+1\)。

题解

考虑加 1 后还能整除的情况，因为 3 和 9 整除是跟数位和有关的，可以着重往这里思考。

如果 \(a\) 的数位和为 2 的话，那么 \(a+1\) 的数位和就为 3，一定被 3 整除；如果 \(a\) 的数位和为 8 的话，那么 \(a+1\) 的数位和就为 9，一定被 9 整除，所以，我们构造的 \(a\) 最好要满足是 上述两种情况。

考虑什么时候能构造上面两种情况：当 \(N\) 的首位为6，7，8，9的时候，我们可选的范围一定是包含数字 11000...0 的，可以构造 2 的倍数，那么对位数较大的 \(N\) 直接输出即可。如果 \(N\) 的首位为 1，2，3，4，5，可以构造 9 的倍数，分别对应 17000...0 , 26000..0 , 35000...0, 44000...0, 53000...0 ，但是此时可能会出现不在范围的情况（例如，\(N\) 为 18000000，构造 17000000 就是不对的），我们需要判断这种情况并做出调整，高位加 1、低位减 1 即可，可以证明新数一定是在范围内的。

但是可能在 \(N\) 比较小的时候，由于 8 的倍数要求低三位数是 8 的倍数，不一定能保证这一点，对于较小的 \(N\) 我们可以暴力 \(O(N\log N)\)来判断。

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

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    if (n >= 5) {
        if (s[0] >= '6') {
            for (int i = 1; i <= n + 1; i++) {
                if (i == 1 || i == 2) {
                    cout << 1;
                } else {
                    cout << 0;
                }
            }
            cout << "\n";
        } else {
            int x = stoi(s.substr(0, 2));
            string ans;
            ans += s[0];
            ans += ('8' - s[0] + '0');
            int y = stoi(ans);
            if (x >= y) {
                ans[0]++;
                ans[1]--;
            }
            cout << ans;
            for (int i = 1; i <= n - 2; i++) {
                cout << 0;
            }
            cout << "\n";
        }
    } else {
        int x = stoi(s);
        for (int i = x; i <= 2 * x - 1; i++) {
            int sum = 0, xx = i, yy = i + 1, sumy = 0;
            while (xx) {
                sum += xx % 10;
                xx /= 10;
            }
            while (yy) {
                sumy += yy % 10;
                yy /= 10;
            }
            if (i % sum == 0 && (i + 1) % sumy == 0) {
                cout << i << "\n";
                return;
            }
        }
        cout << -1 << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

F

题意

给定数组 \(A_i\)，需要构造一个新数组 \(X\)，满足 \(X_{A_i} \ge X_i\)，且 \(1\le X_i\le M\)，求方案数（对 998244353 取模）。

题解

类似差分约束，我们从 \(A_i\) 向 \(i\) 连边，代表 \(X_{A_i} \ge X_i\)。这样形成的图可能会有环，环上的数一定都相等，所以考虑 SCC 强连通分量缩点，然后就会形成一个 DAG，考虑在 DAG 上 dp。设 \(dp_{i,j}\) 表示 父亲节点为 \(i\) ，该节点的数为 \(j\) 的情况数，状态转移应该是

\(dp_{i,j} = \prod_{i\rightarrow son}\sum_{k=1}^jdp_{son,k}\)，那么答案就是入度为 0 的节点的 \(dp_{i,m}\) 的乘积。

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

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

const int mod = 998244353;
struct SCC {
    int n;
    vector<vector<int>> adj;
    vector<int> stk;
    vector<int> dfn, low, bel;
    int cur, cnt;
    SCC() {}
    SCC(int n) { init(n); }
    void init(int n) {
        this->n = n;
        adj.assign(n + 1, {});
        dfn.assign(n + 1, -1);
        low.resize(n + 1);
        bel.assign(n + 1, -1);
        stk.clear();
        cur = cnt = 0;
    }
    void addEdge(int u, int v) { adj[u].push_back(v); }
    void dfs(int x) {
        dfn[x] = low[x] = cur++;
        stk.push_back(x);
        for (auto y : adj[x]) {
            if (dfn[y] == -1) {
                dfs(y);
                low[x] = min(low[x], low[y]);
            } else if (bel[y] == -1) {
                low[x] = min(low[x], dfn[y]);
            }
        }
        if (dfn[x] == low[x]) {
            int y;
            do {
                y = stk.back();
                bel[y] = cnt;
                stk.pop_back();
            } while (y != x);
            cnt++;
        }
    }
    vector<int> work() {
        for (int i = 1; i <= n; i++) {
            if (dfn[i] == -1) {
                dfs(i);
            }
        }
        return bel;
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    SCC scc(n);
    vector<vector<int>> e(n + 1);
    for (int i = 1; i <= n; i++) {
        scc.addEdge(a[i], i);
        e[a[i]].push_back(i);
    }
    vector<int> bel = scc.work();
    int n2 = scc.cnt;
    vector<vector<int>> e2(n2);
    vector<vector<i64>> dp(n2, vector<i64>(m + 1, 1));
    vector<int> deg(n2);
    vector<bool> vis(n2);
    for (int i = 1; i <= n; i++) {
        for (auto j : e[i]) {
            if (bel[i] == bel[j]) {
                continue;
            }
            e2[bel[i]].push_back(bel[j]);
            deg[bel[j]] = 1;
        }
    }
    i64 ans = 1;
    for (int i = 0; i < n2; i++) {
        if (!deg[i]) {
            auto dfs = [&](auto dfs, int x) -> void {
                for (auto y : e2[x]) {
                    dfs(dfs, y);
                    for (int j = 1; j <= m; j++) {
                        dp[x][j] = dp[x][j] * dp[y][j] % mod;
                    }
                }
                for (int i = 2; i <= m; i++) {
                    dp[x][i] = (dp[x][i - 1] + dp[x][i]) % mod;
                }
            };
            dfs(dfs, i);
            ans = ans * dp[i][m] % mod;
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}