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

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
登录
注册
题目详情题解(0)讨论(0)提交记录(0)
  • 更正经题解 | 我心中珍藏的游戏

    最小生成树秒掉了,全题用时最少AC代码:

    userId_undefined

    SJZ08

    出道萌新时间刺客尊贵铂金
    21阅读
    2回复
    2点赞
  • 正经题解|我心中珍藏的游戏

    特邀出题人MACW题解:原链接 题目解析 题目问最多可以获得的额外伤害,其实就是询问在这些技能中,如何怎样选取一个最优的发动技能顺序使得攻击加成最大。我们可以把每一个技能看作成一个图的顶点,把每一个攻击加成看作图的边,权制为 Ei,jEi,jEi,j。由于 Ei,jEi,jEi,j 与 Ej,iEj,iEj,i 相等,则可以将这个图视为无向图。 可以样样例抽象成下图: 考虑使用贪心的思想来解决本题,每次在图中找到权值最大的一条边选择即可,但图中不能出现环。因为是无向图,在考虑的时候可以忽略技能使用的顺序。接下来就是找一个最大生成树即可。 AC代码 时间复杂度分析 本道题可以使用最小生成树Kruskal算法来实现,将题目的模型抽象化后可以被看作为一个最多有 (1+n)∗n2−n\frac{(1+n)*n}{2} - n2(1+n)∗n −n 条边的无向图(化简后可得 n2−n2\frac{n^2 - n}{2}2n2−n )。注意一开始需要对每一条边进行排序。本道题的时间复杂度约为 O(2×n2log⁡2n)O(2\times n^2 \log_2{n})O(2×n2log2 n)。

    userId_undefined

    AC君

    小有名气倔强青铜管理员
    17阅读
    0回复
    0点赞
  • 我嘞个最大生成树

    userId_undefined

    复仇者_帅童

    小有名气CSP-J一等奖出题人
    8阅读
    0回复
    0点赞
首页