P14265 [ROI 2015 Day1] 企鹅研究

**译自 [ROI 2015](https://neerc.ifmo.ru/school/archive/2014-2015.html) Day1 T4.** ***[Пингвиноведение](https://neerc.ifmo.ru/school/archive/2014-2015/ru-olymp-roi-2015-day1.pdf)***

南极南部大学的企鹅学系正在进行企鹅种群的研究工作。研究人员将密集站立的企鹅群体进行拍照，随后由学生对这些照片进行处理。企鹅的识别方式如下：在照片上选取一条特征条带，该条带的高度为 1 个像素，并且条带上的每个像素都属于某一只企鹅的图像。 研究中的企鹅都有相似的体色特征：腹部为白色，背部和翅膀为黑色。因此： - 若照片上只看到企鹅的背部，则对应的条带上会出现一段连续的黑色像素； - 若只看到腹部，则为连续的白色像素； - 若既能看到翅膀又能看到腹部（例如翅膀遮在白色腹部前），则该企鹅对应的条带上会出现由黑白混合组成的像素段。 为了便于后续研究，需要保证每只企鹅在特征条带上都对应一个**仅由黑色或仅由白色像素组成的连续段**。 对于第 $i$ 张照片，已知其特征条带上可能出现的企鹅数量不超过 $k_i$。因此，必须将该条带替换为一条长度相同的**简化条带**，它由不超过 $k_i$ 个连续的色段组成，每个色段要么全为黑色，要么全为白色。在所有可能的简化条带中，需要选择一种**最优方案**，即通过**最少次数地修改像素颜色**，使原条带转化为合法的简化条带。 请编写程序完成上述任务。

输入的第一行包含整数 $t$ —— 照片的数量。接下来有 $t$ 组数据，每组对应一张照片。 每组数据的第一行包含两个整数： - $n_i$ —— 第 $i$ 张照片的特征条带长度； - $k_i$ —— 该条带上最多可能出现的企鹅数量（保证 $k_i \le n_i$）。 第二行包含一个长度为 $n_i$ 的字符串，由字符 **0** 和 **1** 组成。**0** 表示黑色像素；**1** 表示白色像素。

输出 $t$ 行。第 $i$ 行应为一个长度为 $n_i$ 的字符串，由字符 **0** 和 **1** 组成，表示通过最少修改后得到的第 $i$ 张照片的**简化条带**。如果存在多个最优答案，输出任意一个即可。

### 数据范围 | 子任务编号 | 分值 | $n_i, k_i$ 的范围 | $n = n_1 + n_2 + \cdots + n_t$ 的范围 | |:--:|:--:|:--:|:--:| | 1 | 11 | $1 \le k_i \le n_i \le 10$ | $1 \le n \le 5000$ | | 2 | 24 | $1 \le k_i \le n_i \le 100$ | $1 \le n \le 5000$ | | 3 | 24 | $1 \le k_i \le n_i \le 1000$ | $1 \le n \le 50\,000$ | | 4 | 21 | $1 \le k_i \le 5000$ | $1 \le n \le 100\,000$ | | 5 | 20 | $1 \le k_i \le 200\,000$ | $1 \le n \le 200\,000$ |