「Summary」2022-06-27 做题记录

Tricks! Tricks!!!

2022-06-27

$\mathbb{CF196E}$

link

属于是技巧性很强的一道题了。

首先看到题面中任意两个传送门之间可以互相不耗时到达意味着回头路不算，可以想到是生成树；对于找多源间最短距离，可以首先改良版 $spfa$，找到距离每个点最近的源点，对于原图中的一条边 $(u,v)$ , 记 $fr_u$ 为离 $u$ 最近的源点，那么 $fr_u \rightarrow fr_v$ 的距离为 $(fr_u, u) + (u, v) + (v, fr_v)$

$\mathbb{CF241E}$

link

坑比题，给我调 yue 了。。。

对于一条有向边上两个点的距离只能为 $1$ 或 $2$，并且整张图是 $DAG$ 那么可以差分约束处理；注意坑点是首先应该去掉那些不在 $1 \leadsto n$ 上的节点。

$\mathbb{CF1450E}$

link

数据范围；判断 $DAG$ 中关系注意奇偶环性质；

首先明确，图中出现奇环必挂，对于偶环，若出现负圈也挂。
技巧是判奇环可以 $floyd$ 跑，如果一条边上两个端点到同一源点的路径长奇偶性相同，则存在奇环。