日记

周一 7月 21 2025

365 字 · 2 分钟

15岁了。

Dynamic Shortest Path↗

发现 $\Delta w = w + dis_u - dis_v$ 。我们整一个新图，图中的边权就是 $w + dis_u - dis_v$ 。（ $dis$ 还是原图里的最短路）然后跑出来最短路 $add_u$ ，可以发现 $dis_u \gets dis_u + add_u$ 。

那这有什么性质呢？我们发现由于至多把 $c$ 条边的边权 $+1$ ，所以最短路至多加 $c$ ，也就是说 $add_u \in [0,c]$ 。我们可以扔掉 dijkstra 的堆，改用一个桶，dijkstra 的复杂度就降成了 $O(n + m)$ ，总复杂度 $O((n + m)(\log n + q))$ 。

Nezzar and Hidden Permutations↗

先把度数为 $n - 1$ 的扔出去。

考虑在补图上做。考虑一个补图是菊花的图能否构造一个 $p,q$ 使得 $p_i \ne q_i$ 。这个图补图是一个菊花意味着：菊花的根和剩下的点都没有边，且剩下的点成环。我们可以这样构造：

$p$ ：
$p_{root} = 1$ ，剩下的环上的按照 $2 \sim n$ 依次赋值。
$q$ ：
$q_{root} = n$ ，剩下的环上的按照 $1 \sim n - 1$ 依次赋值。

这样我们就构造出来了。

考虑把补图的生成树整出来，然后把他分成几个菊花。因为在补图中加边等于在原图中删边，所以原图也一定合法。

整出菊花之后直接构造就是了。

后日谈

都 7 月下旬了我还那么菜

~~发现这事的时候我整个人都在抖~~

Thanks for reading!

日记

周一 7月 21 2025

365 字 · 2 分钟

© 伊埃斯 | CC BY-NC-SA 4.0