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

    ACM-POJ EXP 108阅读 0评论

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


    大致题意

    给出一个5元3次方程,输入其5个系数,求它的解的个数

    其中系数 ai∈[-50,50] 自变量xi∈[-50,0)∪(0,50]

    注意 : 若 x1=a, x2=b, x3=c, x4=d, x5=e 时,与 x1=b, x2=a, x3=c, x4=d, x5=e 代入方程后都得到值0,那么他们视为不同的解。

    解题思路

    直观的思路:暴力枚举,O(n^5)

    题目Time Limit=5000ms,1ms大约可以执行1000条语句,那么5000ms最多执行500W次

    每个变量都有100种可能值,那么暴力枚举,5层循环,就是要执行100^5=100E次,等着TLE吧。。。。

    要AC这题,就要对方程做一个变形

     
    a_1x_1^3+a_2x_2^3+a_3x_3^3+a_4x_4^3+a_5x_5^3=0
    等价于
    -(a_1x_1^3+a_2x_2^3)=a_3x_3^3+a_4x_4^3+a_5x_5^3

    即先枚举x1和x2的组合,把所有出现过的 左值 记录打表,然后再枚举x3 x4 x5的组合得到的 右值,如果某个右值等于已经出现的左值,那么我们就得到了一个解

    时间复杂度从 O(n^5)降低到 O(n^2+n^3),大约执行100W次


    我们先定义一个映射数组hash[],初始化为0

    对于方程左边,当x1=m , x2 n时得到sum,则把用hash[]记录sum : hash[sum]++,表示sum这个值出现了1次

    之所以是记录“次数”,而不是记录“是否已出现”

    是因为我们不能保证函数的映射为 1对1 映射,更多的是存在 多对1映射

    例如当 a1=a2时,x1=m , x2= n我们得到了sum,但x1=n , x2=m 时我们也会得到sum,但是我们说这两个是不同的解,这就是 多对1 的情况了,如果单纯记录sum是否出现过,则会使得 解的个数 减少。

    其次,为了使得 搜索sum是否出现 的操作为o(1),我们把sum作为下标,那么hash数组的上界就取决于a1 a2 x1 x2的组合,四个量的极端值均为50

    因此上界为 5050^3+5050^3=12500000,由于sum也可能为负数,因此我们对hash[]的上界进行扩展,扩展到25000000,当sum<0时,我们令sum+=25000000存储到hash[]

    由于数组很大,必须使用全局定义

    同时由于数组很大,用int定义必然会MLE,因此要用char或者short定义数组,推荐short

    转载请注明:EXP 技术分享博客 » POJ1840 – Eqs

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

    表情

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

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