金华武义训练游记

slzx2022YuYihan · 2023-01-12 21:35:57 · 个人记录

Day1 2023.01.12

13:00出发，17：00到达。

我和phx拼一间房。

晚上打“连花清瘟”赛，被LZ的人坑掉了半个多小时。

打到21:30，9道里A5道，rank12。

22:50睡觉……

Day2 2023.01.13

08:30开始上课，主讲是清华大学读博的毛嘉怡（好像是国家集训队的）。今天讲最短路基础。

对我来说，有一些难度，但是对于phx神佬还是比较一般的。

有单源、多源多汇、点集、同余最短路等等。

这些方法还是比较巧妙的，但是很难想到，一定需要点播和提示才有可能想到正解。甚至有些看似是数论的题，正解要用最短路解决，建边也很巧妙。

下午13:30~16:30，做今天的练习，其中有好几道蓝题、紫题（应该说基本）。在我和phx的互相帮助下，我们AK了。谢谢phx神佬，帮我找出程序上致命的错误！

晚上22:15睡觉……

Day3 2023.01.14

今天讲最短路提高。

原来floyed在求全源最短路是高效做法！

$A1:

含负权边的图
dijstra$求全源最短路复杂度：$O(nm$ $log$ $n)

$A2: $ $floyd$ 后观察是否有 $f(i, i) < 0$. $Q3:$ 那从某一点 $s$ 出发是否有可达负环？ $A3:$ 确定所有在负环上的点，再做连通性 $BFS$ 即可. $Q4:$ 如何用 $floyd$ 求最小环值？ $A4:$ 考虑图中最大点 $k$, 和其相邻点 $i, j$, 最小环必然能分割成 $f(k - 1, i, j) + (i, k) + (k, j)$. ———————————————————————————————————————————————————————————————————— 还讲了bitset传递闭包优化. [传递闭包](https://www.acwing.com/file_system/file/content/whole/index/content/7800174/) ———————————————————————————————————————————————————————————————————— 还有差分约束，也是应用了转换的思想. ———————————————————————————————————————————————————————————————————— 干货一张：如何判断一条边是否在最短路上？（可以 $O(n ^ 3)$） <https://www.acwing.com/file_system/file/content/whole/index/content/7800761/> ———————————————————————————————————————————————————————————————————— 例题有点难度，都上了浙江省选难度…… 下午练习题，比昨天难了好多，还有黑题。晚上打AT，打寄了，只做出A。C打到一半放弃了，特判情况太多了…… 神奇的是，我还加了128分。~~（看来大家都寄了）~~ 晚上23:00睡觉…… ------------ # Day4 2023.01.15 讲了**强连通分量**。**一张图可以唯一被分解成强连通分量。** ———————————————————————————————————————————————————————————————————— 还有 **DFS 生成树**。横边、返祖边、横叉边、前向边等一些概念。 **任意强连通分量都是DFS生成树上的一个连通子图** ———————————————————————————————————————————————————————————————————— **Tarjan 算法**：定义： * $dfn_u$ ： $DFS$ 生成树中点 $u$ 被访问到的次序。 * $low_u$ ： $u$ 的字数中能通过不超过一条边到达的*尚在栈中*的元素 $dfn$ 最小值。性质： * 一个强连通分量当中任意非根节点 $u$ 都有 $$low_u < dfn_u$$ * 对于一个强连通分量当中的根节点 $u$ 有 $low_u = dfn_u

Targan模板

————————————————————————————————————————————————————————————————————

Targan算法 + 缩点

为什么缩点？ 不存在环！变为有向无环图（DAG）

转化为在DAG上dp。

Tarjan求桥：

定义：

性质：

非树边必然不可能是桥
假设树边 (u, v) , u 是父亲。
(u, v)$是桥当且仅当$low_v > dfn_u

Targan求桥代码

边双连通分量

割点：

定义

若删去 u 使连通块数量增加， u 为割点

性质

在 DFS 生成树中根节点儿子数 \ge \mathbb{2}，是割点，若为 \mathbb{1}，就不是
对于其他根节点 u
- 若存在儿子 v， low_v \ge dfn_u，则 u 是割点
- 若所有儿子 v 都有 low_v < dfn_u，不是割点

明天还会讲 $\mathbb{2} - SAT

今晚20:05CF只搞出A，B，寄了……

C正解想了一半，但是群里打的人都寄了……

23:16，金华开始下大雪……

晚上23:30睡觉……

Day5 2023.01.16

早上鼻血血流不止，因为我晕血，所以有那么一分钟出现了恶心的症状。可能是最近两天太累了。吃完早饭，为了精力，又闭眼了半个小时。

今天讲了 2-SAT 和线段树进阶用法，反正mjy在台上兴奋地讲，我在下面听得昏昏沉沉……

下午打了场三人ACM赛，我、phx、阿来一组。我们前一个半小时，phx切了两道，我们稍稍帮助了他，大部分是他自己搞的。阿来打了M，但是也WA了。后来我想到了一道大概是绿题的D的正解，于是打了一个小时。好多样例都过了，就是有一个毒瘤数据，A不了。后来phx又打A打挂了。阿来M又挂了。随后phx破防了，开始口吐芬芳……我又搞了半个小时D，还是有毒瘤数据WA。5个小时，我们三个做出两道，在初一队伍排名第一……

szh和zlx是一队，他们基本没有交流，自己做自己的，每人切了3题。太巨了！LZ还有2人队狂切7题！！！！！！！！！天差地别啊！！！！

晚上23:00睡觉……

Day6 2023.01.17

讲了同余最短路进阶版，想出正解起码2小时 ~~（普通OIer根本想不到）~~

较短路计数：

用dp实现。令 dp_{u,d} 表示 1 \to u 的，长度为最短路 + d 的路径条数。枚举其路径上前驱 v ，假设连边 (v \to u, w) ， dis(1, v) + d' + w = dis(1, u) + d ， \therefore d' = dis(1, u) - dis(1, v) + d - w ， \therefore d' \le d。那么什么时候会成环？所有的 w 都为最短路之差，由于成环，环上点 dis 值相等，\therefore环上边权全为 \mathbb{0} \implies 无解。否则在DAG上dp即可。

然后就是什么高斯消元、环形dp，感觉水了好多，起码能听得很懂。

今天比以前两天好受很多……

今天有两份代码被mjy评为优秀作业（其实都k过tj了）……

晚上23:00睡觉…… ~~（play bedminton with the bed）~~

Day7 2023.01.18

早上收拾了一下行李，因为今天傍晚要回慈溪了。

状压dp：

枚举子集：

枚举 S 的非空子集，从全集开始从大到小枚举。

for (int i = s; i; i = (i - 1) & s)

一些例题变化多端，十分鬼畜…… ———————————————————————————————————————————————————————————————————— 下午15:30，phx爸妈来接我和phx了。由于我爸的左手还没完全好，妈妈又不会开路况复杂的高速，所以就托phx爸妈带我一个。车子开得很快，18:30就从武义到了慈溪前应路，比导航预计快了半个小时多。感谢phx神佬和他得父母！ ------------- 总结：收获满满，不虚此行！本游记至此终……