AT_abc380_c [ABC380C] Move Segment
题目描述
给定一个长度为 n、只包含 ‘0’ 和 ‘1’ 的字符串 s。请输出将 s 中从头开始第 k 个 ‘1’ 的连续块移动到第 k−1 个 ‘1’ 的连续块的后面所得的字符串。
保证 s 中包含至少 k 个 ‘1’ 的连续块。
更为准确的说明如下:
∙用 sl…r 表示 s 的第 l 个字符到第 r 个字符组成的子串;
∙称 sl…r 为 ‘1’ 的连续块,当且仅当以下三个条件全部满足:
∘对任意的 l≦i≦r 都有 si=‘1’;
∘满足 l=1 或 sl−1=‘0’;
∘满足 r=n 或 sr+1=‘0’。
∙假设 s 中所有的 ‘1’ 的连续块依次为 $s_{l_1 \dots r_1}, s_{l_2 \dots r_2}, \dots, s_{l_p \dots r_p}$,且 l1<l2<⋯<lp。这时,定义长度为 n 的字符串 t 为「将 s 中从头开始第 k 个 ‘1’ 的连续块移动到第 k−1 个 ‘1’ 的连续块的后面所得的字符串」,具体如下:
∘当 1≦i≦rk−1 时,ti=si;
∘当 $r_{k-1}+1 \leqq i \leqq r_{k-1}+\left(r_k-l_k\right)+1$ 时,ti=‘1’;
∘当 rk−1+(rk−lk)+2≦i≦rk 时,ti=‘0’;
∘当 rk+1≦i≦n 时,ti=si。
输入格式
第一行输入两个整数 $n, k \left(1 \leqq n \leqq 5 \times 10^5;\ 2 \leqq k \leqq n\right)$ 代表字符串的长度与需要移动的 ‘1’ 的连续块的编号。
第二行输入一个长度为 n、只包含 ‘0’ 和 ‘1’ 的字符串 s。保证 s 中包含至少 k 个 ‘1’ 的连续块。
输出格式
在一行上输出一个长度为 n 的字符串,代表操作结束后得到的字符串。
测试样例
15 3
010011100011001
010011111000001
10 2
1011111111
1111111110
样例 1 解释
样例中的字符串 s 中有 4 个 ‘1’ 的连续块,分别为 s2…2、s5…7、s11…12 和 s15…15。将第 3 个连续块 s11…12 移动到第 2 个连续块 s5…7 的后面,得到 "010011111000001"。