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

    ACM-POJ EXP 132阅读 0评论

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


    大致题意

    有k个坏人k个好人坐成一圈,前k个为好人(编号1~k),后k个为坏人(编号k+1~2k)

    现在有一个报数m,从编号为1的人开始报数,报到m的人就要自动死去。

    问当m为什么值时,可以使得在出现好人死亡之前,k个坏人先全部死掉?

    PS:当前一轮第m个人死去后,下一轮的编号为1的人 为 前一轮编号为m+1的人

    前一轮恰好是最后一个人死掉,则下一轮循环回到开头那个人报“1”

    解题思路

    经典的约瑟夫水题

    由于k值比较少(1~13),暴力枚举m就可以了

    递推公式为:

    ans[i]; //第i轮杀掉 对应当前轮的编号为ans[i]的人

    ans[0]=0;

    ans[i]=(ans[i-1]+m-1)%(n-i+1); (i>1 , 总人数n=2k 则n-i为第i轮剩余的人数)


    有耐心的同学可以自己推导一下公式。。。

    推导时要注意2点:

    第一:每轮都是以前一轮死掉的人的后一个人作为“1”开始顺序编号的

    如:k=2 (n=4) m=7

    1

    4

    3

    2

    那么最初的编号如下

    第一轮报数后,3号被杀掉,那么以3号后面的一个人“4”作为下一轮的“1”重新编号

    第二

    f[i]=(f[i-1]+m)%(n-i); (i>1)

    这是网上一些地方给出的递推公式,对于本题而言是不正确的。因为这种递推公式针对的是从0开始报数的Joseph,本题是从1开始报数的,必须要变形


    最后就是由于本题k值有限,只有13个值,那么POJ的数据测试就极有可能重复测试每个k值的结果,为了节省总体时间,我们的程序只在第一次得到k值的时候计算m值,然后保存下来,当k值再次出现时,就直接把保存的结果输出,不再计算m。这是在服务器打表的处理。


    另外有了递推的程序后,我们就知道了每个k值对应的m值。

    此时追求0ms AC的同学可以利用递推程序的结果,再写一个程序,直接在程序里面打表

    int Joseph[]={0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881,1245064};

    转载请注明:EXP 技术分享博客 » POJ1012 – Joseph

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

    表情

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

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