2 分钟阅读

题目描述

小红定义一个 01 矩阵是合法的，当且仅当其中每个由 0 组成的四连通块大小都恰好为 3，并且每个由 1 组成的四连通块大小也都恰好为 3。

现在给定一个大小为 $2 \times n$ 的 01 矩阵。你每次可以修改一个字符，将 1 改成 0，或将 0 改成 1。

请你求出，最少需要修改多少个字符，才能使这个矩阵变成合法矩阵。如果无论如何都无法变成合法矩阵，输出 $-1$。

这里的连通块采用四连通定义，也就是说两个格子只有在共边时才算相邻。

输入描述

第一行输入一个整数 $n$（$1 \le n \le 2 \times 10^5$）。

接下来两行，每行输入一个长度为 $n$ 的 01 字符串，表示矩阵的两行。

输出描述

输出一个整数，表示最少修改次数。

如果无解，输出 $-1$。

示例

输入

1
2
3

6
110110
100100

输出

1

0

说明

原矩阵本身已经合法。其中左侧的 3 个 1 构成一个大小为 3 的连通块，右侧的 3 个 1 也构成一个大小为 3 的连通块。所有 0 的连通块大小同样都恰好为 3，因此不需要修改。

分析与思路

初步探路

看到这道题，我最初尝试对其进行转换：将 1 映射为 1，将 0 映射为 $-1$。为什么这么做？这来源于 Codeforces Round 1097 (Div. 2, Based on Zhili Cup 2026) 的一道 C 题，不过这其实和本题没什么关系。

首先很容易知道 $3 \mid n$（即 $n$ 必须是 3 的倍数），否则无解。接下来需要讨论合法连通块的形状。最初我遗漏了一个重要情况——横着的 111 或者 000 也是符合要求的连通块，这很关键。我当时只考虑了 L 型块，但事实上横排也是合法的。

如果只考虑 L 型，我们会陷入一个误区：认为每一列的和必然是 $-1, 0, 1, -1, 0, 1, \dots$ 或者 $1, 0, -1, 1, 0, -1, \dots$ 这样循环的模式。但这样的推理会遗漏很多可行的情况，因为它无法处理每一列都是 0 的情况。例如，上层是 111000 而下层是 000111，根据上述映射规则和推论会得到错误的答案。核心原因就在于我们忽略了横排摆放也是合法的。

补全思考

明确了连通块可以呈 “L” 型或 “一” 型（横条）后，之前的映射法则显然不再适用。不过之前的思路也并非毫无用处：由于并不存在真正独立的块，我们仍然可以从第一个 $2 \times 3$ 块入手。但很快会发现，只考虑一个块对我们没有任何帮助，我们需要考虑 两个块 之间的关系。为什么呢？还记得”一”型的情况吗？在这种形状下，天然就需要考虑两个 $2 \times 3$ 块之间的拼接。

如果不考虑左右边界，一个 $2 \times 3$ 块总共有以下 6 种合法的形态：

a1: `110` / `100`   a2: `100` / `110`
b1: `011` / `001`   b2: `001` / `011`
c1: `111` / `000`   c2: `000` / `111`

注意，这里只用了三个字母来命名。为什么会这样分组？先思考一下相邻块的约束关系。

根据约束规则，从第一个块出发：

  • 如果第一个块是 a1，那么第二个块只能是 a1 或 a2；
  • 如果第一个块是 a2，第二个块也只能是 a1 或 a2（a1 和 a2 本质上是上下翻转的关系，根据对称性可快速得到）。
  • 同理，b1 后面只能是 b1 或 b2，b2 后面只能是 b1 或 b2。
  • 而对于 c1 和 c2，c1 后面只能是 c2，c2 后面只能是 c1（必须交替出现）。

由此可知，整个 $2 \times n$ 矩阵只能由以下三种模式之一构成：

  1. a 模式：a1 和 a2 的混合（每个 $2 \times 3$ 块独立选择 a1 或 a2）；
  2. b 模式：b1 和 b2 的混合（每个 $2 \times 3$ 块独立选择 b1 或 b2）；
  3. c 模式：c1 和 c2 交替出现（不能混合，必须严格交替）。

因此，我们可以分别枚举每个 $2 \times 3$ 块变成上述某种合法形态所需的修改次数，然后取总和最小的方案。对于 a 模式和 b 模式，每个 $2 \times 3$ 块只需在两种候选形态中取修改次数更少者；对于 c 模式，则需按交替规则计算总修改代价。

代码

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 namespace std;

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

    int n;
    cin >> n;
    string s1, s2;
    cin >> s1 >> s2;

    if (n % 3) {
        cout << -1 << '\n';
        return 0;
    }

    auto calc = [&](int left, const string& top, const string& bot) {
        int res = 0;
        for (int k = 0; k < 3; ++k) {
            if (s1[left + k] != top[k]) res++;
            if (s2[left + k] != bot[k]) res++;
        }
        return res;
    };

    int m = n / 3;
    int costA = 0, costB = 0, costC0 = 0, costC1 = 0;

    for (int i = 0; i < m; ++i) {
        int l = i * 3;

        int a1 = calc(l, "110", "100");
        int a2 = calc(l, "100", "110");
        costA += min(a1, a2);

        int b1 = calc(l, "011", "001");
        int b2 = calc(l, "001", "011");
        costB += min(b1, b2);

        int c1 = calc(l, "111", "000");
        int c2 = calc(l, "000", "111");

        if (i % 2 == 0) {
            costC0 += c1;
            costC1 += c2;
        } else {
            costC0 += c2;
            costC1 += c1;
        }
    }

    int ans = min({costA, costB, costC0, costC1});
    cout << ans << '\n';

    return 0;
}

猜您还喜欢

周期

2 分钟阅读

题目描述