Atcoder Beginner Contest 398 题解

发表于 更新于 分类于 阅读次数： 本文字数： 5.9k
Atcoder第一次遇见交互题，很有趣，感觉是遇见过的最简单的F。

D

题意

一团火在 （0，0）产生烟雾，一个人在（R，C），现在有 T 个时间点，每个时间点会把产生的烟向一个方向吹去，且（0，0）会不断产生烟，求烟和人重合的时间点。

题解

模拟烟的路径是不现实的，考虑到相对运动，烟动和人动是等价的，因此可以改变人的位置，还需要考虑新生成的烟：在原来的参考系中（0，0）和（R，C）是相对静止的，因此新的参考系新生成的烟和人一起动。

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
#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() {
    int n, r, c;
    cin >> n >> r >> c;
    set<array<int, 2>> smoke;
    int x = 0, y = 0;
    smoke.insert({x, y});

    string s;
    cin >> s;
    for (int i = 0; i < n; i++) {
        switch (s[i]) {
            case 'N':
                x++;
                break;
            case 'W':
                y++;
                break;
            case 'S':
                x--;
                break;
            case 'E':
                y--;
                break;
        }
        smoke.insert({x, y});
        cout << smoke.count({r + x, c + y});
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E

题意

交互题。

给定一棵树，和对手轮流加边，要求形成的环大小不能是奇数，决定先后手和加边方式让自己胜利。

题解

赛时找了一下性质：如果能加边，那么两节点深度之和必须是奇数，且不能相邻（认为根节点深度为1），因为这样的话两节点之间间隔的节点数目一定是偶数个。那么 \(O(n^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
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
#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() {
    int n;
    cin >> n;
    vector<vector<int>> e(n + 1);
    vector<int> dep(n + 1), p(n + 1);
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    set<pair<int, int>> st;

    auto dfs = [&](auto dfs, int x, int fa) -> void {
        p[x] = fa;
        for (auto y : e[x]) {
            if (y == fa) {
                continue;
            }
            dep[y] = dep[x] + 1;
            dfs(dfs, y, x);
        }
    };
    dep[1] = 1;
    dfs(dfs, 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (p[i] == j || p[j] == i) {
                continue;
            }
            int d = dep[i] + dep[j] - 1;
            if (d % 2 == 0 && d >= 4) {
                st.insert({i, j});
            }
        }
    }
    if (st.size() % 2 == 1) {
        cout << "First" << endl;
        cout << (*st.begin()).first << " " << (*st.begin()).second << endl;
        st.erase(st.begin());
        while (!st.empty()) {
            int x, y;
            cin >> x >> y;
            if (x == -1 && y == -1) {
                return;
            }
            if (x > y) {
                swap(x, y);
            }
            st.erase(st.find({x, y}));
            cout << (*st.begin()).first << " " << (*st.begin()).second << endl;
            st.erase(st.begin());
        }
    } else {
        cout << "Second" << endl;
        while (!st.empty()) {
            int x, y;
            cin >> x >> y;
            if (x == -1 && y == -1) {
                return;
            }
            if (x > y) {
                swap(x, y);
            }
            st.erase(st.find({x, y}));
            cout << (*st.begin()).first << " " << (*st.begin()).second << endl;
            st.erase(st.begin());
        }
    }
}

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

后来补题时发现可以用二分图的思想来做：因为不能形成奇环，那么最后形成的一定是一张二分图，对原树进行染色后，设两集合大小分别为 \(A,B\)，那么能加的边数就是 \(AB - (n-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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#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() {
    int n;
    cin >> n;
    vector<vector<int>> e(n + 1);
    vector<vector<bool>> g(n + 1, vector<bool>(n + 1));
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
        g[x][y] = g[y][x] = true;
    }
    queue<int> q;
    vector<int> f(n + 1, -1);
    bool is_Bipartite = true;
    for (int i = 1; i <= n; i++) {
        if (f[i] == -1) {
            q.push(i);
            f[i] = 0;
            while (!q.empty()) {
                int x = q.front();
                q.pop();
                for (auto y : e[x]) {
                    if (f[y] == -1) {
                        f[y] = f[x] ^ 1;
                        q.push(y);
                    } else if (f[x] == f[y]) {
                        is_Bipartite = false;
                        break;
                    }
                }
            }
        }
        if (!is_Bipartite) {
            break;
        }
    }
    int cnt0 = 0, cnt1 = 0;
    for (int i = 1; i <= n; i++) {
        cnt0 += (f[i] == 0);
        cnt1 += (f[i] == 1);
    }
    int cur = 1;
    if (((cnt0 * cnt1) - (n - 1)) % 2 == 0) {
        cout << "Second" << endl;
    } else {
        cout << "First" << endl;
        cur = 0;
    }
    int x = 2, y = 1;
    while (true) {
        if (cur == 0) {
            while (g[x][y] || f[x] == f[y]) {
                y++;
                if (y == x) {
                    x++;
                    y = 1;
                }
            }
            g[x][y] = g[y][x] = true;
            cout << y << " " << x << endl;
        } else {
            int x, y;
            cin >> x >> y;
            if (x == -1) {
                break;
            }
            g[x][y] = g[y][x] = true;
        }
        cur ^= 1;
    }
}

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

F

题意

给定一个字符串，找到一个字符串，这个字符串的前缀是原串，且是一个回文串。

题解

观察一下可以得出，既然新串要求是回文串，那么我们只需要找原串的后缀中最长的回文串，然后把剩下的部分反转一下输出到后面去即可。

可以使用 Manacher 算法来处理每个位置的最长回文串半径，之后我们枚举一个位置 \(l\) ，满足这个位置开始的后缀是回文串。由于 Manacher 算法得到的数组 \(r\) 对应原串的长度就是 \(r - 1\)，因此只需要从中心开始，判断 \(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
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;

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

vector<int> manacher(string s) {
    string t = "#";
    for (auto c : s) {
        t += c;
        t += "#";
    }
    int n = t.size();
    vector<int> r(n);
    for (int i = 0, j = 0; i < n; i++) {
        if (2 * j - i >= 0 && j + r[j] > i) {
            r[i] = min(r[2 * j - i], j + r[j] - i);
        }
        while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) {
            r[i]++;
        }
        if (i + r[i] > j + r[j]) {
            j = i;
        }
    }
    return r;
}

void solve() {
    string s;
    cin >> s;
    auto r = manacher(s);
    int n = s.size();
    int l = 0;
    while (r[l + n] < n - l + 1) {
        l++;
    }
    string t = s.substr(0, l);
    reverse(t.begin(), t.end());
    cout << s + t << "\n";
    auto ans = s;
}

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