Atcoder Beginner Contest 396 + 397 题解

发表于 更新于 分类于 阅读次数： 本文字数： 11k
训练ing。

Atcoder Beginner Contest 396 题解

D

题意

给你一张简单无向图，每条边带有权值，求从 1 到 \(N\) 的路径中所有权值异或最小的一条。

\(N\le 10\)

题解

首先异或路径绝对不能使用 Dijkstra 或 Floyd 算法，因为当前边的最小值不一定能拓展到别的顶点。

考虑到如此小的 \(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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> e(n + 1);
    for (int i = 1; i <= m; i++) {
        int x, y, v;
        cin >> x >> y >> v;
        e[x].emplace_back(y, v);
        e[y].emplace_back(x, v);
    }
    vector<bool> vis(n + 1);
    int ans = LLONG_MAX;
    auto dfs = [&](auto self, int x, int v) -> void {
        if (vis[x]) {
            return;
        }
        if (x == n) {
            ans = min(ans, v);
        }
        vis[x] = 1;
        for (auto [y, w] : e[x]) {
            self(self, y, v ^ w);
        }
        vis[x] = 0;
    };
    dfs(dfs, 1, 0);
    cout << ans << "\n";
}

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

E

题意

给定三个数组 \(X,Y,Z\)，求出一个数组 \(A\) ，满足 \(A_{X_i} \oplus A_{Y_i} = Z_i\)，且 \(\sum_{i=1}^NA_i\) 最小或判断不存在。

题解

显然对于每个 \(i\) ，\(X_i\) 和 \(Y_i\) 有着一个约束关系，将它们之间连接一条边后会形成一个图，由于是异或操作，所以每一位可以独立考虑。

我们单独考虑每一位，不妨先不考虑真实存放的值 \(ans\)，而是求出一个相对的异或值 \(v\) 使得约束关系成立，（这样处理，最后求出答案的时候再异或上一个 0 / 1即可）。

然后考虑如何求出满足条件的相对关系：我们使用并查集维护连接在一起的边，并在并查集中加入权值：设根节点的初始值为 0，每当一个数加入并查集时，如果本来就相连，那么判断是否冲突（两值异或后为边权），如果不相连，就合并，新节点的权值也应该更新。

考虑这样的并查集的实现，首先查找功能需要进行路径压缩，压缩过程中还需要往根节点异或路径顶点的权值，返回两个值：祖先节点和当前节点的相对权值；而合并功能由于存在祖先节点的更换，需要异或本身消除影响（ \(a\oplus a = 0\)）。

然后考虑答案的最小值：对于每一位，所有节点都是 0 或 1，那么如果 1 比较多，我们就给每个节点再异或上一个 1 ，使得 0 尽可能多，如果 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
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
#include <bits/stdc++.h>
using namespace std;
#define int long long

struct DSU {
    int n;
    vector<int> p, sz, v;
    DSU(int n_) {
        n = n_;
        init(n);
    }
    void init(int n) {
        p.resize(n + 1);
        sz.resize(n + 1, 1);
        v.resize(n + 1);
        iota(p.begin() + 1, p.end(), 1);
    }
    pair<int, int> find(int x) {
        if (p[x] != x) {
            auto [root, val] = find(p[x]);
            p[x] = root;
            v[x] ^= val;
        }
        return {p[x], v[x]};
    }
    bool merge(int x, int y, int z) {
        auto [rx, vx] = find(x);
        auto [ry, vy] = find(y);
        if (rx == ry) {
            return (vx ^ vy) == z;
        } else {
            p[rx] = ry;
            v[rx] = vx ^ vy ^ z;
            return true;
        }
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> x(m + 1), y(m + 1), z(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> x[i] >> y[i] >> z[i];
    }
    vector<int> ans(n + 1);
    for (int k = 30; k >= 0; k--) {
        DSU dsu(n);
        bool ok = true;
        for (int i = 1; i <= m; i++) {
            int u = x[i], v = y[i];
            int z_bit = (z[i] >> k) & 1;
            if (!dsu.merge(u, v, z_bit)) {
                ok = false;
                break;
            }
        }
        if (!ok) {
            cout << -1 << "\n";
            return;
        }
        map<int, vector<int>> g;
        for (int i = 1; i <= n; i++) {
            auto [rt, val] = dsu.find(i);
            g[rt].push_back(i);
        }
        for (auto &[rt, e] : g) {
            int c0 = 0, c1 = 0;
            for (auto v : e) {
                if (dsu.v[v] == 0) {
                    c0++;
                } else {
                    c1++;
                }
            }
            int bit = (c0 <= c1) ? 1 : 0;
            for (auto v : e) {
                int b = bit ^ dsu.v[v];
                if (b) {
                    ans[v] |= (1 << k);
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " \n"[i == n];
    }
}

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

F

题意

给定 \(n, m\) 和 长度为 \(n\) 的数组 \(a\)，对于 \(k = 0,1,...,m-1\)，使得 \(a\) 中每个数都加上 \(k\) 再对 \(m\) 取模。输出当前数组的逆序对数。

题解

显然一次操作后有影响的数就是原来的值为 \(m - k\) 的数，因为它会变成 0 ，使得与它前面位置的数形成更多逆序对，与后面位置形成逆序对的数量减少，而其他数的相对大小不变，逆序对数也不变。

我们设满足这种条件的数的下标为 \(v_1, v_2,...,v_x\) ，显然 \(v_i\) 会与前面的 \(v_i - i\) 个数都形成逆序对，之前与后面的 \(n - v_i - (x - i)\)​ 个数形成的逆序对会消除。

我们使用权值树状数组统计逆序对数后按照上面的方式处理即可。

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

struct Fenwick {
    int n;
    vector<int> a;
    Fenwick(int n_ = 0) { init(n_); }
    void init(int n_) {
        n = n_;
        a.assign(n + 1, 0);
    }
    void add(int x, int v) {
        for (int i = x; i <= n; i += i & (-i)) {
            a[i] += v;
        }
    }
    int sum(int x) {
        int res = 0;
        for (int i = x; i > 0; i -= i & (-i)) {
            res += a[i];
        }
        return res;
    }
    int rangeSum(int l, int r) { return sum(r) - sum(l - 1); }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    vector<vector<int>> g(m);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        g[a[i]].push_back(i);
    }
    int res = 0;
    Fenwick fen(m + 1);
    for (int i = n; i >= 1; i--) {
        res += fen.sum(a[i] + 1);
        fen.add(a[i] + 2, 1);
    }
    cout << res << "\n";
    for (int i = m - 1; i >= 1; i--) {
        for (int j = 0; j < g[i].size(); j++) {
            res += g[i][j] - j - 1;
            res -= n - g[i][j] - (g[i].size() - j - 1);
        }
        cout << res << "\n";
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Atcoder Beginner Contest 397 题解

D

题意

给定一个 \(N\)，判断是否存在一对正整数 \(x, y\)，满足 \(x^3 - y^3 = N\)。

\(N\le 10^{18}\)

题解

我们第一想法是枚举 \(y\) ，判断 \(N+y^3\) 能不能开三次方，这样做的复杂度是 \(O(\sqrt{N})\)，很难通过。

考虑立方差公式：\(x^3 - y^3 = (x-y)\times(x^2+xy+y^2)\) ，我们令 \(d = x - y\) ，那么 \(x^2 + xy + y^2 \ge x^2 - 2xy+y^2 = d^2\)，所以 \(d^3 \le N\)，我们可以枚举 \(d\) ，令 \(N = (d + k) ^ 3 - k^3 = d^3 + 3d^2k + 3dk^2\) 一定会被 \(d\) 整除，接下来就是解方程 \(d^2 + 3dk + 3k^2 = \frac{N}{d}\)​，使用求根公式需要小心溢出，也可以使用二分求解。

时间复杂度： \(O(\sqrt[3]{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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i * i * i <= n; i++) {
        int k = n / i;
        if (i * k == n) {
            auto check = [&](int a, int b, int c) {
                // 求 ax^2 + bx + c  = 0 的解 x
                int lo = 0, hi = 1e9 + 1;
                while (lo <= hi) {
                    int mid = lo + (hi - lo) / 2;
                    if (a * mid * mid + b * mid + c > 0) {
                        hi = mid - 1;
                    } else if (a * mid * mid + b * mid + c < 0) {
                        lo = mid + 1;
                    } else {
                        return mid;
                    }
                }
                return 0ll;
            };
            k = check(3, 3 * i, i * i - k);
            if (k != 0) {
                cout << k + i << " " << k << "\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;
}

E

题意

给定一个有 \(NK\) 个节点的树，将这棵树分解为 \(N\) 条路径，每条路径上有 \(K\) 个节点，每个节点只能在一条路径中，判断是否可以分解。

题解

我们不妨从叶子节点贪心地往上拓展 \(K\) 个节点，那么从根节点 DFS 的过程中存在以下情况：

如果有三条及以上子链长度小于 \(K\)​ ，那么当前节点无论放在哪条链都不行。

如果恰好有两条子链长度小于 \(K\) ，那么必须满足两条链的节点数加上 1 等于 \(K\) ，也就是把它们与父节点合并在一起。

否则，当前节点放在子链中。

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
#include <iostream>
#include <vector>
using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> e(n * k + 1);
    vector<int> len(n * k + 1);

    for (int i = 1; i < n * k; i++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }

    auto dfs = [&](auto dfs, int x, int fa) -> bool {
        len[x] = 1;
        int cnt = 0, sum = 0;
        for (auto y : e[x]) {
            if (y == fa) {
                continue;
            }
            if (dfs(dfs, y, x) == 0) {
                return 0;
            }
            if (len[y] == k) {
                continue;
            }
            cnt++;
            sum += len[y];
        }
        if (cnt > 2) {
            cout << "No\n";
            return 0;
        }
        if (cnt == 2) {
            if (sum == k - 1) {
                len[x] = k;
            } else {
                cout << "No\n";
                return 0;
            }
        } else {
            len[x] = sum + 1;
        }
        return 1;
    };
    if (dfs(dfs, 1, 0)) {
        cout << "Yes\n";
    }
}

int main() {
    solve();
    return 0;
}

F

题意

在本场 C 题的基础上，把一个数组分解成三个非空数组，这三个数组的权值就是数组内不同元素的数量，求三个非空数组的权值和最大值。

题解

C 题的做法是求出原数组的前后缀答案，然后一次遍历求出最大值 \(\max(pre[i] + suf[i+1])\)。

然而本题可以分解为三个数组，也就是说如果原来的分割点为 \(i\) 的话，在 \([i+1, n)\)的区间里还可以再取一个分割点，直接模拟的话显然超时，我们不妨考虑各元素能产生的贡献：

设 \(nxt[i]\) 表示 \(i\) 位置右边第一个满足 \(a[j] = a[i]\) 的位置 \(j\) ，那么如果在 \([i, nxt[i] - 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
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <bits/stdc++.h>
using namespace std;

template <class Info, class Tag>
struct LazySegmentTree {
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) { init(n_, v_); }
    template <class T>
    LazySegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) { init(std::vector(n_ + 1, v_)); }
    template <class T>
    void init(std::vector<T> init_) {
        n = init_.size() - 1;
        info.assign(4 << (int)log2(n + 1), Info());
        tag.assign(4 << (int)log2(n + 1), Tag());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r) {
                info[p] = Info(init_[l]);  // 使用 Info 的构造函数
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }
    void pull(int p) { info[p] = info[2 * p] + info[2 * p + 1]; }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (l == r) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x <= m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m + 1, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) { modify(1, 1, n, p, v); }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l > y || r < x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return rangeQuery(2 * p, l, m, x, y) +
               rangeQuery(2 * p + 1, m + 1, r, x, y);
    }
    Info rangeQuery(int l, int r) { return rangeQuery(1, 1, n, l, r); }
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l > y || r < x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        rangeApply(2 * p, l, m, x, y, v);
        rangeApply(2 * p + 1, m + 1, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        return rangeApply(1, 1, n, l, r, v);
    }
};

struct Tag {
    int sum = 0;
    Tag() {}
    Tag(int x) : sum(x) {}
    void apply(const Tag &t) & { sum += t.sum; }
};
struct Info {
    int x = 0;
    Info() {}
    Info(int x) : x(x) {}
    void apply(const Tag &t) & { x += t.sum; }
};
Info operator+(const Info &a, const Info &b) { return Info(max(a.x, b.x)); }

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<int> pre(n + 1), suf(n + 1);
    set<int> st;
    for (int i = 1; i <= n; i++) {
        st.insert(a[i]);
        pre[i] = st.size();
    }
    st.clear();
    for (int i = n; i >= 1; i--) {
        st.insert(a[i]);
        suf[i] = st.size();
    }
    vector<int> nxt(n + 1, -1);
    vector<int> mp(n + 1, -1);
    for (int i = n; i >= 1; i--) {
        nxt[i] = mp[a[i]];
        mp[a[i]] = i;
    }
    LazySegmentTree<Info, Tag> tr(n);
    for (int i = 1; i <= n; i++) {
        if (nxt[i] != -1) {
            tr.rangeApply(i, nxt[i] - 1, 1);
        }
    }
    int ans = 0;
    for (int i = 1; i < n; i++) {
        if (nxt[i] != -1) {
            tr.rangeApply(i, nxt[i] - 1, -1);
        }
        int v = tr.rangeQuery(i + 1, n).x;
        ans = max(ans, pre[i] + suf[i + 1] + v);
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}