#2410. 节日庆典

    ID: 2410 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>PROV赛事:contest890来源:qoj.ac数据:公开样例字符串单调栈

节日庆典

节日庆典

题目描述

预览输出 JSOI2019 Round 2 节日庆典(celebrate) 节日庆典(celebrate) 【题目背景】 JYY 和探险队顺利完成了火星上的任务。在离开前,探险队正好赶上了火星人一年 一度最盛大的节日“气球节”。然而,火星人遇到了每年一度的麻烦:怎样最美观地摆 放气球。JYY 决定请你设计算法帮助火星人解决这个问题。 【题目描述】 在庆典开始前,火星人会把气球准备好并串在一根绳子上。气球按顺序排列可以看 成是一个由小写字母组成的长度为n 的字符串S。然后,火星人会按照字符串的顺序逐 个把气球加入到一个庆典的圆环上,并且表演一个节目庆祝。 下图展示了一串气球cbbadbcd在进行到第5 个节目时的情形,此时在庆典环上的 气球是cbbad。 为了让每个节目都更好看,火星人希望在每个节目开始前调整气球在环上的顺序, 使得每个节目的气球排布都最美观。对于一组气球(一个字符串),火星人认为最美观的 字符串是庆典圆环上按绳子方向读出.字.典.序.最.小.的.字.符.串,例如对于cbbad,共有5 个 读出字符串的位置: • cbbad (i = 1) • bbadc (i = 2) • badcb (i = 3) • adcbb (i = 4) • dcbba (i = 5) 第7 页 共9 页

预览输出 JSOI2019 Round 2 节日庆典(celebrate) 如果有多个字典序最小的字符串,火星人希望找出.离.绳.头.最.近的那个(即i 最小的 那个)。更严谨地说,对于字符串T,定义 Ti = T[i . . . |T|] :: T[1 . . . i −1] (1 ≤i ≤|T|), 其中:: 是字符串的拼接操作。定义f(T) 为最小的i (1 ≤i ≤|T|) 满足Ti = min{T1, T2, . . . , T|T|}。 JYY 希望你帮助他设计一个算法,让火星人每个节目的气球排列都最美观,即对于 给定字符串S 的每一个前缀S[1 . . . i] (1 ≤i ≤|S|),求出f(S[1 . . . i])。 【输入格式】 从文件celebrate.in 中读入数据。 输入文件只有一行,该行包括一个字符串S。 【输出格式】 输出到文件celebrate.out 中。 在一行中对于每个i (1 ≤i ≤|S|),输出一个整数f(S[1 . . . i])。输出的数字之间以 空格分隔。 【样例1 输入】 1 abaacaba 【样例1 输出】 1 1 1 3 3 3 6 3 8 【样例2】 见选手目录下的celebrate/celebrate2.in 与celebrate/celebrate2.ans。 第8 页 共9 页

预览输出 JSOI2019 Round 2 节日庆典(celebrate) 【子任务】 测试点 n 是否随机生成? 生成限制 1 ≤20 否 无 2,3 ≤103 是 字符集为{a, b, c} 4 ≤2 × 105 5 ≤5 × 104 否 每个字符出现次数相等 6,7 ≤106 无 8,9,10 ≤3 × 106 第9 页 共9 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

abaacaba
1 1 3 3 3 6 3 8

样例 2

accbcdbbdccabacdbccabcbbdbbcccbdccbadccdaaccadaadabcdabdacddacdccbbaddddabadcdbbdbcaddbdbcddcbaaadaabaaaadadcbcdabccadadcddcadcdddcdddacaaabcaccbabbdcddabbaacbabcdbdabadacddccacabcdabbabcbddadccabdabccabadcbbaacaddacabcdbabdcdadbdcdacdbbccddaacbadabbbabadcdcbcbdddcddcdddbbdccdaabdbadbddbcdcaacccabbabdddddadacbcdcadcbadbaddacdcdadccdcccdbabadbdcacbddbdddcddddaaadaddcbaabcabaaaccbacaaacacdddcdcdadaacaadcbccbbcdcdabdbcababdaabacdaacccacdacaddbcbbaccbcbddadbbdcddbddacabdaabdadbbcaccbdabdadabcbbbbcabdbdcddbbbcdacdccadabdcbddcaadbdabdbabcacdaaadbacdccbadcabdbdcacccddbabccdadabcaaddacbcdccdcbcddddcbdcdbcbaddbdadbbcaaacdacabbdccbaabcddaabdadcccadccaaacdcbbccdacbccbccbdbbccdcdabcaacddbdabdcbbbbadaabacbacbdabdaddbddacbcbdccacabcabbdbdcabbdcacbcdaaccbdcaacdaccccbbabdccbdabddabcccbaaabcacccbacacadbdabcbcccdbdcdbadcddbddaacdccbbbcbdbbdbbaadcbddbabccbccbacbbdbdbadabccdbccbacacbbacadcdbaabbccbcccdbbbdaddddbcddddbdbbbccabbacbaccdddacddbbdbaababcabdccccabccbadbcbaacdacdcddbddcbccdcaadbadcabccbadcdddcba
1 1 1 1 1 1 1 1 1 1 1 12 12 14 12 12 12 12 12 20 20 12 12 12 12 12 12 12 12 12 12 12 12 12 12 36 12 12 12 12 41 41 41 41 41 41 41 47 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 95 95 95 95 99 95 95 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 137 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 361 102 102 102 102 102 102 102 102 102 102 102 102 102 102 376 102 102 102 102 102 102 102 384 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 542 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 616 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 649 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 781 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102