当前位置: 首页 > news >正文

10.17 —— (VP) 2021icpc沈阳

自己 \(vp\) 区域赛以来最好的一把,赛时 \(5\) 题,罚时 \(607\),正式赛大概 \(rk 120\) 左右,属于是蒟蒻的超水平发挥了。尤其是 \(H\) 题最后半小时内想出正解并且 \(1A\),感觉真的特别爽。

\(E, F\) 纯签到。

\(B\) 题套路也极为典型,二进制拆位考虑就可以把看似很难的问题划分成 $O(\log) $ 个很简单的子问题,需要用到并查集和二分图染色,这里不再赘述详细解法。

code

\(J\) 题吃了 \(6\) 发罚时,属实是有些唐了。记住,罚时很重要!罚时很重要!罚时很重要!此题的套路也很典型:\(a, b\) 做相同的操作,答案不会改变。因此对于所有询问,直接将这些询问的 \(a\) 归一化,于是问题就变成了单源最短路问题,一次 \(bfs\) 即可,复杂度 \(O(20 * 10000)\),其中 \(20\) 是状态转移过程中的常数,\(10000\) 是状态总数。

code

\(H\) 题需要将题意化繁为简的能力,把问题变成一个易懂的形式,剩下的就特别好想了。与本题等价的问题是:每次可以选取具有公共结点的一对边,每条边只能选一次,直到不能再继续选,最大化选取所有边的总和。 由于给定图是连通的,不难猜到,当边数为偶数时,所有的边一定都可以选到;而边数是奇数时,一定可以选 \(m - 1\) 条边,也就是只有一条边不会被选择。那么我们就可以枚举所有边,看不选它时,剩下的所有边能否均被选择。此时有两种情况:

  • 该边不是割边:那么去掉这条边后,剩下的图仍然连通,且边数为偶数,情况与上一个相同,一定可以都选到。
  • 该边是割边:去掉该边后,会形成两个连通块,并且这两个连通块的奇偶性相同。显然如果是偶数,则可行;奇数则不可行。

于是问题缩小为了:去除连通图的一条指定割边,判断形成的两个连通块的奇偶性。可以用 \(dcc\) 边双连通分量对原图进行缩点,形成由割边构成的一棵树。则连通块内的边数就等于内部的割边数+非割边数。割边数就是子树大小-1,非割边数就是子树内所有边双内的边数之和,可以一次 \(dfs\) 预处理得到所有割边的解。

code

接下来是补题时间。

L. Perfect Matchings

原问题等价于:求给定的一棵大小为 \(2n\) 的树中,不含有树边且匹配数为 \(n\)(选 \(n\) 个点对,即所有点均要匹配到)的最大匹配数量。

待补。。。

http://www.hskmm.com/?act=detail&tid=33305

相关文章:

  • 10.17每日总结
  • 今天宝宝进面了
  • 《大象Thinking in Projects》读书笔记1
  • 20251017
  • MT签名去除签名校验分析
  • uml
  • P3643 [APIO2016] 划艇 分析
  • day016
  • uml九图和数据流图总结
  • UpdateSourceTrigger和Mode的区别
  • NOIP2020 T2
  • Alex-VGG3
  • 第二章日志分析-redis应急响应
  • 第一章 应急响应- Linux入侵排查
  • 浏览器多开的方法
  • 10月17号
  • 19. 删除链表的倒数第 N 个结点
  • Day13
  • 第一章日志分析-mysql应急响
  • 操作系统应用构建(十二)RustDesk 用户服务器搭建——东方仙盟筑基期
  • python-IDLE定制界面大小
  • 高级语言程序设计第1次作业
  • Maui:通过附加属性将命令绑定到事件
  • 超好用的浏览器多开小工具!轻松管理多个账号,可以无限制使用其他插件
  • 微服务组件-Eureka 科技详解
  • 新学期每日总结(第10天)
  • List.subList() 返回值为什么不能强转成 ArrayList
  • 奶奶都能看懂的 C++ —— 手把手指针
  • 10/17
  • CSP-2024 T4