HDU7528 cats 的电脑中毒

传送门

Solution

设两个二进制串有 $k$ 位不同，那么它们的距离 $d=k$。设与串 $i$ 的距离为 $d_i$，题目即求使得 $\min\{d_1,d_2,d_3\}$ 最大的串。

若三个串的第 $l$ 位相同，答案串的第 $l$ 位就取不同的 01，$d_i$ 全部加 $1$。

否则第 $l$ 位上必有 $i_1,i_2$ 串相同，另外的 $i_3$ 串不同。此时可以对 $d_{i_1},d_{i_2}$ 加 $1$，或者对 $d_{i_3}$ 加 $1$。

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

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

答案即为 $\max\{1,\min\{d_1,d_2,d_3\}\}$

Code

#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;
}