AT_abc380_c.[ABC380C] Move Segment
普及-
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
给定一个只包含 0 和 1 的长度为 N 的字符串 S。
请输出将 S 中从头开始第 K 个 1 的连续块移动到第 K−1 个 1 的连续块的后面所得的字符串。
保证 S 中包含至少 K 个 1 的连续块。
更为准确的说明如下:
- 用 Sl…r 表示 S 的第 l 个字符到第 r 个字符组成的子串。
- Sl…r 是
1的连续块,当且仅当满足以下所有条件:- Sl=Sl+1=⋯=Sr=
1 - l=1 或 Sl−1=
0 - r=N 或 Sr+1=
0
- Sl=Sl+1=⋯=Sr=
- 假设 S 中所有的
1的连续块为 Sl1…r1,…,Slm…rm,且 l1<⋯<lm。
这时,定义长度为 N 的字符串 T 为“将 S 中从头开始第 K 个1的连续块移动到第 K−1 个1的连续块的后面所得的字符串”,具体如下:- 当 1≤i≤rK−1 时,Ti=Si
- 当 rK−1+1≤i≤rK−1+(rK−lK)+1 时,$T_i = $
1 - 当 rK−1+(rK−lK)+2≤i≤rK 时,$T_i = $
0 - 当 rK+1≤i≤N 时,Ti=Si
输入格式
输入从标准输入中按以下格式给出。
N K S
输出格式
请输出答案。
输入输出样例
输入#1
15 3 010011100011001
输出#1
010011111000001
输入#2
10 2 1011111111
输出#2
1111111110
说明/提示
限制条件
- 1≤N≤5×105
- S 是只包含
0和1的长度为 N 的字符串 - 2≤K
- S 中包含至少 K 个
1的连续块
样例解释 1
S 中有 4 个 1 的连续块,分别为第 2 个字符到第 2 个字符、第 5 个字符到第 7 个字符、第 11 个字符到第 12 个字符、第 15 个字符到第 15 个字符。
输入解题思路,AI测评打分。不知道怎么写?