• 欢迎光临源码岛,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境! 立即加入我们
  • 天池×九章算法|超级码力在线编程大赛 复赛题解

    正文概述 admin   2020-09-22   57

    简单地将题目转换成一个图,可以发现这是一棵基环树。

    由于丢失权限的服务器不会给另一台丢失权限的服务器发送信息,那么为了方便可以转换成最多有几台丢失权限的服务器,然么直接求最大独立集即可。

    对于环外的点直接挑入度为零的点,很显然挑入度小的点更优。

    然后按照这个步骤隔一个的挑点。若标到了环上的点,就剖环,最后把没剖开的环重新剖一次。

    用一个数组去标记遍历过的点,然后再用一个参数表示这个点选不选。

    最后计算答案即可。

    时间复杂度为$O(n)$

    空间复杂度为$O(n)$

    C++

    Python

    这题其实就是求包含给定点的最小生成树,也就是最小斯坦纳树。

    我们设$f[i][j]$表示节点目前正在转移的节点为i,节点i已经连通了状态为j的最小代价。

    当i不变时:$fi=fi+fi,k∈j$.

    时间复杂度为$O(n*3^k)$

    空间复杂度为$O(n*40)$

    C++

    Python

    枚举数字a,b和区间$[l,r]$,计算$[l,r]$中a和b的个数$cnt_a$和$cnt_b$,$ans=max(cnt_a−cnt_b)$

    显然这样是$O(10^2n^2)$的,需要优化。

    考虑换一种方式,先枚举a,然后同时对所有b做DP,定义$dp[b][i]$表示$[1,i]$的所有子段中,$cnt_a−cnt_b$的最大值,为了确保这当中的a,b数量均大于0,考虑记录两个东西:

    然后对当前字符分两种情况转移:

    $s_i≠a$,那么更新$dp[s_i][i][0/1]$的值:

    注意一下初值:$dpc=−∞,dpc=0$。然后时刻更新答案即可。

    时间复杂度为$O(10^2n)$

    空间复杂度为$O(20)$

    C++

    Python

    枚举$1-log_2n$作为最后剩下的组

    对于组内分组计数,即每次翻倍,列如最后剩下两组,不断翻倍,直到大于总人数,这个翻倍过程就是组内分组的次数,然后按照p,v计算时间花费

    更新每次枚举的花费求得最小花费

    C++

    Python

    1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
    2. 分享目的仅供大家学习和交流,请不要用于商业用途!
    3. 如果你也有好源码或者教程,可以到审核区发布,分享有岛币奖励!
    4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
    5. 如有链接无法下载、失效或广告,请联系管理员处理!
    6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
    7. 如遇到加密压缩包,默认解压密码为"www.ymadao.com",如遇到无法解压的请联系管理员!
    8.源码岛是一个优质的资源分享站,本站资源均为各位友友分享而来,特殊原创会标明如有侵犯版权等可联系
    源码岛 » 天池×九章算法|超级码力在线编程大赛 复赛题解

    发表评论

    • 2056会员总数(位)
    • 18285资源总数(个)
    • 52本周发布(个)
    • 7 今日发布(个)
    • 571稳定运行(天)

    提供最优质的资源集合

    开通SVIP 了解SVIP