AT_abc380_c.[ABC380C] Move Segment

普及-

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

给定一个只包含 01 的长度为 NN 的字符串 SS
请输出将 SS 中从头开始第 KK1 的连续块移动到第 K1K-11 的连续块的后面所得的字符串。

保证 SS 中包含至少 KK1 的连续块。

更为准确的说明如下:

  • SlrS_{l\ldots r} 表示 SS 的第 ll 个字符到第 rr 个字符组成的子串。
  • SlrS_{l\ldots r}1 的连续块,当且仅当满足以下所有条件:
    • Sl=Sl+1==Sr=S_l = S_{l+1} = \cdots = S_r = 1
    • l=1l=1Sl1=S_{l-1} = 0
    • r=Nr=NSr+1=S_{r+1} = 0
  • 假设 SS 中所有的 1 的连续块为 Sl1r1,,SlmrmS_{l_1\ldots r_1}, \ldots, S_{l_m\ldots r_m},且 l1<<lml_1 < \cdots < l_m
    这时,定义长度为 NN 的字符串 TT 为“将 SS 中从头开始第 KK1 的连续块移动到第 K1K-11 的连续块的后面所得的字符串”,具体如下:
    • 1irK11 \leq i \leq r_{K-1} 时,Ti=SiT_i = S_i
    • rK1+1irK1+(rKlK)+1r_{K-1}+1 \leq i \leq r_{K-1}+(r_K-l_K)+1 时,$T_i = $ 1
    • rK1+(rKlK)+2irKr_{K-1}+(r_K-l_K)+2 \leq i \leq r_K 时,$T_i = $ 0
    • rK+1iNr_K+1 \leq i \leq N 时,Ti=SiT_i = S_i

输入格式

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

NN KK SS

输出格式

请输出答案。

输入输出样例

  • 输入#1

    15 3
    010011100011001

    输出#1

    010011111000001
  • 输入#2

    10 2
    1011111111

    输出#2

    1111111110

说明/提示

限制条件

  • 1N5×1051 \leq N \leq 5\times 10^5
  • SS 是只包含 01 的长度为 NN 的字符串
  • 2K2 \leq K
  • SS 中包含至少 KK1 的连续块

样例解释 1

SS 中有 441 的连续块,分别为第 22 个字符到第 22 个字符、第 55 个字符到第 77 个字符、第 1111 个字符到第 1212 个字符、第 1515 个字符到第 1515 个字符。

输入解题思路,AI测评打分。不知道怎么写?

首页