acgo题库
  • 首页
  • 题库
  • 题单
  • 竞赛
  • 讨论
  • 排行
  • 团队
  • 备赛专区

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
登录
注册
题目详情题解(0)讨论(0)提交记录(0)
  • A50146题解 思维题

    比较容易想到一个四重循环的暴力破解办法,第一重循环判断第i个数是不是好数,第二,三,四重循环分别跑第一个数,第二个数和第三个数,但是由于n <= 5000,所以这个方法会TLE,考虑优化,这边注意到时间复杂度是支持On²logn的,而且第一重循环基本上优化不了,那动刀也只是在第二三四重循环上,我们观察第二三四重循环的本质,比较好想一个On3logn的优化方法,第四重循环变set,但是还不够,接着想,我们已知当前值a[i],和第二重循环a[j], 那么我只想知道前i – 1个数中存不存在可复两数和为a[i] – a[j],所以我们可以优化掉第三四维,开个set来存储之前所有的两数和,时间复杂度On²logn,这样这题就通过了。 细节:注意到是之前所有元素的两数和,所以更新set操作一定是在更新ans操作后,而且每个数可复用,所以ai + ai的值你也要放进set里;还卡set,直接unordered_set

    userId_undefined

    nt

    倔强青铜
    12阅读
    0回复
    0点赞
首页