CF729D Sea Battle

Galya 正在一个 $1 \times n$ 的网格上玩一维“海战”游戏。在这个游戏中，$a$ 艘战舰被放置在网格上。每艘战舰都占据连续的 $b$ 个格子。一个格子不能同时属于两艘船，但是船只之间可以相互接触。 Galya 并不知道船的位置。她可以向某些格子射击，每射击一次，会告知她该格子是否有船（这种情况称为“命中”），否则称为“未命中”。 Galya 已经进行了 $k$ 次射击，所有的结果都是未命中。 你的任务是计算，Galya 至少还需要再向多少个格子射击，才能保证无论船如何放置，至少能够命中一艘船。 保证至少存在一种合理的舰船摆放方式。

第一行包含四个正整数 $n$、$a$、$b$、$k$（$1 \le n \le 2 \cdot 10^5$，$1 \le a,b \le n$，$0 \le k \le n-1$），分别表示网格长度、舰船数量、每艘舰船的长度以及 Galya 已经射击的格子数量。 第二行包含一个长度为 $n$ 的仅由 $0$ 和 $1$ 组成的字符串。如果第 $i$ 个字符为 $1$，表示 Galya 已经射击了第 $i$ 个格子。否则她未曾射击。保证该字符串中恰好有 $k$ 个 $1$。

第一行输出最少还需射击的格子数，使得无论战舰如何摆放，至少有一艘船能够被命中。 第二行输出这些需要射击的格子的编号，每个编号只能输出一次，编号范围为 $1$ 到 $n$（从左到右编号）。 你可以按照任意顺序输出格子编号。如果有多种方案，你可以输出其中任意一种。

在第一个样例中，有一艘船。它可能在 Galya 已经射击过的格子的左边，也可能在右边。因此，至少需要再分别射击左端和右端各一个格子，共两次。 由 ChatGPT 5 翻译