题库练习 [ABC380C] Move Segment
← 上一题 下一题 →

A7692 | [ABC380C] Move Segment

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

给定一个只包含 01 的长度为 $N$ 的字符串 $S$。
请输出将 $S$ 中从头开始第 $K$ 个 1 的连续块移动到第 $K-1$ 个 1 的连续块的后面所得的字符串。

保证 $S$ 中包含至少 $K$ 个 1 的连续块。

更为准确的说明如下:

- 用 $S_{l\ldots r}$ 表示 $S$ 的第 $l$ 个字符到第 $r$ 个字符组成的子串。
- $S_{l\ldots r}$ 是 1 的连续块,当且仅当满足以下所有条件:
- $S_l = S_{l+1} = \cdots = S_r =$ 1
- $l=1$ 或 $S_{l-1} =$ 0
- $r=N$ 或 $S_{r+1} =$ 0
- 假设 $S$ 中所有的 1 的连续块为 $S_{l_1\ldots r_1}, \ldots, S_{l_m\ldots r_m}$,且 $l_1 < \cdots < l_m$。
这时,定义长度为 $N$ 的字符串 $T$ 为“将 $S$ 中从头开始第 $K$ 个 1 的连续块移动到第 $K-1$ 个 1 的连续块的后面所得的字符串”,具体如下:
- 当 $1 \leq i \leq r_{K-1}$ 时,$T_i = S_i$
- 当 $r_{K-1}+1 \leq i \leq r_{K-1}+(r_K-l_K)+1$ 时,$T_i = $ 1
- 当 $r_{K-1}+(r_K-l_K)+2 \leq i \leq r_K$ 时,$T_i = $ 0
- 当 $r_K+1 \leq i \leq N$ 时,$T_i = S_i$

输入格式

输入从标准输入中按以下格式给出。

> $N$ $K$ $S$

输出格式

请输出答案。

输入输出样例

输入 #1
15 3
010011100011001
输出 #1
010011111000001
输入 #2
10 2
1011111111
输出 #2
1111111110
C++ 编辑器
输入
输出