击中战舰
李华在玩一款叫做《海战》的小游戏，下面是游戏介绍。
给定一个 $1 \times n$ 的方格矩阵，方格从左到右依次编号为 $1 \sim n$。
在这个方格矩阵中，隐藏着 $a$ 个战舰。
每个战舰都占据 $b$ 个连续的方格，每个方格最多只能被一个战舰占据。
每个战舰的具体位置未知。
玩家的任务就是在这种情况下，向一些方格发动精确打击，如果受到精确打击的方格被某个战舰占据着，则视为击中该战舰。
李华已经向 $k$ 个方格发动了精确打击，不幸的是，一个战舰都没有击中。
请你计算，他至少还需要向多少个方格发动精确打击，才能确保自己可以至少击中一个战舰。
请给出一个具体方案。
输入格式
第一行包含 $4$ 个整数 $n,a,b,k$。
第二行包含一个长度为 $n$ 的 $01$ 字符串，如果第 $i$ 个字符为 $1$，则表示第 $i$ 个方格已经受到了精确打击，如果第 $i$ 个字符为 $0$，则表示第 $i$ 个方格还未受到精确打击。保证字符 $1$ 恰好出现 $k$ 次。
输出格式
第一行输出李华还需要发动精确打击的最少方格数量。
第二行输出李华还需要发动精确打击的方格的具体编号，具体输出顺序随意。
如果方案不唯一，输出任意合理方案均可。
数据范围
前 $3$ 个测试点满足 $1 \leq n \leq 13$。
所有测试点满足 $1 \leq n \leq 2 \times {10}^{5}$，$1 \leq a,b \leq n$，$0 \leq k \leq n−1$。
输入样例1：
5 1 2 1 00100
输入样例2：
13 3 2 3 1000000010001
输出样例2：
2 7 11
解题思路
比赛的时候没想出来，或者说思路跑歪了。
题目问最少攻击多少次可以至少攻击到一艘战舰，这个问题等价于最少攻击多少次使得空地最多摆放$a-1$艘战舰（这一步我就不可能想到的了）。
现在已经攻击了某些位置，先看一下剩余的位置最多可以摆放多少艘战舰。根据已经被攻击的位置把整个区间划分成若干段，每一段都是连续的$0$。可以发现每一段都是相互独立的，因为不可能存在一艘战舰横跨被攻击的位置，不然就会被击中。因此要求总共最多可以摆放多少搜战舰，可以独立求每一段最多可以摆放多少搜战舰，然后把各个部分进行累加。
接下来独立求一下每一段的长度，假设长度为$m$，那么这一段最多可以摆放$\left\lfloor \frac{m}{b} \right\rfloor$艘战舰，构造一种取到等号的方案，就是从前往后数，每$b$个位置就摆放一艘战舰，那么一定可以摆放到$\left\lfloor \frac{m}{b} \right\rfloor$艘战舰。因此可以通过这种方法求出每一段最多摆放战舰的个数，假设全部加起来总的摆放个数为$t$，那么一定有$t \geq a$，因为题目保证有解。
现在我们要把$t$变成$a-1$，为此看一下每攻击一次最多可以减少多少艘战舰。可以发现每攻击一次最多可以减少$1$艘战舰，因此可以发现最少需要攻击$t-(a-1)$次，使得空地最多摆放$a-1$艘战舰。要取到$t-(a-1)$这个答案，就要证明能否构造一种攻击方案使得每次攻击恰好减少$1$艘战舰（取等号）。攻击第一艘战舰的最后一个位置，那么被攻击的位置前面有$b-1$个位置，这些位置不可能再摆放战舰，后面还剩余$m-b$个位置可以摆放战舰，最多可以摆放$\left\lfloor \frac{m}{b} \right\rfloor-1$艘战舰，因此等号可以取到。
AC代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 const int N = 2e5 + 10;
5
6 char str[N];
7
8 int main() {
9 int n, a, b, k;
10 scanf("%d %d %d %d %s", &n, &a, &b, &k, str + 1);
11
12 int ret = 0;
13 for (int i = 1, len = 0; i <= n; i++) {
14 if (str[i] == '1') {
15 len = 0;
16 }
17 else if (++len == b) {
18 ret++;
19 len = 0;
20 }
21 }
22
23 ret -= a - 1;
24 printf("%d\n", ret);
25
26 for (int i = 1, len = 0; ret; i++) {
27 if (str[i] == '1') {
28 len = 0;
29 }
30 else if (++len == b) {
31 printf("%d ", i);
32 ret--;
33 len = 0;
34 }
35 }
36
37 return 0;
38 }
参考资料
AcWing 4616. 击中战舰（AcWing杯 - 周赛）：https://www.acwing.com/video/4353/
标签：攻击,摆放,leq,方格,战舰,击中 From： https://www.cnblogs.com/onlyblues/p/16704203.html