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

    ACM-POJ EXP 217阅读 0评论

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


    大致题意

    题意不难懂,对于任意的数字串n,都可以压缩存储为c1 d1 c2 d2 …. ck dk 形式的数字串

    而存在一些特别的数字串,其压缩前后的样子是一模一样的,定义这种数字串为self-inventorying

    当我们把n看成原串,

    A为n压缩1次后的数字串,

    B为n压缩2次后的数字串(即A压缩1次后的数字串)

    ….以此类推

    K为n压缩k次后的数字串(即K-1压缩k-1次后的数字串)

    则可以延伸出数字串n的3种属性

    1、 n压缩1次就马上出现self-inventorying特性,即 n n n n n n n …..

    2、 n压缩j次后的数字串J出现self-inventorying特性,即 n A B C….H I J J J J J J J

    3、 n压缩j次后的数字串J,每再压缩K次,重新出现数字串J,即n A B… J ..K J ..K J..K J

    其中K称为循环间隔,K>=2

    现给定一字符串,输出其属性。 属性1优于属性2,属性2优于属性3

    解题思路

    字符串处理,纯粹的模拟题

    压缩n时要注意,ck可能是1位,也可能是2位,需要判断。

    设R(n)为描述整数n的压缩数字串

    1、当R(n)==R(R(n))时,则n is self-inventorying

    2、对于整数n:

    3、对于整数n:

    4、当且仅当n的3种属性都不存在时,n can not be classified after 15 iterations

    Source修正

    East Central North America 1998(已失效)

    测试数据

    本文第二页附带测试数据


    转载请注明:EXP 技术分享博客 » POJ1016 – Numbers That Count

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

    表情

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

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