浅念づ昔夜's Blog

Like author, like book.

0%

HDU7528 cats 的电脑中毒

发表于 更新于 分类于
本文字数： 466 阅读时长 ≈ 2 分钟

传送门

Solution

设两个二进制串有 kk 位不同，那么它们的距离 d=kd=k。设与串 ii 的距离为 did_i，题目即求使得 min⁡{d1,d2,d3}\min\{d_1,d_2,d_3\} 最大的串。

若三个串的第 ll 位相同，答案串的第 ll 位就取不同的 01，did_i 全部加 11。

否则第 ll 位上必有 i1,i2i_1,i_2 串相同，另外的 i3i_3 串不同。此时可以对 di1,di2d_{i_1},d_{i_2} 加 11，或者对 di3d_{i_3} 加 11。

初始化时，记录每一位属于哪种类型（是哪一个串在这一位上与众不同）。

接下来进行 nn 次操作，每次对最小的 did_i 加 11。在此前提下，优先选择一次能加两个 did_i 的操作。

答案即为 max⁡{1,min⁡{d1,d2,d3}}\max\{1,\min\{d_1,d_2,d_3\}\}

Code

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

const int N = 2e5 + 10;

int T, n, a[4], ans, tot, sum[N];
char s[10][N];

void solve()
{
    scanf("%d", &n);
    ans = 0;
    for (int i = 1; i <= 3; i++) {
        scanf("%s", s[i] + 1);
        a[i] = sum[i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        if (s[1][i] == s[2][i] && s[1][i] == s[3][i])
            ans++;
        else if (s[1][i] == s[2][i])
            a[3]++;
        else if (s[1][i] == s[3][i])
            a[2]++;
        else
            a[1]++;
    }
    tot = a[1] + a[2] + a[3];
    while (tot) {
        --tot;
        if (sum[1] <= sum[2] && sum[1] <= sum[3] && (a[2] || a[3])) {
            if (a[2]) {
                --a[2];
                sum[1]++; sum[3]++;
            } else if (a[3]) {
                --a[3];
                sum[1]++; sum[2]++;
            }
            continue;
        } else if (sum[2] <= sum[1] && sum[2] <= sum[3] && (a[1] || a[3])) {
            if (a[1]) {
                --a[1];
                sum[2]++; sum[3]++;
            } else if (a[3]) {
                --a[3];
                sum[2]++; sum[1]++;
            }
            continue;
        } else if (sum[3] <= sum[1] && sum[3] <= sum[2] && (a[1] || a[2])) {
            if (a[1]) {
                --a[1];
                sum[2]++; sum[3]++;
            } else if (a[2]) {
                --a[2];
                sum[3]++; sum[1]++;
            }
            continue;
        }
        if (sum[1] <= sum[2] && sum[1] <= sum[3]) {
            --a[1]; ++sum[1];
        } else if (sum[2] <= sum[1] && sum[2] <= sum[3]) {
            --a[2]; ++sum[2];
        } else if (sum[3] <= sum[1] && sum[3] <= sum[2]) {
            --a[3]; ++sum[3];
        }
    }
    printf("%d\n", max(1, ans + min(sum[1], min(sum[2], sum[3]))));
} 

int main()
{
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}