P3551 [POI2013]USU-Take-out

    • 59通过
    • 130提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 POI 2013 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Little Edna has received the take-out game as a present.

    Take-out is a single player game, in which the player is given a sequence of $n$ adjacent blocks, numbered from $1$ to $n$.

    Each block is either black or white, and there are $k$ times as many white blocks as there are black ones.

    The player's goal is to remove all the blocks by certain permissible moves.

    A single move consists in removing exactly $k$ white blocks and a single black block without changing the positions of other blocks.

    The move is permissible if there is no "gap" (a space left by a previously taken out block) between any two blocks being removed.

    Help poor little Edna in finding any sequence of permissible moves that remove all the blocks.

    有n块砖,其中白色是黑色的k倍,求一个消除序列,满足以下条件:

    每次消除k+1个砖,其中k块白色,1块黑色,并且这k+1块砖从开始到结束,中间不能路过已经消除过的砖

    数据保证有解

    输入输出格式

    输入格式:

    In the first line of the standard input there are two integers, $n$ and $k$ ($2\le n\le 1\ 000\ 000$, $1\le k\le n-1$), separated by a single space, that denote the total number of blocks used in the gameand the number of white blocks per black node (to be removed in every move). In all the tests the condition $k+1|n$ holds.

    In the second line there is a string of $n$ letters b or c. These tell the colours of successive blocks (in Polish):

    b (for biały) - white, c (for czarny) - black. You may assume that in all the tests there exists a sequence of permissible moves that takes out all the blocks.

    输出格式:

    Your program should print $\frac{n}{k+1}$ lines to the standard output.

    Successive lines should describe successive moves.

    Each line should contain $k+1$ integers, in increasing order,separated by single spaces, that denote the numbers of blocks to be removed in the move.

    输入输出样例

    输入样例#1: 复制
    12 2
    ccbcbbbbbbcb
    
    输出样例#1: 复制
    1 8 12
    2 6 7
    3 4 5
    9 10 11
    

    说明

    有n块砖,其中白色是黑色的k倍,求一个消除序列,满足以下条件:

    每次消除k+1个砖,其中k块白色,1块黑色,并且这k+1块砖从开始到结束,中间不能路过已经消除过的砖

    数据保证有解

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。