AtCoder Beginner Contest 192

发表于2021-02-22更新于2023-09-15字数统计898阅读时长9分

比赛链接

E Train

Description

题目链接

Solution

设 disidis_i 表示从起点到 ii 的最短时间。设当前节点 nownow，disnowdis_{now} 已求出，节点 nownow 的后继节点为 toto，所连边编号为 ii，则有 disto=min(disto,disnow+⌈disnowki⌉∗ki+ti）dis_{to} = min(dis_{to},dis_{now+} \lceil \frac{dis_{now}}{k_i} \rceil*k_i+t_i）。用 DijkstraDijkstra 算法跑一遍最短路即可。

Code

Train
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
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl
#define int long long

using namespace std;
typedef long long LL;

template <class T>
void read(T& x) {
    x = 0;
    T f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

template <class T, class... Args>
void read(T& x, Args&... args) {
    read(x), read(args...);
}

struct Edge {
    int to, k, t;
};

const int MAXN = 1E5 + 5;

vector<Edge> G[MAXN];

int n, m, dis[MAXN], vis[MAXN], x, y;

void solve(int caseNum) {
    read(n, m, x, y);
    for (int i = 1; i <= m; i++) {
        int u, v, k, t;
        read(u, v, t, k);
        G[u].push_back(Edge{v, k, t});
        G[v].push_back(Edge{u, k, t});
    }
    for (int i = 1; i <= n; i++) dis[i] = 1e18;
    priority_queue<pair<int, int>, vector<pair<int, int> >,
                   greater<pair<int, int> > >
        q;
    dis[x] = 0;
    q.push({0, x});
    while (!q.empty()) {
        int now = q.top().second;
        q.pop();
        if (vis[now]) continue;
        vis[now] = 1;
        for (auto& e : G[now]) {
            int to = e.to;
            int k = e.k;
            int t = e.t;
            int tmp =
                (dis[now] % k == 0 ? dis[now] / k : dis[now] / k + 1) * k + t;
            if (dis[to] > tmp) {
                dis[to] = tmp;
                q.push({dis[to], to});
            }
        }
    }
    if (dis[y] == 1e18)
        cout << -1;
    else
        cout << dis[y];
}

signed main() {
    int testCase = 1;
    for (int i = 1; i <= testCase; i++) solve(i);
    return 0;
}

F Potion

Description

题目链接

Solution

设选了 cc 种材料，那么对于某个固定的 CC，要使达到魔法值 XX 的时间最小，我们需要让选择材料的魔法值的和尽可能大，且该和与 XX 模 CC 同余。设 dp[i][j][k]dp[i][j][k] 表示在前 ii 种材料中选了 jj 个，这些材料魔法值的和模 CC 余 kk 时能得到的最大魔法值。那么有dp[i][j][k]=max(dp[i−1][j][k],dp[i−1][j−1)[((k−A[i])%C+C)%C]+Ai)dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-1)[((k - A[i]) \% C + C) \% C]+A_i)，于是答案即为 min⁡1≤C≤NX−dp[N][C][X%C]C\min\limits_{1 \le C \le N} \frac{X-dp[N][C][X \% C]}{C}。注意状态转移时只从合法的状态转移，对于不合法的状态，我们设其 dpdp 值为 −1-1，遇到这些状态应直接跳过。

Code

Potion
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>

#define debug(x) cerr << #x << " = " << x << endl
#define int long long

using namespace std;

const int MAXN = 101;
const int MOD = 1E9 + 7;
int n, x, a[MAXN], dp[MAXN][MAXN][MAXN], ans = 1E18;

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> x;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int c = 1; c <= n; c++) {
        memset(dp, -1, sizeof(dp));
        for (int i = 0; i <= n; i++) dp[i][0][0] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= i; j++) {
                for (int k = 0; k < c; k++) {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if (dp[i - 1][j - 1][((k - a[i]) % c + c) % c] != -1)
                        dp[i][j][k] = max(
                            dp[i][j][k],
                            dp[i - 1][j - 1][((k - a[i]) % c + c) % c] + a[i]);
                }
            }
        if (dp[n][c][x % c] != -1) ans = min(ans, (x - dp[n][c][x % c]) / c);
    }
    cout << ans;
    return 0;
}