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

    ACM-POJ EXP 170阅读 0评论

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


    大致题意

    给定两个四位素数a b,要求把a变换到b

    变换的过程要保证 每次变换出来的数都是一个 四位素数,而且当前这步的变换所得的素数 与 前一步得到的素数 只能有一个位不同,而且每步得到的素数都不能重复。

    求从a到b最少需要的变换次数。无法变换则输出Impossible

    解题思路

    超级水题,40入口的BFS + 素数判定

    不过剪枝之后就没有40入口了,入口数远小于40

    无论是判定素数还是搜索素数,首先排除偶数,这样就剪掉一半枝叶了

    判断素数用根号法判断,

    如果一个数X不能被 [2,√X] 内的所有素数整除,那么它就是素数

    可以判断的复杂度降到logn

    注意:千位的变换要保证千位不为0

      其实素数也是用来辅助搜索剪枝

    转载请注明:EXP 技术分享博客 » POJ3126 – Prime Path

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

    表情

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

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