Cowntact Tracing 2 (USACO Bronze 2023 December)

我们要求的是最少有多少头牛最初感染了疾病。

首先我们看到，因为疾病是在相邻的牛中间传播，所以字符串中每个连续的1组成的子串，都至少来自于一头最初的感染的牛。所以这个指引我们应该从连续的1组成的子串开始求解，我们已经有了一个结果的下限，就是这样的子串的个数。是否最终结果会比这个下限更大呢？应该是有可能的，比如我们有一个单独的1，两边都是0，那么这就限制了传播的时间只能为0，因为如果时间大于0，必然疾病就已经扩展到了更大的范围。然后这个传播时间，就使得其它更长的子串中最初需要更多头的牛。因此我们应该想办法求出这个传播时间。

所以基本思路就是通过统计每个连续1组成的子串的长度，我们来计算最长的可能传播时间 $t$ ，然后通过这个最长传播时间 $t$ ，来计算每个子串中最初最少有几头病牛。再加起来就能得到最终的答案。

具体来说：

当子串在中间时，经过时间 $t$ ，一头病牛变成 $2t+1$ 头，所以长度为 $c_i$ 的子串，对应最长传播时间为： $t_i= \frac{c_i-1}{2}$
当子串在两头时，如果病牛在最左侧或者最右侧，那么经过时间 $t$ 之后，子串长度是 $t+1$ 。所以长度为 $c_i$ 的子串，对应最长传播时间为： $t_i = c_i-1$

整体的最长传播时间 $t=\min{t_i}$ ，然后我们就可以通过 $c_i$ 和 $t$ 来计算每个子串中最初最少有几头病牛了。

ans = \sum_i \lceil \frac{c_i}{2t+1} \rceil

算法复杂度是 $\mathcal{O}(N)$ 。

#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
int n, cnt;
char s[300005];
vector<int> W;
int t = 300005;
int ans;
 
int main() {
    scanf("%d", &n);
    scanf("%s", s);
    for (int i = 0; i <= n; i++) {
        if (i < n && s[i] == '1') {
            cnt++;
        } else {
            if (cnt == 0) continue;
            W.push_back(cnt);
            if (i-cnt == 0 || i == n)   // on the side
                t = min(t, cnt-1);
            else                        // in the middle
                t = min(t, (cnt + 1) / 2 - 1);
            cnt = 0;
        }
    }
    int span = 2*t+1;
    for (int w: W) {
        ans += (w + span - 1) / span;
    }
    printf("%d\n", ans);
}