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

    ACM-POJ EXP 94阅读 0评论

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


    大致题意

    给定一个字符串,从任意位置把它切为两半,得到两条子串

    定义 子串1为s1,子串2为s2,子串1的反串为s3,子串2的反串为s4

    现在从s1 s2 s3 s4中任意取出两个串组合,问有多少种不同的组合方法


    规定

    (1) 串Si不能和其 反串 组合

    (2) Si+Sj 与 Sj+Si 是两种组合方式(但未必是不同的组合方式)

    解题思路

    利用hash表查重

    穷举全部组合的情况,每枚举一个就记录一次,假如后面枚举的组合已经存在记录,说明组合重复,计数器不变,否则计数器+1


    本题不能用STL的map映射,map太慢会超时

    自己写Hash表吧!

    对于*ps指向的字符串s,我定义的关键字

    可以认为i为权重,利用字母的ASCII得到key

    解决冲突方法为链地址法

    转载请注明:EXP 技术分享博客 » POJ3007 – Organize Your Train part II

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

    表情

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

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