第三周训练

1. ABC 269 G - Reversible Cards 2

题意

有 \(N\) 张卡，卡正面反面各有数字 \(A_i\)，\(B_i\)，初始朝向正面
\(\sum_1^n(A_i+B_i)=M\)
你可以任意的反转卡，使得所有朝向上的数字之和为 \(K(K=1,2,...,M)\)，求最小反转次数。如果无法完成，输出 \(-1\)

做法

用 \(cnt\) 数组存下所有反转所能使得初始和变化 \(-K,...,0,...,K\) 的可用次数
然后使用 \(dp\)，将所有可能性在 \(dp\) 数组中应用，使用二进制优化

代码

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
/**
 * @author: XiaFan
 * @date: 09-20 18:59
 **/
#include <bits/stdc++.h>
using i64 = long long;

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

    int n, m;
    std::cin >> n >> m;
    std::vector<int> a(n), b(n), cnt(2 * m + 1);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i] >> b[i];
        sum += a[i];
        cnt[m + b[i] - a[i]]++;
    }

    std::vector<int> dp(2 * m + 1, n + 1);
    dp[sum] = 0;
    for (int i = 0; i <= 2 * m; i++) {
        if (cnt[i] == 0) {
            continue;
        }

        for (int j = 0; cnt[i] > 0; j++) {
            int flip = std::min(1 << j, cnt[i]);
            cnt[i] -= flip;
            int add = flip * (i - m);
            if (add >= 0) {
                for (int k = m; k - add >= 0; k--) {
                    dp[k] = std::min(dp[k], dp[k - add] + flip);
                }
            } else {
                for (int k = 0; k <= m; k++) {
                    dp[k] = std::min(dp[k], dp[k - add] + flip);
                }
            }
        }
    }

    for (int i = 0; i <= m; i++) {
        if (dp[i] > n) {
            std::cout << -1 << "\n";
        } else {
            std::cout << dp[i] << "\n";
        }
    }

    return 0;
}

2. CF 821 D2. Zero-One (Hard Version)

题意

给了a，b字符串，要用任意操作次数使得两者相等，输出最小操作代价，如果不行输出-1
每次操作，先择了l，r两个不等下表，反转两个字符量，如果两个下表相邻，代价是x，否则是y。

做法

显然如果不相等的字符有奇数个，那么不可能完成。

代码

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

using i64 = long long;

constexpr i64 inf = 1E18;

void solve() {
    int n;
    i64 x, y;
    std::cin >> n >> x >> y;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        char ch;
        std::cin >> ch;
        a[i] ^= ch - '0';
    }
    for (int i = 0; i < n; i++) {
        char ch;
        std::cin >> ch;
        a[i] ^= ch - '0';
    }

    int cnt = std::accumulate(a.begin(), a.end(), 0);
    if (cnt % 2 != 0) {
        std::cout << -1 << "\n";
        return;
    }
    std::vector<int> pos;

    for (int i = 0; i < n; i++) {
        if (a[i]) {
            pos.push_back(i);
        }
    }

    if (x >= y) {
        if (cnt != 2) {
            std::cout << (cnt / 2) * y << "\n";
            return;
        }
        if (pos[1] > pos[0] + 1) {
            std::cout << y << "\n";
            return;
        }
        i64 ans = x;
        if (n > 2) {
            ans = std::min(ans, 2 * y);
        }
        std::cout << ans << "\n";
        return;
    }

    std::vector dp(cnt, std::vector<i64>(cnt, -1));

    auto get = [&](int l, int r) -> i64 {
        if (l + 1 == r) {
            return std::min(2 * y, x);
        } else {
            return std::min(y, x * (r - l));
        } 
    };

    std::function<i64(int, int)> dfs = [&](int l, int r) -> i64 {
        if (l > r) {
            return 0;
        }
        if (dp[l][r] != -1) {
            return dp[l][r];
        }
        i64 res = 1e18;
        res = std::min(res, dfs(l + 1, r - 1) + get(pos[l], pos[r]));
        res = std::min(res, dfs(l, r - 2) + get(pos[r - 1], pos[r]));
        res = std::min(res, dfs(l + 2, r) + get(pos[l], pos[l + 1]));
        dp[l][r] = res;
        return dp[l][r];
    };

    std::cout << dfs(0, cnt - 1) << "\n";
}

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

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}