ACM训练-6月补题题解

发表于 更新于 分类于 阅读次数： 本文字数： 24k
快暑假集训了，期末也基本结束了该训练了。

CF1950 Div.4 F

题意

输出一棵树的最小深度，要求有 \(a\) 个节点有两个儿子，\(b\) 个节点有一个儿子，\(c\) 个节点为叶子节点。

题解

容易想到无解的情况是根据树的性质，节点数等于边数加一，节点数为 \(a + b+c\)，边数为 \(2a + b\)，那么一定有 \(a + 1 = c\)。

我在做的时候构造时想的先放叶子节点，然后往上放其他节点，这样做分类讨论的情况比较多，很复杂。

实际更好的做法是先把两个儿子的节点放了，然后往下放一个儿子的节点。

根据完全二叉树的性质，这 \(a\) 个节点会确定深度为 \(h = \log a + 1\) 的树的形状，但是这并不是一棵完美二叉树，我们可以用一些 \(b\) 节点把它补成一棵所有叶子节点深度都相同的二叉树，如果是完美的二叉树，叶子节点有 \(2^h\) 个，但是我们只能保留 \(c\) 个叶子节点，多出来的 \(2^h - c\) 个叶子节点对应的父亲应该是 \(b\) 个节点里面的。那么接下来用所有的 \(b\) 往下放，会增加深度 \(\lceil \frac{b}{c}\rceil\)​。

时间复杂度 \(O(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
#include <bits/stdc++.h>

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

void solve() {
    int a, b, c;
    std::cin >> a >> b >> c;
    if (a * 2 + b + 1 != a + b + c) {
        std::cout << -1 << "\n";
        return;
    }
    int log = a ? 32 - __builtin_clz(a) : 0;
    b -= (1 << log) - c;
    std::cout << log + (b + c - 1) / c << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t = 1;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

CF1950 Div.4 G

题意

\(n\) 个元素，每个元素有两种属性（长度小于等于 \(s\) 的字符串），可以选择删除一些元素后重新排列，要求相邻元素至少有一种属性相同，求最少删除数量。

\(n\le 16, s\le 10^4\)。

题解

看着很像连边后欧拉路径的一道题，但是数据范围提示得相当明显是状压 dp。

设 \(dp_{\{S\}, i}\) 是状态 \(S\)，最后一个元素是 \(i\) 是否可行，那么 \(dp_{\{S\}, i} = dp_{\{S\}, i} \mid dp_{\{S\} - i,j}\)，用 bool 数组表达即可。

初始状态 \(dp_{\{i\},i} = true\)​，但是字符串的长度比较长，最好能映射到一个整数快速比较，不然会 TLE。

时间复杂度 \(O(2^n\times n^2 + s\log s)\)

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

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

void solve() {
    int n;
    std::cin >> n;
    std::map<std::string, int> mpg, mpw;
    std::vector<int> g(n + 1), w(n + 1);
    int cntg = 0, cntw = 0;
    for (int i = 1; i <= n; i++) {
        std::string s, t;
        std::cin >> s >> t;
        g[i] = mpg[s] ? mpg[s] : mpg[s] = ++cntg;
        w[i] = mpw[t] ? mpw[t] : mpw[t] = ++cntw;
    }
    int S = 1 << n;
    int ans = n;
    std::vector<std::vector<bool>> dp(S, std::vector<bool>(n + 1));
    for (int i = 1; i <= n; i++) {
        dp[1 << (i - 1)][i] = true;
        dp[0][i] = true;
    }
    for (int s = 0; s < S; s++) {
        for (int p = 1; p <= n; p++) {
            if (s >> (p - 1) & 1) {
                for (int q = 1; q <= n; q++) {
                    if (s >> (q - 1) & 1 && (g[p] == g[q] || w[p] == w[q]) &&
                        dp[s - (1 << (p - 1))][q]) {
                        int j = s - (1 << (p - 1));
                        dp[s][p] = true;
                        if (dp[s][p]) {
                            ans = std::min(ans, n - __builtin_popcount(s));
                        }
                    }
                }
            }
        }
    }
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t = 1;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

ABC408 D

题意

给定一个 01 串，求翻转多少个位置才能使得这个串最多只有一段连续的 1。

题解

序列只能有一段连续的 1，设为 \([l ,r]\)，那么我们需要把 \([1, l - 1]\) 和 \([r + 1, n]\) 的 1 变为 0，\([l, r]\) 的 0 变为 1，可以通过前缀和预处理前缀 1 的个数 \(pre_i\)，那么需要改变的个数为：\(pre_{l - 1}+pre_n - pre_r + r - l + 1 - pre_r + pre_{l - 1}\)，即 \(r - 2pre_r + pre_n + (2pre_{l - 1} - (l - 1))\)，我们不妨固定 \(r\)，那么求最小值，就需要 \(2pre_{l - 1} - (l - 1)\) 的最小值，我们再预处理 \(2pre_x - x\)​ 的前缀最小值即可。

时间复杂度：\(O(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
#include <bits/stdc++.h>

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

void solve() {
    int N;
    std::cin >> N;
    std::string S;
    std::cin >> S;
    S = " " + S;
    std::vector<int> pre(N + 1);
    for (int i = 1; i <= N; i++) {
        pre[i] = pre[i - 1] + (S[i] == '1');
    }
    std::vector<int> premn(N + 1);
    for (int i = 1; i <= N; i++) {
        premn[i] = std::min(premn[i - 1], 2 * pre[i] - i);
    }
    int ans = 2e9;
    for (int i = 1; i <= N; i++) {
        ans = std::min(ans, i - 2 * pre[i] + pre[N] + premn[i]);
    }
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T;
    std::cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

ABC408 E

题意

给定简单无向图，存在边权，求 1 到 \(N\) 的路径中权值的或最小是多少。

题解

求或最小显然需要按位贪心考虑。我们可以从高位到低位，考虑能不能让这一位取 0，即是否能不经过这一位为 1 的边，从 1 到达 \(N\)，如果不行，这一位必须取 1。我们可以用并查集来做到这一点。

具体地，对于每一位分别合并该位为 0 的边，并且如果某条边高位取了 1，并且该边对应的位也是 1，它也应该合并。

时间复杂度：\(O(M\log^2n)\)

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

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

struct DSU {
    int n;
    std::vector<int> p, sz;
    DSU(int n_) { init(n_); }
    void init(int n_) {
        n = n_;
        p.resize(n + 1);
        sz.resize(n + 1, 1);
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        while (x != p[x]) {
            x = p[x] = p[p[x]];
        }
        return x;
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (sz[x] > sz[y]) {
            std::swap(x, y);
        }
        p[x] = y;
        sz[y] += sz[x];
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, M;
    std::cin >> N >> M;
    std::vector<std::array<int, 3>> e(M + 1);
    for (int i = 1; i <= M; i++) {
        int x, y, w;
        std::cin >> x >> y >> w;
        e[i] = {x, y, w};
    }
    int ans = 0;
    std::vector<bool> digit(30);
    for (int i = 29; i >= 0; i--) {
        DSU dsu(N);
        for (int j = 1; j <= M; j++) {
            auto [x, y, w] = e[j];
            if (w >> i & 1) {
                continue;
            }
            bool ok = true;
            for (int k = 29; k > i; k--) {
                if (digit[k] == false && w >> k & 1) {
                    ok = false;
                    break;
                }
            }
            if (!ok) {
                continue;
            }
            dsu.merge(x, y);
        }
        if (!dsu.same(1, N)) {
            digit[i] = true;
            ans |= (1 << i);
        }
    }
    std::cout << ans << "\n";

    return 0;
}

ABC408 F

题意

\(N\) 个脚手架，它们的高度 \(H\) 是 \(1～N\) 的排列且互不相同，求能进行的操作最大次数：从第 \(i\) 个脚手架跳到第 \(j\) 个，要求 \(H_j\le H_i - D\) 并且 \(1 \le \mid i - j\mid \le R\)。

题解

只能从高度大的向高度低的转移，比较容易想到的是 dp，但是 \(dp_i\) 设为位置 \(i\) 的情况不好转移，因为无法考虑到高度由低到高，由于高度是一个排列，这提示我们设 \(dp_i\) 为从高度 \(i\) 开始能进行的最大操作次数，\(pos_i\) 为高度为 \(i\) 的脚手架对应的位置。

考虑转移方程：如果是 \(dp_i = \max_{j = i - D}^{i - 1}dp_j + 1\)，还需要满足 \(1\le\mid pos_i - pos_j\mid \le R\)，这样的话不易判断第二个条件，考虑另一种转移为 \(dp_{i} = \max_{pos_j = i - R}^{i + R} dp_j\)，需要 \(j \le i - D\)，由于我们是从小到大转移的，第二个条件只需要在我们处理 \(i\) 时，也更新 \(dp_{i + D}\) 即可，对于转移方程，可以通过线段树优化，查询最大值即可。

时间复杂度：\(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
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
#include <bits/stdc++.h>

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

template <class Info>
struct SegmentTree {
    int n;
    std::vector<Info> info;
    SegmentTree(int n_, Info v_ = Info()) { init(n_, v_); }
    template <class T>
    SegmentTree(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 * (n + 1), Info());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r) {
                info[p] = init_[l];
                return;
            }
            int mid = (l + r) / 2;
            build(2 * p, l, mid);
            build(2 * p + 1, mid + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }
    void pull(int p) { info[p] = info[2 * p] + info[2 * p + 1]; }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (l == r) {
            info[p] = v;
            return;
        }
        int mid = (l + r) / 2;
        if (x <= mid) {
            modify(2 * p, l, mid, x, v);
        } else {
            modify(2 * p + 1, mid + 1, r, x, v);
        }
        pull(p);
    }
    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 mid = (l + r) / 2;
        return rangeQuery(2 * p, l, mid, x, y) +
               rangeQuery(2 * p + 1, mid + 1, r, x, y);
    }
};

struct Info {
    int x = 0;
    Info() {}
    Info(int x) : x(x) {}
};

Info operator+(const Info &a, const Info &b) {
    return Info(std::max(a.x, b.x));
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, D, R;
    std::cin >> N >> D >> R;
    std::vector<int> H(N + 1);
    for (int i = 1; i <= N; i++) {
        std::cin >> H[i];
    }
    std::vector<int> pos(N + 1), dp(N + 1);
    for (int i = 1; i <= N; i++) {
        pos[H[i]] = i;
        dp[i] = 1;
    }
    SegmentTree<Info> seg(N);
    for (int i = 1; i <= N; i++) {
        seg.modify(1, 1, N, pos[i], dp[i]);
        int j = i + D;
        if (j <= N) {
            int val = seg.rangeQuery(1, 1, N, std::max(1, pos[j] - R),
                                     std::min(N, pos[j] + R))
                          .x;
            val = std::max(val, 0) + 1, dp[j] = val;
        }
    }
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        ans = std::max(ans, dp[i]);
    }
    std::cout << ans - 1 << "\n";

    return 0;
}

ABC409 E

题意

给定一棵树，每个节点都放了正电荷或负电荷，边权代表每个单位的电荷移动的代价，在同一节点处的正负电荷可以相互抵消。求全部电荷恰好抵消的最小移动代价。

题解

一开始以为是换根 dp，计算全部电荷到根节点再抵消的代价，但是这样显然不是最优的答案，因为在中途相遇的电荷就可以抵消。因此我们直接通过一次 DFS 计算子节点的电荷到根的代价，然后计算根节点的电荷数继续递归。此时根节点的答案其实就是正确答案，因为最后一次抵消一定是两个相邻节点，一个全是正电荷，一个全是负电荷，再经过它们的连边后抵消。由于题目条件正负电荷恰好能相互抵消，因此选定一个终点，一定可以转移到其他相邻的节点。

时间复杂度：\(O(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
#include <bits/stdc++.h>

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

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N;
    std::cin >> N;
    std::vector<std::vector<std::array<int, 2>>> adj(N + 1);
    std::vector<int> X(N + 1);
    int sum = 0;
    for (int i = 1; i <= N; i++) {
        std::cin >> X[i];
        sum += X[i];
    }
    for (int i = 1; i < N; i++) {
        int x, y, w;
        std::cin >> x >> y >> w;
        adj[x].push_back({y, w});
        adj[y].push_back({x, w});
    }
    std::vector<i64> sz(N + 1);
    std::vector<i64> f(N + 1);
    i64 ans = 2e9;
    auto dfs = [&](auto dfs, int x, int fa) -> void {
        sz[x] = X[x];
        for (auto [y, w] : adj[x]) {
            if (y == fa) {
                continue;
            }
            dfs(dfs, y, x);
            sz[x] += sz[y];
            f[x] += f[y];
            f[x] += abs(sz[y] * w);
        }
    };
    dfs(dfs, 1, 0);
    sz[0] = sum;
    ans = f[1];
    // auto dfs2 = [&](auto dfs2, int x, int fa) -> void {
    //     for (auto [y, w] : adj[x]) {
    //         if (y == fa) {
    //             continue;
    //         }
    //         f[y] = f[x] + w * abs(sz[0] - 2 * sz[y]);
    //         ans = std::min(ans, f[y]);
    //         dfs2(dfs2, y, x);
    //     }
    // };
    // dfs2(dfs2, 1, 0);
    std::cout << ans << "\n";

    return 0;
}

ABC409 F

题意

给定二维平面上 \(N\) 个点和 \(Q\) 次操作，操作为新增一个点，合并所有距离最短的连通分量（连通分量的距离定义为它们之中点距离点最小值），如果只有一个连通分量输出 -1，查询两个点是否连通。

\(N,Q\le 1500\)

题解

看题意很容易想到并查集。对于操作 2，我们维护一个小根堆即可，每加入一个点，就把与所有点的距离都加入堆中，操作时取最小值判断是否连通即可。

值得注意的是要合并所有距离最短的，因此不是只合并一个，而是将所有距离为最小值的都合并。对于 -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
#include <bits/stdc++.h>

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

struct DSU {
    int n;
    std::vector<int> p, sz;
    DSU(int n_) {
        n = n_;
        init(n);
    }
    void init(int n) {
        p.resize(n + 1);
        sz.resize(n + 1, 1);
        iota(p.begin() + 1, p.end(), 1);
    }
    int find(int x) {
        while (x != p[x]) {
            x = p[x] = p[p[x]];
        }
        return x;
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (sz[x] > sz[y]) {
            std::swap(x, y);
        }
        sz[y] += sz[x];
        p[x] = y;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return sz[find(x)]; }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, Q;
    std::cin >> N >> Q;
    DSU dsu(N + Q);
    std::vector<std::array<int, 2>> a(N + Q + 1);
    for (int i = 1; i <= N; i++) {
        int x, y;
        std::cin >> x >> y;
        a[i] = {x, y};
    }
    std::priority_queue<std::array<int, 3>, std::vector<std::array<int, 3>>,
                        std::greater<>>
        pq;
    for (int i = 1; i <= N; i++) {
        for (int j = i + 1; j <= N; j++) {
            pq.push({abs(a[i][0] - a[j][0]) + abs(a[i][1] - a[j][1]), i, j});
        }
    }
    while (Q--) {
        int op;
        std::cin >> op;
        if (op == 1) {
            int x, y;
            std::cin >> x >> y;
            a[++N] = {x, y};
            for (int i = 1; i < N; i++) {
                pq.push({abs(x - a[i][0]) + abs(y - a[i][1]), i, N});
            }
        } else if (op == 2) {
            bool ok = false;
            int min_d = 2e9;
            while (!pq.empty()) {
                auto [d, x, y] = pq.top();
                if (min_d != 2e9 && d != min_d) {
                    break;
                }
                pq.pop();
                if (dsu.merge(x, y)) {
                    min_d = d;
                    if (!ok) {
                        std::cout << d << "\n";
                    }
                    ok = true;
                }
            }
            if (!ok) {
                std::cout << -1 << "\n";
            }
        } else {
            int x, y;
            std::cin >> x >> y;
            if (dsu.same(x, y)) {
                std::cout << "Yes\n";
            } else {
                std::cout << "No\n";
            }
        }
    }

    return 0;
}

CF1926 Div.4 F

题意

给定一个 \(7\times 7\) 的棋盘，由字符 “B” 和 “W” 组成，要求每个 “B” 左上、左下、右上、右下的四个方向不能都是 “B”，求需要改变多少个格子。

题解

只考虑对角线，那么容易发现可以按照黑白染色分别考虑行 + 列为奇数和偶数的情况。

考虑最坏的情况：整个棋盘全是 “B”，我们会发现我们只需要改变 8 个位置的格子，即 \((3,3),(3,4),(3,5),(4,3),(4,5),(5,3),(5,4),(5,5)\)，因此对于奇数和偶数的情况，答案不会太多，我们可以枚举要翻转的 \(0～4\) 个格子并判断。

时间复杂度：\(O(T(\begin{pmatrix}25\\4\end{pmatrix}\times 25 + \begin{pmatrix}25\\4\end{pmatrix}\times 24))\)

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

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

std::vector<std::array<int, 2>> odd, even;

bool valid(std::vector<std::vector<int>> &g, bool odd) {
    for (int r = 2; r < 7; r++) {
        for (int c = 2; c < 7; c++) {
            if (g[r][c] && ((r + c) % 2 == odd)) {
                if (g[r - 1][c - 1] && g[r - 1][c + 1] && g[r + 1][c + 1] &&
                    g[r + 1][c - 1]) {
                    return false;
                }
            }
        }
    }
    return true;
}

bool check(std::vector<std::vector<int>> &g, int flips_left, int idx,
           std::vector<std::array<int, 2>> &vec, int valid_val) {
    if (flips_left == 0) {
        return valid(g, valid_val);
    }
    if (idx == vec.size()) {
        return false;
    }
    bool ok = false;
    ok |= check(g, flips_left, idx + 1, vec, valid_val);
    g[vec[idx][0]][vec[idx][1]] ^= 1;
    ok |= check(g, flips_left - 1, idx + 1, vec, valid_val);
    g[vec[idx][0]][vec[idx][1]] ^= 1;
    return ok;
}

void solve() {
    std::vector<std::vector<int>> g(8, std::vector<int>(8));
    for (int i = 1; i <= 7; i++) {
        for (int j = 1; j <= 7; j++) {
            char c;
            std::cin >> c;
            g[i][j] = (c == 'B');
        }
    }
    int ans = 0;
    for (int i = 0; i <= 4; i++) {
        if (check(g, i, 0, odd, 1)) {
            ans += i;
            break;
        }
    }
    for (int i = 0; i <= 4; i++) {
        if (check(g, i, 0, even, 0)) {
            ans += i;
            break;
        }
    }
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    for (int i = 1; i <= 7; i++) {
        for (int j = 1; j <= 7; j++) {
            if ((i + j) % 2) {
                odd.push_back({i, j});
            } else {
                even.push_back({i, j});
            }
        }
    }

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

CF1926 Div.4 G

题意

给定一个树，每个节点有三种状态：P，S 和 C，其中 C 可以被看作 P 或 S，求连接 P 节点和 S 节点的边最少数量。

题解

主要问题是 C 节点如何处理，考虑树形 dp，设 \(dp_{i,0}\) 为该节点为 P 的子树的答案，\(dp_{i,1}\) 为该节点为 S 的子树的答案，那么转移有 \(dp_{i, 0 }=\sum \min(dp_{j,0},dp_{j,1} + 1),dp_{i,1} = \sum\min(dp_{j,1}, dp_{j,0} + 1)\)（针对 C 节点）。

而对于 P 节点和 S 节点，只转移自己对应的状态即可，初始化为 0 ，另一个状态初始化为 inf。

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

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

void solve() {
    int n;
    std::cin >> n;
    std::vector<std::vector<int>> adj(n + 1);
    for (int i = 2; i <= n; i++) {
        int x;
        std::cin >> x;
        adj[x].push_back(i);
        adj[i].push_back(x);
    }
    std::string s;
    std::cin >> s;
    s = " " + s;
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(2, 2e9));
    auto dfs = [&](auto dfs, int x, int fa) -> void {
        if (s[x] == 'P') {
            dp[x][0] = 0;
        } else if (s[x] == 'S') {
            dp[x][1] = 0;
        } else {
            dp[x][0] = dp[x][1] = 0;
        }
        for (auto y : adj[x]) {
            if (y == fa) {
                continue;
            }
            dfs(dfs, y, x);
            if (s[x] == 'P') {
                if (s[y] == 'C') {
                    dp[x][0] += std::min(dp[y][0], dp[y][1] + 1);
                } else if (s[y] == 'P') {
                    dp[x][0] += dp[y][0];
                } else {
                    dp[x][0] += dp[y][1] + 1;
                }
            } else if (s[x] == 'S') {
                if (s[y] == 'C') {
                    dp[x][1] += std::min(dp[y][1], dp[y][0] + 1);
                } else if (s[y] == 'P') {
                    dp[x][1] += dp[y][0] + 1;
                } else {
                    dp[x][1] += dp[y][1];
                }
            } else {
                dp[x][0] += std::min(dp[y][1] + 1, dp[y][0]);
                dp[x][1] += std::min(dp[y][0] + 1, dp[y][1]);
            }
        }
    };
    dfs(dfs, 1, 0);
    std::cout << std::min(dp[1][0], dp[1][1]) << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

ABC410 D

题意

给定一张 \(N\) 点 \(M\) 边有向图，存在边权，求 1 到 \(N\) 的所有路径（不一定是简单路径）中异或和最小的。

\(N,M\le 1000\)

题解

这种异或要么按位贪心，要么暴力，本题按位贪心是不可行的，因为可能存在环，且不一定是简单路径。数据量比较小，可以直接考虑暴力 BFS，对于每个节点使用 std::set 来存储到达该节点的所有异或和，那么对于队头的节点和异或和，如果 set 中不存在该值，就将所有邻边入队，如果存在就跳过。

考虑最坏的完全图，每个节点最多入队 \(N\) 次，因此时间复杂度为 \(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
#include <bits/stdc++.h>

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

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, M;
    std::cin >> N >> M;
    std::vector<std::vector<std::array<int, 2>>> adj(N + 1);
    for (int i = 1; i <= M; i++) {
        int x, y, w;
        std::cin >> x >> y >> w;
        adj[x].push_back({y, w});
    }
    std::vector<std::set<int>> st(N + 1);
    std::queue<std::array<int, 2>> q;
    q.push({1, 0});
    while (!q.empty()) {
        auto [x, v] = q.front();
        q.pop();
        if (st[x].find(v) != st[x].end()) {
            continue;
        }
        st[x].insert(v);
        for (auto [y, w] : adj[x]) {
            q.push({y, v ^ w});
        }
    }
    if (st[N].size() == 0) {
        std::cout << -1 << "\n";
    } else {
        std::cout << *st[N].begin() << "\n";
    }

    return 0;
}

ABC410 E

题意

你有 \(H\) 生命和 \(M\) 法力，依次对 \(N\) 个怪物消灭：消耗 \(A_i\) 生命或 \(B_i\)​ 法力。求最多能消灭多少怪物。

\(N,H,M,A_i,B_i\le 3000\)

题解

很容易想到 dp，做这题的时候我忽略了一个很重要的条件：依次消灭，不能消灭就停止。

有两种做法，第一种是比较常见的设法：设 \(dp_{i,j}\) 为有 \(i\) 生命和 \(j\) 法力时最多能消灭多少，那么转移方程显然是 \(dp_{i,j} = \max(dp_{i + A_k,j}, dp_{i,j + B_k}) + 1\)，初始均为 -inf，\(dp_{0,0} = 0\)。本题有“依次”的限制，跟背包 dp 是不一样的，若我们已知 \(dp_{i,j}\) 为 \(x\)，那么这个状态的下一个状态的 dp 值一定会更新 \(dp_{i + A_{x+1},j}, dp_{i,j+B_{x+1}}\) 为 \(x + 1\)。这样我们从小到大 dp 就不会有后效性了。

时间复杂度：\(O(HM)\)

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

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

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, H, M;
    std::cin >> N >> H >> M;
    std::vector<int> A(N + 1), B(N + 1);
    for (int i = 1; i <= N; i++) {
        std::cin >> A[i] >> B[i];
    }
    std::vector dp(H + 1, std::vector<int>(M + 1, -2e9));
    dp[0][0] = 0;
    int ans = 0;
    for (int i = 0; i <= H; i++) {
        for (int j = 0; j <= M; j++) {
            if (dp[i][j] == -2e9 || dp[i][j] == N) {
                continue;
            }
            int x = dp[i][j] + 1;
            if (i + A[x] <= H) {
                dp[i + A[x]][j] = std::max(dp[i + A[x]][j], x);
                ans = std::max(ans, x);
            }
            if (j + B[x] <= M) {
                dp[i][j + B[x]] = std::max(dp[i][j + B[x]], x);
                ans = std::max(ans, x);
            }
        }
    }
    std::cout << ans << "\n";

    return 0;
}

第二种做法是可行性 dp。最朴素的是设 \(dp_{i,j,k}\) 为前 \(i\) 个怪物，在状态为 \(i,k\) 时能否消灭，那么转移为 \(dp_{i,j,k} = dp_{i-1,j+A_{i},k}\mid dp_{i-1,j,k + B_i}\)，时间和空间复杂度都是 \(O(NHM)\)，优化空间是很显然的滚动数组优化，由此，我们可以写出以下 时间复杂度为 \(O(NHM)\) 的代码，不过无法通过：

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

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

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, H, M;
    std::cin >> N >> H >> M;
    std::vector<int> A(N + 1), B(N + 1);
    for (int i = 1; i <= N; i++) {
        std::cin >> A[i] >> B[i];
    }
    std::vector dp(H + 1, std::vector<bool>(M + 1));
    dp[H][M] = 1;
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        std::vector ndp(H + 1, std::vector<bool>(M + 1));
        for (int j = 0; j <= H; j++) {
            for (int k = 0; k <= M; k++) {
                if (j + A[i] <= H) {
                    ndp[j][k] = ndp[j][k] | dp[j + A[i]][k];
                }
                if (k + B[i] <= M) {
                    ndp[j][k] = ndp[j][k] | dp[j][k + B[i]];
                }
            }
        }
        bool ok = false;
        for (int j = 0; j <= H; j++) {
            if (ok) {
                break;
            }
            for (int k = 0; k <= M; k++) {
                if (ndp[j][k]) {
                    ans = i;
                    ok = true;
                    break;
                }
            }
        }
        if (ok == false) {
            break;
        }
        dp = ndp;
    }
    std::cout << ans << "\n";

    return 0;
}

继续优化，既然我们是可行性 dp，可以考虑 bitset 优化到 \(O(\frac{NHM}{\omega})\)。本人是第一次写 bitset，本题的原理就是开一个 std::vector<std::bitset<>()>，将 \(dp_{i,j}\leftarrow dp_{i+A_k,j} \mid dp_{i,j + B_K}\) 变成 \(dp_{i}\leftarrow dp_{i + A_k}\mid (dp_{i}>> B_k)\)，也就是将每一行一个一个转移变为第 \(i + A_k\) 行一起转移到第 \(i\) 行，通过移位操作，将第 \(B_k - 1～M\) 列一起转移到 \(1～M - B_k\) 列，同时避免了越界的情况，由于这些操作可以并行计算，对于速度非常大。还需要注意 \(H - A_k<i\le H\) 的情况，此时只能有列转移。

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 i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, H, M;
    std::cin >> N >> H >> M;
    std::vector<int> A(N + 1), B(N + 1);
    for (int i = 1; i <= N; i++) {
        std::cin >> A[i] >> B[i];
    }
    int ans = 0;
    std::vector dp(H + 1, std::bitset<3001>());
    dp[H][M] = 1;
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= H - A[i]; j++) {
            dp[j] = dp[j + A[i]] | (dp[j] >> B[i]);
        }
        for (int j = std::max(H - A[i] + 1, 0); j <= H; j++) {
            dp[j] = dp[j] >> B[i];
        }
        bool ok = false;
        for (int j = 0; j <= H; j++) {
            if (dp[j].any()) {
                ok = true;
                ans = i;
                break;
            }
        }
        if (ok) {
            ans = i;
        }
    }
    std::cout << ans << "\n";

    return 0;
}

ABC410 F

题意

给定一个字符矩阵，字符有“.”和“#”，求有多少个矩形满足内部“#”和“.”个数相同。

题解

很经典的 trick：定义 “.” 为 -1，“#” 为 1，对于只有一行的情况，也就是变成求所有区间里和为 0 的区间有多少个，这又是另一个 trick，通过前缀和处理后，将 \(pre_{r} - pre_{l - 1} = 0\) 变成 \(pre_{l - 1} = pre_{r}\) 处理。通过一个数组计数，可以 \(O(N)\) 解决。

而对于矩阵的情况，通过二维前缀和，枚举选择的行的范围，变成若干个上述情况，复杂度为 \(O(HW^2)\)，那么我们当 \(W > H\) 时交换 \(H,W\)，复杂度不会超过 \(O(N\sqrt{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
70
71
72
73
#include <bits/stdc++.h>

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

void solve() {
    int H, W;
    std::cin >> H >> W;
    std::vector<std::string> g(H + 1);
    for (int i = 1; i <= H; i++) {
        std::cin >> g[i];
        g[i] = " " + g[i];
    }
    int n = H, m = W;
    if (H > W) {
        std::swap(n, m);
    }
    std::vector a(n + 1, std::vector<int>(m + 1)),
        pre(n + 1, std::vector<int>(m + 1));
    if (n != H) {
        for (int j = 1; j <= W; j++) {
            for (int i = 1; i <= H; i++) {
                a[j][i] = g[i][j] == '.' ? 1 : -1;
            }
        }
    } else {
        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= W; j++) {
                a[i][j] = g[i][j] == '.' ? 1 : -1;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            pre[i][j] =
                a[i][j] + pre[i][j - 1] + pre[i - 1][j] - pre[i - 1][j - 1];
        }
    }
    i64 ans = 0;
    const int eps = n * m;
    std::vector<int> cnt(2 * eps + 1);
    for (int l = 1; l <= n; l++) {
        for (int r = l; r <= n; r++) {
            cnt[eps] = 1;
            for (int j = 1; j <= m; j++) {
                int x = pre[r][j] - pre[l - 1][j] + eps;
                ans += cnt[x];
                cnt[x]++;
            }
            for (int j = 1; j <= m; j++) {
                int x = pre[r][j] - pre[l - 1][j] + eps;
                cnt[x] = 0;
            }
        }
    }
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T;
    std::cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

CF1915 Div.4 G

题意

给定一张有向图，求从 1 到 \(n\) 的最短路，边的长度被定义为边权乘上路径中遇到的点权，每走到一个点可以改变或保留。

\(n,m\le 1000\)

题解

以后这种状态转换的可以想到分层图，由于每走到一个点可能换点权或者不换点权，我们就按点权分层后跑 Dijkstra 即可。

下面的代码没有 vis 数组，因此是 \(O(nm)\) 的。

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

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

void solve() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<std::array<int, 2>>> adj(n + 1);
    for (int i = 1; i <= m; i++) {
        int x, y, w;
        std::cin >> x >> y >> w;
        adj[x].push_back({y, w});
        adj[y].push_back({x, w});
    }
    std::vector<int> s(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> s[i];
    }
    std::vector<std::vector<i64>> dis(n + 1, std::vector<i64>(1e3 + 1, 3e18));
    auto dijkstra = [&](int st = 1) {
        dis[st][s[st]] = 0;
        std::priority_queue<std::array<i64, 3>, std::vector<std::array<i64, 3>>,
                            std::greater<>>
            pq;
        pq.push({0, 1, s[st]});
        while (!pq.empty()) {
            auto [_, x, b] = pq.top();
            pq.pop();
            for (auto [y, w] : adj[x]) {
                i64 d = w * b;
                if (dis[y][b] > dis[x][b] + d) {
                    dis[y][b] = dis[x][b] + d;
                    pq.push({dis[y][b], y, b});
                }
                if (dis[y][s[y]] > dis[x][b] + d) {
                    dis[y][s[y]] = dis[x][b] + d;
                    pq.push({dis[y][s[y]], y, s[y]});
                }
            }
        }
    };
    dijkstra();
    i64 ans = 3e18;
    for (int i = 1; i <= n; i++) {
        ans = std::min(ans, dis[n][s[i]]);
    }
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t = 1;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}