A16657 | Notelock
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
Teto 正在玩热门音游 osu!。这个游戏可以用一个二进制字符串 $s$（长度为 $n$）和一个正整数 $k$ 来描述，其中会依次发生以下事情：
- 你可以选择字符串 $s$ 中的一些位置进行保护。
- 然后对于每一个 $i$（$1 \le i \le n$），Teto 按顺序可以将 $s_i$ 变为 $0$，如果满足以下所有条件：
- $s_i = 1$；
- $s_i$ 没有被保护；
- 前 $k-1$ 个元素中没有 $1$。更形式化地说，$s_{\max(1, i-k+1)},\ldots,s_{i-1}$ 中没有出现 $1$。
你不喜欢 Teto（出于某些原因）。所以你想要让她无法改变 $s$，即 $s$ 保持不变，请问你最少需要保护多少个位置？
$^*$ 一个二进制字符串仅包含字符 $0$ 和 $1$。
- 你可以选择字符串 $s$ 中的一些位置进行保护。
- 然后对于每一个 $i$（$1 \le i \le n$），Teto 按顺序可以将 $s_i$ 变为 $0$，如果满足以下所有条件：
- $s_i = 1$；
- $s_i$ 没有被保护；
- 前 $k-1$ 个元素中没有 $1$。更形式化地说，$s_{\max(1, i-k+1)},\ldots,s_{i-1}$ 中没有出现 $1$。
你不喜欢 Teto（出于某些原因）。所以你想要让她无法改变 $s$，即 $s$ 保持不变，请问你最少需要保护多少个位置？
$^*$ 一个二进制字符串仅包含字符 $0$ 和 $1$。
输入格式
输入包含多组测试用例。第一行为测试用例个数 $t$（$1 \le t \le 100$）。接下来每组测试用例如下：
每组测试的第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 1000$；$2 \le k \le n$），分别表示字符串的长度和 $k$ 的值。
每组测试的第二行为一个长度为 $n$ 的二进制字符串 $s$，仅包含字符 $0$ 和 $1$。
所有测试用例中 $n$ 的总和不超过 $1000$。
每组测试的第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 1000$；$2 \le k \le n$），分别表示字符串的长度和 $k$ 的值。
每组测试的第二行为一个长度为 $n$ 的二进制字符串 $s$，仅包含字符 $0$ 和 $1$。
所有测试用例中 $n$ 的总和不超过 $1000$。
输出格式
每组测试用例，输出一个整数，表示你需要保护的最少位置数，才能使 Teto 无法改变字符串。
输入输出样例
输入 #1
9 2 2 11 6 6 100001 5 3 10000 7 2 1010101 7 4 0000001 3 3 010 3 2 011 7 4 1001001 8 3 00000000
输出 #1
1 1 1 4 1 1 1 1 0
对于第一个测试用例，你可以保护第一个元素，此时 $s = \mathtt{\color{red}{1}1}$。Teto 无法改变 $s_1$，因为它已被保护，同时也无法改变 $s_2$，因为 $s_1 = 1$。可以证明这是最优方案。
对于第二个测试用例，你只需要保护第一个元素，此时 $s = \color{red}{\mathtt{1}}\mathtt{00001}$。Teto 无法改变 $s_1$，因为它被保护；也无法改变 $s_6$，因为在前 $k-1$ 个元素中存在 $1$（$\color{blue}{\mathtt{10000}}\mathtt{1}$）。
对于第四个测试用例，你需要保护 $s_1,s_3,s_5,s_7$，此时 $s = \mathtt{\color{red}{1}0\color{red}{1}0\color{red}{1}0\color{red}{1}}$。可以证明这是最优解。例如，如果你没有保护 $s_3$，那么 Teto 可以将其改为 $0$（$\mathtt{\color{red}{1}\color{blue}{0}10\color{red}{1}0\color{red}{1}}$）。
对于第二个测试用例，你只需要保护第一个元素，此时 $s = \color{red}{\mathtt{1}}\mathtt{00001}$。Teto 无法改变 $s_1$，因为它被保护；也无法改变 $s_6$，因为在前 $k-1$ 个元素中存在 $1$（$\color{blue}{\mathtt{10000}}\mathtt{1}$）。
对于第四个测试用例，你需要保护 $s_1,s_3,s_5,s_7$，此时 $s = \mathtt{\color{red}{1}0\color{red}{1}0\color{red}{1}0\color{red}{1}}$。可以证明这是最优解。例如，如果你没有保护 $s_3$，那么 Teto 可以将其改为 $0$（$\mathtt{\color{red}{1}\color{blue}{0}10\color{red}{1}0\color{red}{1}}$）。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？