• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ3096 – Surprising Strings

    ACM-POJ EXP 122阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    定义D-pairs表示取字符串s中相距为D的两个字母所构成的字母对,该字母对中两个字母的位置顺序与他们在主串s中的位置顺序一致

    定义D-unique表示,若从字符串s中取出所有相距为D的字母对D-pairs,且这些D-pairs都是独一无二的,那么成字符串s是一个D-unique串

    D的取值范围为0~s.len()-2

    假如字符串s对于所有的D都有D-unique成立,则字符串s是令人惊讶的 = =

    现在输入一些字符串,问他们能不能令人惊讶= =

    解题思路

    令人惊讶的中级水题= =

    STL的map标记D-unique是否重复出现就OK

    也可以用ASCII标记,取两个大写字母的ASCII构成一个四位数作为key就可以了,比map快一点点


    层次关系

    对于某个D,当所有D-pairs都不同时,s是D-unique

    对于所有D,s都有D-unique时,它是surprising string

    注意,长度小于等于2的s都是surprising string

    其实我感觉这题暴力也能AC= =,S最大长度也就79…


    方法一:STL<map>标记

    转载请注明:EXP 技术分享博客 » POJ3096 – Surprising Strings

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址