AtCoder Beginner Contest 197

发表于2021-04-11更新于2023-09-15字数统计799阅读时长9分

比赛链接

D Hanjo

Description

题目链接

Solution

Code

Hanjo
1
2


时间复杂度为 O(2HW(HW)3)O(2^{\sqrt{HW}}(HW)^3)。

Code

Hanjo
1
2


E Traveler

Description

Solution

Code

Traveler
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
constexpr int MAXN = 2e5 + 5, MOD = 1e9 + 7;
#define int long long

int n;
array<long long, MAXN> x, c, l, r;
long long dp[MAXN][2];

signed main() {
    boost;
    cin >> n;
    vector<int> vc;
    memset(dp, 0x3f, sizeof(dp));
    fill(l.begin(), l.end(), 2e9);
    fill(r.begin(), r.end(), -2e9);
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> c[i];
        l[c[i]] = min(l[c[i]], x[i]);
        r[c[i]] = max(r[c[i]], x[i]);
        vc.push_back(c[i]);
    }
    sort(vc.begin(), vc.end());
    int cnt = unique(vc.begin(), vc.end()) - vc.begin();
    for (int i = 0; i < cnt; i++) {
        int co = vc[i], L = l[co], R = r[co], prePos = 0;
        if (i == 0) {
            if (R * L < 0) {
                dp[0][0] = R * 2 - L; // stop at left
                dp[0][1] = 2LL * (-L) + R;
            } else {
                if (R > 0) {
                    dp[0][0] = 2LL * R - L;
                    dp[0][1] = R;
                } else {
                    dp[0][0] = -L;
                    dp[0][1] = 2LL * (-L) - R;
                }
            }
        } else {
            prePos = l[vc[i - 1]];
            if ((R - prePos) * (L - prePos) < 0) {
                dp[i][0] = min(dp[i][0], dp[i - 1][0] + (R - prePos) * 2 - (L - prePos));
                dp[i][1] = min(dp[i][1], dp[i - 1][0] + 2LL * (-(L - prePos)) + (R - prePos));
            } else {
                if ((R - prePos) > 0) {
                    dp[i][0] = min(dp[i][0], dp[i - 1][0] + 2LL * (R - prePos) - (L - prePos));
                    dp[i][1] = min(dp[i][1], dp[i - 1][0] + R - prePos);
                } else {
                    dp[i][0] = min(dp[i][0], dp[i - 1][0] + (-(L - prePos)));
                    dp[i][1] = min(dp[i][1], dp[i - 1][0] + 2LL * (-(L - prePos)) - (R - prePos));
                }
            }

            prePos = r[vc[i - 1]];
            if ((R - prePos) * (L - prePos) < 0) {
                dp[i][0] = min(dp[i][0], dp[i - 1][1] + (R - prePos) * 2 - (L - prePos));
                dp[i][1] = min(dp[i][1], dp[i - 1][1] + 2LL * (-(L - prePos)) + (R - prePos));
            } else {
                if ((R - prePos) > 0) {
                    dp[i][0] = min(dp[i][0], dp[i - 1][1] + 2LL * (R - prePos) - (L - prePos));
                    dp[i][1] = min(dp[i][1], dp[i - 1][1] + R - prePos);
                } else {
                    dp[i][0] = min(dp[i][0], dp[i - 1][1] + (-(L - prePos)));
                    dp[i][1] = min(dp[i][1], dp[i - 1][1] + 2LL * (-(L - prePos)) - (R - prePos));
                }
            }
        }
    }
    cout << min(dp[cnt - 1][0] + abs(l[vc.back()]), dp[cnt - 1][1] + abs(r[vc.back()]));
    return 0;
}

F Construct a Palindrome

Description

题目链接

Solution

Code

Construct a Palindrome
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;

constexpr int MAXN = 1e3 + 3, MOD = 1e9 + 7;

int n, m, vis[MAXN][MAXN];

vector<int> g[MAXN][26];

struct Node {
    Node() = default;
    Node(int _a, int _b, int _c) : v1(_a), v2(_b), dist(_c) {}

    bool operator<(const Node& other) const {
        return dist > other.dist;
    }

    int v1, v2, dist;
};

void dijkstra() {
    priority_queue<Node> q;
    for (int i = 1; i <= n; i++) {
        q.push(Node(i, i, 0));
        for (int c = 0; c < 26; c++)
            for (auto& to : g[i][c])
                q.push(Node(to, i, 1)), q.push(Node(i, to, 1));
    }
    while (!q.empty()) {
        int x = q.top().v1, y = q.top().v2, dist = q.top().dist;
        q.pop();
        if (vis[x][y]) continue;
        vis[x][y] = true;
        if ((x == 1 && y == n) || (x == n && y == 1)) {
            cout << dist << endl;
            return;
        }
        for (int c = 0; c < 26; c++) {
            for (auto& to1 : g[x][c]) {
                for (auto& to2 : g[y][c]) {
                    if (to1 != to2) {
                        q.push(Node(to1, to2, dist + 2));
                        q.push(Node(to2, to1, dist + 2));
                    } else {
                        q.push(Node(to1, to2, dist + 2));
                    }
                }
            }
        }
    }
    cout << -1 << endl;
}

int main() {
    boost;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        char c;
        cin >> u >> v >> c;
        g[u][c - 'a'].push_back(v);
        g[v][c - 'a'].push_back(u);
    }
    dijkstra();
    return 0;
}