[NOIP2024] 编辑字符串

GitHub 跳转原题关系图返回列表

把连续可交换位置压成区间容量，分别贪心匹配同为 1 和同为 0 的最大数量。

OJ: luogu

题目 ID: P11361

难度:普及+/提高

标签:字符串贪心区间

日期: 2026-06-22 19:01

题意

有两个长度为 n 的二进制字符串 s1, s2。每个字符串还有一个限制串 t：t[i]=1 表示这个位置的字符可以参与相邻交换，t[i]=0 表示不能参与交换。

可以分别对两个字符串做任意多次合法相邻交换，问最终最多有多少个位置满足两个字符串字符相同。

思路

先看一个小数据暴力：枚举每个可交换连续段的所有最终排列，再枚举两个字符串的最终形态并比较。

cpp

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// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

int T, n;
string s1, s2, t1, t2;
vector<string> final_a, final_b;

void build_finals_dfs(const string &s, const string &t, int pos, string current, vector<string> &result) {
    if (pos == n) {
        result.push_back(current);
        return;
    }

    if (t[pos] == '0') {
        build_finals_dfs(s, t, pos + 1, current + s[pos], result);
        return;
    }

    int end_pos = pos;
    int count_one = 0;
    while (end_pos < n && t[end_pos] == '1') {
        count_one += s[end_pos] == '1';
        end_pos++;
    }

    int len = end_pos - pos;
    int total = 1 << len;
    for (int mask = 0; mask < total; mask++) {
        int bits = 0;
        for (int i = 0; i < len; i++) {
            if (mask & (1 << i)) {
                bits++;
            }
        }
        if (bits != count_one) {
            continue;
        }

        string next_string = current;
        for (int i = 0; i < len; i++) {
            if (mask & (1 << i)) {
                next_string.push_back('1');
            } else {
                next_string.push_back('0');
            }
        }
        build_finals_dfs(s, t, end_pos, next_string, result);
    }
}

int calc_score(const string &a, const string &b) {
    int score = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == b[i]) {
            score++;
        }
    }
    return score;
}

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

    cin >> T;
    while (T--) {
        cin >> n;
        cin >> s1 >> s2 >> t1 >> t2;

        final_a.clear();
        final_b.clear();

        build_finals_dfs(s1, t1, 0, "", final_a);
        build_finals_dfs(s2, t2, 0, "", final_b);

        int ans = 0;
        for (int i = 0; i < (int)final_a.size(); i++) {
            for (int j = 0; j < (int)final_b.size(); j++) {
                ans = max(ans, calc_score(final_a[i], final_b[j]));
            }
        }

        cout << ans << '\n';
    }

    return 0;
}

暴力的瓶颈在于，一个长的可交换段会有很多种排列。

关键观察是：一个连续可交换段内，靠相邻交换可以得到任意排列。对于二进制串来说，这一段最终只需要保留两个信息：

text

1区间 [l,r]，以及其中 1 的数量 cnt

不能交换的位置就看作长度为 1 的段。

先只考虑“两个字符串同为 1”的位置数。对 s1 和 s2 分别拆段后，每段都是一个区间容量 [l,r,cnt]，表示这个区间里可以安排 cnt 个 1。

然后用双指针从左到右匹配两个段：

当前两段的重叠部分长度为 len；
能同时放 1 的数量为 min(len, rest1, rest2)；
匹配后扣掉两边剩余的 1；
哪一段右端点更靠左，就移动哪一侧指针。

为什么可以贪心？因为当前重叠区间一旦错过，之后至少有一侧指针右移，这段位置不会再回来。能在这里匹配的目标字符尽量匹配，不会让后面的机会变差。

同为 0 的数量也可以用同一个方法求：把两个字符串的 0/1 取反，原来的 0 就变成目标字符 1。

所以答案是：

text

1最大同为 1 的数量 + 最大同为 0 的数量

代码

cpp

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
107
108
109
110
111
112
113
114
115#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

struct Block {
    int left, right;
    int count_one;
};

int T, n;
string s1, s2, t1, t2;
Block block_a[MAXN], block_b[MAXN];
int cnt_a, cnt_b;

void build_blocks(const string &s, const string &t, Block block[], int &cnt, bool flip_bit) {
    cnt = 0;
    int i = 0;

    while (i < n) {
        if (t[i] == '0') {
            int value = s[i] - '0';
            if (flip_bit) {
                value ^= 1;
            }

            cnt++;
            block[cnt].left = i + 1;
            block[cnt].right = i + 1;
            block[cnt].count_one = value;
            i++;
        } else {
            int j = i;
            int count_one = 0;
            while (j < n && t[j] == '1') {
                int value = s[j] - '0';
                if (flip_bit) {
                    value ^= 1;
                }
                count_one += value;
                j++;
            }

            cnt++;
            block[cnt].left = i + 1;
            block[cnt].right = j;
            block[cnt].count_one = count_one;
            i = j;
        }
    }
}

int count_same_one(bool flip_bit) {
    build_blocks(s1, t1, block_a, cnt_a, flip_bit);
    build_blocks(s2, t2, block_b, cnt_b, flip_bit);

    int i = 1, j = 1;
    int rest_a = block_a[1].count_one;
    int rest_b = block_b[1].count_one;
    int ans = 0;

    while (i <= cnt_a && j <= cnt_b) {
        int left = max(block_a[i].left, block_b[j].left);
        int right = min(block_a[i].right, block_b[j].right);

        if (left <= right) {
            int len = right - left + 1;
            int take = min(len, min(rest_a, rest_b));
            ans += take;
            rest_a -= take;
            rest_b -= take;
        }

        if (block_a[i].right < block_b[j].right) {
            i++;
            if (i <= cnt_a) {
                rest_a = block_a[i].count_one;
            }
        } else if (block_a[i].right > block_b[j].right) {
            j++;
            if (j <= cnt_b) {
                rest_b = block_b[j].count_one;
            }
        } else {
            i++;
            j++;
            if (i <= cnt_a) {
                rest_a = block_a[i].count_one;
            }
            if (j <= cnt_b) {
                rest_b = block_b[j].count_one;
            }
        }
    }

    return ans;
}

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

    cin >> T;
    while (T--) {
        cin >> n;
        cin >> s1 >> s2 >> t1 >> t2;

        int same_one = count_same_one(false);
        int same_zero = count_same_one(true);

        cout << same_one + same_zero << '\n';
    }

    return 0;
}

复杂度

每次拆段和匹配都是 $O(n)$ ，统计同为 1 和同为 0 各做一次。

总时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ 。

总结

本题的关键是不要真的模拟相邻交换。连续可交换段可以任意重排，所以只需要把它压成“区间 + 目标字符数量”。

之后问题变成两个区间容量序列的最大重叠匹配，用双指针贪心即可。统计 1 做一次，取反后统计 0 再做一次，二者相加就是最大相同位置数。

P11361 [NOIP2024] 编辑字符串

题目描述

小 M 有两个长度为 $n$ 且字符集为 $\{0, 1\}$ 的字符串 $s_1, s_2$ 。

小 M 希望两个字符串中对应位置字符相同的出现次数尽可能多，即满足 $s_{1,i} = s_{2,i}$ 的 $i(1 \leq i \leq n)$ 尽可能多。为此小 M 有一个字符串编辑工具，这个工具提供的基本操作是在一个字符串中交换两个相邻的字符。为了保持字符串的可辨识性，规定两个字符串中的部分字符不能参与交换。小 M 可以用工具对 $s_1$ 或 $s_2$ 进行多次字符交换，其中可以参与交换的字符能够交换任意多次。

现在小 M 想知道，在使用编辑工具后，两个字符串中对应位置字符相同的出现次数最多能有多少。

输入格式

本题包含多组测试数据。

输入的第一行包含一个整数 $T$ ，表示测试数据的组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

第一行包含一个整数 $n$ ，表示字符串长度。
第二行包含一个长度为 $n$ 且字符集为 $\{0, 1\}$ 的字符串 $s_1$ 。
第三行包含一个长度为 $n$ 且字符集为 $\{0, 1\}$ 的字符串 $s_2$ 。
第四行包含一个长度为 $n$ 且字符集为 $\{0, 1\}$ 的字符串 $t_1$ ，其中 $t_{1,i}$ 为 $1$ 表示 $s_{1,i}$ 可以参与交换， $t_{1,i}$ 为 $0$ 表示 $s_{1,i}$ 不可以参与交换。
第五行包含一个长度为 $n$ 且字符集为 $\{0, 1\}$ 的字符串 $t_2$ ，其中 $t_{2,i}$ 为 $1$ 表示 $s_{2,i}$ 可以参与交换， $t_{2,i}$ 为 $0$ 表示 $s_{2,i}$ 不可以参与交换。

输出格式

对于每组测试数据输出一行，包含一个整数，表示对应的答案。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

【样例 1 解释】

最开始时， $s_1 = \tt{011101}$ ，第 $4$ 和第 $6$ 个字符不能参与交换； $s_2 = \tt{111010}$ ，第 $2$ 和第 $5$ 个字符不能参与交换。

考虑如下操作：先交换 $s_{1,1}$ 与 $s_{1,2}$ 得到 $s_1 = \tt{101101}$ ，再交换 $s_{1,2}$ 与 $s_{1,3}$ 得到 $s_1 = \tt{110101}$ ，最后交换 $s_{2,3}$ 与 $s_{2,4}$ 得到 $s_2 = \tt{110110}$ 。此时 $s_1$ 与 $s_2$ 的前 $4$ 个位置上的字符都是相同的。可以证明不存在更好的方案，故输出 $4$ 。

【样例 2 解释】

见附件的 edit/edit2.in 与 edit/edit2.ans。

该样例共有 $10$ 组测试数据，其中第 $i(1 \leq i \leq 10)$ 组测试数据满足数据范围中描述的测试点 $2i - 1$ 的限制。

【数据范围】

对于所有的测试数据，保证： $1 \leq T \leq 10$ ， $1 \leq n \leq 10^5$ 。

::cute-table{tuack}

测试点编号	$n\leq$	特殊性质
$1\sim 4$	$10$	无
$5,6$	$10^3$	A
$7,8$	$10^5$	^
$9,10$	$10^3$	B
$11,12$	$10^5$	^
$13,14$	$10^3$	C
$15,16$	$10^5$	^
$17,18$	$10^3$	无
$19,20$	$10^5$	^

特殊性质 A：保证 $s_1$ 的所有字符相同。
特殊性质 B：保证 $t_1 = t_2$ 。
特殊性质 C：保证 $t_1$ 和 $t_2$ 中各自恰有一个字符 $\tt 0$ 。

[NOIP2024] 编辑字符串

目录

题意

思路

代码

复杂度

总结