某岛

… : "…アッカリ~ン . .. . " .. .
January 12, 2022

NOI 2021

Day 1

轻重边

P7735 [NOI2021] 轻重边
对于每次操作打一个新的时间戳,用这个时间戳对路径染色,那么。。。
重边数 = 相同颜色的相邻点对数 = 路径长度 – 颜色段数,于是只需要求出颜色段数。

[SDOI2011]染色 的代码稍微改改即可。

路径交点

P7736 [NOI2021] 路径交点
LGV 引理

庆典

Luogu P7737 [NOI2021] 庆典
https://djy-juruo.blog.luogu.org/solution-p7737

图论题,算法都不难,但是要拼的东西很多,比较考验底力。。。暴力 Floyd 可以拿 20 分。。

正解先 scc(),然后题目的条件告诉我们可以用树来代替 scc() 后的 dag 去表示可达关系,
k=0 的情况,直接在树上用前缀和减减即可,然后 这个题解 告诉我们可以使用虚树来避免讨论 k。。

我们用 atl 里提供的 scc()
再从 这个题里找来 lca,(用倍增祖先我会 TLE。。)
再从 这个题里找来虚树

最后缝合在一起,暴力 bfs() 即可,(Floyd 的话貌似要开路径数和权值和两个数组。)

btw,无论 Kosaraju、还是 Tarjan,都是基于 dfs() 的算法,强连通缩点完成之后的结构,都是满足逆向拓扑序的,取反后,直接把 1 号节点作为根节点即可,可以省一个拓扑排序。。。
– https://stackoverflow.com/questions/32750511/does-tarjans-scc-algorithm-give-a-topological-sort-of-the-scc

Day 2

量子通信

密码箱

机器人游戏

P7740 [NOI2021] 机器人游戏