Moo Language School 的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题给出 $n$ ~n~ 块地与每个农场的大小 $k$ ~k~，每 $k$ ~k~ 块连续的地构成一个农场；Farmer John 需要在每个农场至少建一所学校，并让建在 Farmer Nhoj 所属地上的学校次数尽可能少。核心结论是答案为「Farmer Nhoj 拥有该农场全部 $k$ ~k~ 块地」的农场个数，只需把二进制串按长度 $k$ ~k~ 分块，统计全为 1 的块数。

分析

核心观察

学校可以建在任意一块地上，而题目只要求「每个农场至少有一所学校」，一所学校只服务它所在的那个农场，因此各个农场的代价彼此独立，总代价等于各农场代价之和。对单个农场而言：只要农场内存在一块不属于 Farmer Nhoj 的地，就能把学校建在那里而不产生任何代价；只有当农场内的 $k$ ~k~ 块地全部属于 Farmer Nhoj 时，才不得不付费建一次。

思路

先明确一座农场对应哪些地块。由题面，第 $i$ ~i~ 块地属于第 $\lceil i/k \rceil$ ~\lceil i/k \rceil~ 个农场，于是第 $j$ ~j~ 个农场恰好由下标

$\displaystyle (j-1)k + 1,\ (j-1)k + 2,\ \ldots,\ jk$

这 $k$ ~k~ 块连续的地组成，整个串共分成 $n/k$ ~n/k~ 个农场。

由于每个农场至少要有一所学校，且一所学校只覆盖它所在的那一个农场，最优策略可以对每个农场单独决定：

若该农场的 $k$ ~k~ 块地中存在某块地 $i$ ~i~ 满足 $s_i = 0$ ~s_i = 0~，就把学校建在这块地上。该农场满足了要求，而这次建造没有落在 Farmer Nhoj 的地上，代价为 $0$ ~0~。
若该农场的 $k$ ~k~ 块地全部满足 $s_i = 1$ ~s_i = 1~，则农场内任何一块地都属于 Farmer Nhoj，学校无论建在哪里都要付费；建一所即可，代价为 $1$ ~1~。

因此题目的答案就是「 $s$ ~s~ 按长度 $k$ ~k~ 分块后全为 1 的块数」，也就是 Farmer Nhoj 拥有该农场全部 $k$ ~k~ 块地的农场个数。实现上无需任何数据结构：从下标 $0$ ~0~ 开始每 $k$ ~k~ 个字符检查一段，判断段内是否出现 0，没出现就让计数器加 $1$ ~1~。每个字符至多被检查一次，总工作量与输入串长同阶。

具体示例

样例共 $6$ ~6~ 组测试用例，逐组分块验算如下（1 表示该块地归 Farmer Nhoj）：

用例	$n$ ~n~	$k$ ~k~	$s$ ~s~	按 $k$ ~k~ 分块	全 `1` 的块数
$1$ ~1~	$8$ ~8~	$2$ ~2~	`10011100`	`10`，`01`，`11`，`00`	$1$ ~1~
$2$ ~2~	$5$ ~5~	$1$ ~1~	`11111`	`1`，`1`，`1`，`1`，`1`	$5$ ~5~
$3$ ~3~	$8$ ~8~	$4$ ~4~	`01111110`	`0111`，`1110`	$0$ ~0~
$4$ ~4~	$5$ ~5~	$1$ ~1~	`00101`	`0`，`0`，`1`，`0`，`1`	$2$ ~2~
$5$ ~5~	$4$ ~4~	$4$ ~4~	`1101`	`1101`	$0$ ~0~
$6$ ~6~	$4$ ~4~	$4$ ~4~	`1111`	`1111`	$1$ ~1~

得到的答案依次为 $1, 5, 0, 2, 0, 1$ ~1, 5, 0, 2, 0, 1~，与样例输出完全一致。

逐组核对细节：第 $1$ ~1~ 组的分块依次为 10、01、11、00，前两个与最后一个都含 0，可以在 0 上免费建校；只有分块 11 全归 Farmer Nhoj，必须付费一次，答案 $1$ ~1~。题面给出的方案是在第 $2, 3, 5, 7$ ~2, 3, 5, 7~ 块地上各建一所（每个农场恰好一所），其中只有第 $5$ ~5~ 块地（即 11 中的第一块）归 Farmer Nhoj，同样印证答案为 $1$ ~1~。第 $2$ ~2~ 组 $k = 1$ ~k = 1~，每个农场只有一块地且全为 1， $5$ ~5~ 个农场全部要付费。第 $3$ ~3~ 组的两个分块 0111、1110 各含一个 0，都有免费的选址，答案 $0$ ~0~。第 $4$ ~4~ 组同样是 $k = 1$ ~k = 1~，串 00101 中恰有 $2$ ~2~ 个 1，对应 $2$ ~2~ 个必须付费的农场。第 $5$ ~5~ 组唯一的农场 1101 含 0，可以免费建校，答案 $0$ ~0~；第 $6$ ~6~ 组唯一的农场 1111 全归 Farmer Nhoj，答案 $1$ ~1~。

算法步骤

读入测试用例数量 t。
对每个测试用例读入 n、k 与长度为 n 的二进制串 s，令计数器 ans 为 $0$ ~0~。
从 $0$ ~0~ 到 $n/k - 1$ ~n/k - 1~ 枚举块编号 b，检查 s 中下标区间 $[bk, (b+1)k)$ ~[bk, (b+1)k)~ 内的字符。
若该区间内没有出现 0（即整块都是 1），令 ans 加 $1$ ~1~。
输出 ans。

复杂度分析

时间： $O(\sum n)$ ~O(\sum n)~。每组测试用例只把它的串扫描一遍，串长最大为 $20$ ~20~、测试组数最大为 $10^4$ ~10^4~，总扫描量不超过 $2 \times 10^5$ ~2 \times 10^5~ 个字符。
空间： $O(n)$ ~O(n)~。只需要存储当前测试用例的字符串；除输入本身外仅用若干整型变量，附加空间为 $O(1)$ ~O(1)~。

实现注意事项

判定的单位是「整块 $k$ ~k~ 块地」，而不是「块内含有 1」。例如 10 含有一个 1，但这个农场仍可免费建校，不能把答案加 $1$ ~1~。
边界情形： $k = 1$ ~k = 1~ 时每个农场只有一块地，答案等于串中 1 的个数； $k = n$ ~k = n~ 时整个串就是一个农场，答案只能是 $0$ ~0~ 或 $1$ ~1~。
全 0 串的答案为 $0$ ~0~（每个农场都能免费建校）；全 1 串的答案为 $n/k$ ~n/k~；二者分别是答案的最小值与最大值。
数据规模为 $t \le 10^4$ ~t \le 10^4~、每串长度 $n \le 20$ ~n \le 20~，读入量不大但行数多，C++ 中应关闭同步流或用 scanf 读入，Python 中应一次性 read().split() 后顺序取用，避免逐行输入的额外开销。
C++ 中用 s[i] == '0' 判断字符；Python 中把串按 bytes 取出后可用 b"0" not in s[l:r] 直接判断，无需解码成文本。

源代码

#include <iostream>
#include <string>

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

    int t;
    std::cin >> t;

    while (t--) {
        int n, k;
        std::cin >> n >> k;

        std::string s;
        std::cin >> s;

        // 答案为「整个农场（k 块连续的地）都归 Farmer Nhoj 所有」的农场个数：
        // 只要农场里有一块地不属于他，就把学校建在那块地上，代价为 0。
        int ans = 0;
        for (int b = 0; b < n / k; ++b) {
            bool allNhoj = true;
            for (int i = b * k; i < (b + 1) * k; ++i) {
                if (s[i] == '0') {
                    allNhoj = false;
                    break;
                }
            }
            if (allNhoj) {
                ++ans;
            }
        }

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

    return 0;
}

import sys


def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    pos = 1
    out = []

    for _ in range(t):
        n = int(data[pos])
        k = int(data[pos + 1])
        s = data[pos + 2]
        pos += 3

        ans = 0
        for b in range(n // k):
            if b"0" not in s[b * k:(b + 1) * k]:
                ans += 1
        out.append(str(ans))

    sys.stdout.write("\n".join(out) + "\n")


main()

目前没有评论。