Cowntact Tracing 2

题意

有 $N$ 头牛排成一行。最开始有若干头牛感染。

每天晚上，已经感染的牛会把疾病传给左右相邻的牛；感染后会一直保持感染。

过了未知的若干天后，给出一个长度为 $N$ 的 01 串，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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 16:17
 * update_at: 2026-07-11 16:18
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n;
string s;
int seg_len[MAXN];
bool seg_edge[MAXN];
int seg_cnt;

void collect_segments() {
    seg_cnt = 0;
    int i = 0;
    while (i < n) {
        if (s[i] == '0') {
            i++;
            continue;
        }

        int start = i;
        while (i < n && s[i] == '1') {
            i++;
        }
        int finish = i - 1;

        seg_cnt++;
        seg_len[seg_cnt] = finish - start + 1;
        seg_edge[seg_cnt] = (start == 0 || finish == n - 1);
    }
}

bool can_use_window(int window) {
    for (int i = 1; i <= seg_cnt; i++) {
        int len = seg_len[i];
        int allowed;

        if (seg_edge[i]) {
            allowed = 2 * len - 1;
        } else if (len % 2 == 0) {
            allowed = len - 1;
        } else {
            allowed = len;
        }

        if (window > allowed) return false;
    }
    return true;
}

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

    cin >> n;
    cin >> s;

    collect_segments();
    if (seg_cnt == 0) {
        cout << 0 << '\n';
        return 0;
    }

    int ans = n;

    // 小数据暴力：枚举所有可能的传播窗口长度 2D+1。
    for (int window = 1; window <= 2 * n + 1; window += 2) {
        if (!can_use_window(window)) continue;

        int now = 0;
        for (int i = 1; i <= seg_cnt; i++) {
            now += (seg_len[i] + window - 1) / window;
        }
        ans = min(ans, now);
    }

    cout << ans << '\n';

    return 0;
}

如果过了 $D$ 天，那么一头初始感染牛最多会影响从它向左 $D$ 个位置、向右 $D$ 个位置，也就是一个长度为：

2D+1

的窗口。

于是最终的每一段连续 1，都需要用若干个这样的窗口覆盖。为了让初始感染牛数量最少，窗口长度应该尽量大。

现在问题变成：最终能使用的最大窗口长度是多少？

记一段连续 1 的长度为 len。

内部奇数段

如果这段 1 左右两边都有 0，并且 len 是奇数，那么最大窗口可以正好等于 len。

text

1
2
30 1 1 1 0
  <--->
   len = 3

内部偶数段

窗口长度一定是奇数，也就是 $2D+1$ 。如果内部段长度是偶数，不可能由一个窗口刚好覆盖整段，否则会多感染一侧的 0。

所以内部偶数段的最大窗口只能是 len - 1。

text

1
20 1 1 1 1 0
  len = 4, 最大窗口 = 3

边界段

如果一段 1 贴着最左端或最右端，传播可以从边界向内截断。长度为 len 的边界段，最大窗口可以达到：

2 \times len - 1

例如最左边有三个 1：

text

11 1 1 0 ...

可以理解为初始感染牛就在第一个位置，向左的传播被边界挡住，所以允许更大的天数。

因此，对每一段连续 1 计算它允许的最大窗口长度，取所有段的最小值作为全局窗口 window。

最后每段长度为 len 的连续 1 需要：

\left\lceil \frac{len}{window} \right\rceil

头初始感染牛。把所有段加起来就是答案。

代码

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 16:17
 * update_at: 2026-07-11 16:18
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300005;

int n;
string s;
int seg_len[MAXN];
bool seg_edge[MAXN];
int seg_cnt;

void collect_segments() {
    seg_cnt = 0;
    int i = 0;
    while (i < n) {
        if (s[i] == '0') {
            i++;
            continue;
        }

        int start = i;
        while (i < n && s[i] == '1') {
            i++;
        }
        int finish = i - 1;

        seg_cnt++;
        seg_len[seg_cnt] = finish - start + 1;
        seg_edge[seg_cnt] = (start == 0 || finish == n - 1);
    }
}

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

    cin >> n;
    cin >> s;

    collect_segments();
    if (seg_cnt == 0) {
        cout << 0 << '\n';
        return 0;
    }

    int window = 2 * n + 1;
    for (int i = 1; i <= seg_cnt; i++) {
        int len = seg_len[i];
        int allowed;

        if (seg_edge[i]) {
            // 边界段可以由边界上的初始感染牛向内传播。
            allowed = 2 * len - 1;
        } else if (len % 2 == 0) {
            // 内部偶数段不能由一个奇数长度窗口完全覆盖。
            allowed = len - 1;
        } else {
            allowed = len;
        }

        window = min(window, allowed);
    }

    int ans = 0;
    for (int i = 1; i <= seg_cnt; i++) {
        ans += (seg_len[i] + window - 1) / window;
    }

    cout << ans << '\n';

    return 0;
}

复杂度

只需要扫描字符串收集连续 1 段，再扫描这些段统计答案。

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

总结

本题的核心是把“未知天数”转化成“未知窗口长度”。

窗口越大，需要的初始感染牛越少，所以先找所有连续 1 段共同允许的最大窗口，再用这个窗口覆盖每一段。

目录

题意

思路

内部奇数段

内部偶数段

边界段

代码

复杂度

总结