Solution Set - 《赏竹而格之》
2024-09-03 03:58:13
1.「GXOI / GZOI 2019」「洛谷 P5304」旅行者
Link & Submission.
经典二进制分组,没啥好说的。
2. 「SDOI 2019」「洛谷 P5361」热闹的聚会与尴尬的聚会
Link & Submission.
随便拓扑一发可以求到最大的 \(p\),进而得到 \(q\) 的目标值。我一看,精确求 \(q\) 是 NP-Hard?!好的我们 std::shuffle
一发依次选……我焯它过了?
确定性算法:注意到 \((p+1)(q+1)\ge n+1\),我们每次取 \(\arg\min\{d(u)\}\),将它和它的邻接点删掉,尝试构造独立集,同时用当前的 \(\min\{d(u)\}\) 和对应的图更新 \(q\) 度图,然后发现可行√
如果实现随意都是 \(\mathcal O(Tm\log m)\) 的。
3. 「LibreOJ NOI Round #1」「LOJ #508」失控的未来交通工具
Link & Submission.
我卡得比较久的地方是第一步转化的先入为主:觉得这个和同余最短路相关,继而想动态维护最短路之类的鬼东西……
图非常不可做,一般我们选择将路径特殊化:变成树边 + 环,但恼人的是这个“环”似乎并不独立于“路径”,我们必须先走到环上的点才能进入环。联系经典的异或路径问题,可以尝试一步构造,让环仅依赖于连通块存在:若想要加入一个环,我们从路径上一点从任意路径走向环,绕一圈,然后在这“任意路径”上往返 \(m\) 次即可。显然我们只需要关心所有环长的 \(\gcd\),并查集记录这一信息。
对于询问,可以转化成求 \(gx+my=\cdots\) 的整数解问题,虽然数学计算的 corner cases 很多但写题解就不重要了√ 复杂度是 \(\mathcal O(q\log V)\)。
最新文章
- gtest学习一:在vs2013中搭建gtest环境
- JAVA里的异常
- mottoes
- JavaScript使用DeviceOne开发实战(一) 配置和起步
- Grunt 安装与配置环境
- 【leetcode】Search in Rotated Sorted Array
- jquery实现nav的下拉
- 2016中国VR开发者论坛第一期
- EF保存平面数据到SqlServer
- jQuery模拟鼠标点击事件失效的问题
- Android之Activity的几种跳转方式
- 《Android内核剖析》读书笔记 第13章 View工作原理【View重绘过程】
- BOM之history对象
- Tp3.2 和 Tp5.0之间的区别
- 异步请求时有时会让js不起作用,那么重新加载js
- LeetCode之“链表”:在O(1)时间删除链表节点
- eclipse里访问tomcat首页出现404错误解决之法
- Ubuntu18.04下编译安装Guitarix 0.37.3
- xcode6 新建项目真机调试无法全屏
- samtools软件的使用