#PQJ890x6224. QOJ 890_6224
QOJ 890_6224
预览输出 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 页