P3279 [SCOI2013]密码

    • 75通过
    • 176提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 Splay 字符串 并查集 2013 四川
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Fish是一条生活在海里的鱼。有一天他很无聊,就到处去寻宝。他找到了位于海底深处的宫殿,但是一扇带有密码锁的大门却阻止了他的前进。

    通过翻阅古籍,Fish 得知了这个密码的相关信息:

    1. 该密码的长度为N。

    2. 密码仅含小写字母。

    3. 以每一个字符为中心的最长回文串长度。

    4. 以每两个相邻字符的间隙为中心的最长回文串长度。

    很快Fish 发现可能有无数种满足条件的密码。经过分析,他觉得这些密码中字典序最小的一个最有可能是答案,你能帮他找到这个密码么?

    注意:对于两个串A和B,如果它们的前i个字符都相同,而A的第i+1个字符比B的第i+1个字符小,那么认为是则称密码A 的字典序小于密码B 的字典序,例如字符串abc 字典序小于字符串acb。如果密码A的字典序比其他所有满足条件的密码的字典序都小,则密码A是这些密码中字典序最小的一个。

    输入输出格式

    输入格式:

    输入由三行组成。第一行仅含一个整数N,表示密码的长度。第二行包含N 个整数,表示以每个字符为中心的最长回文串长度。第三行包含N - 1 个整数,表示每两个相邻字符的间隙为中心的最长回文串长度。

    输出格式:

    输出仅一行。输出满足条件的最小字典序密码。古籍中的信息是一定正确的,故一定存在满足条件的密码。

    输入输出样例

    输入样例#1: 复制
    3
    1 1 1
    0 0
    输出样例#1: 复制
    abc
    
    输入样例#2: 复制
    3
    1 3 1
    0 0
    输出样例#2: 复制
    aba
    输入样例#3: 复制
    3
    1 3 1
    2 2
    输出样例#3: 复制
    aaa

    说明

    对于20% 的数据,1 <= n <= 100。

    另有30% 的数据,1 <= n <= 1000。

    最后50% 的数据,1 <= n <= 10^5。

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