日记 - 伊埃斯的博客站

现在还不到放弃的时候。

Takahashi is Slime↗

感觉像奇技淫巧。

其实就是暴力扩展加上记忆化搜索，让它从 $O(\text{过不去})$ 变成了 $O(n)$ 的。

Vanya and Balloons↗

好久没做过如此酣畅淋漓的大模拟了。

我们看到数据范围： $n \le 1000$ ，这 $1000$ 有点说法的，因为如果正解复杂度是 $O(n^2)$ 的话，以 CF 那以严著称的数据肯定不会只开到 $1000$ ，起码也是个 $3000$ ，所以我们可以把它往 $O(n^2 \log n)$ 上想。

我们枚举 $i,j$ ，考虑找到 $d$ 最大的，以 $(i,j)$ 为中心，不包含 $0$ 的十字形。这个可以用二分解决。解决完这个，考虑如何求最大的答案。

显然不能先 $mod$ 再比较。看到这种超级大的数之间的比较的话，一定往套 $\log$ 上想。设我们最大的十字形里有 $res_2$ 个 $2$ ， $res_3$ 个 $3$ 。那么这个十字形的答案就是 $2^{res_2} \times 3^{res_3} = 2^{res_2} \times 2^{res_3 \times \log_2 3} = 2^{res_2 + res_3 \times \log_2 3}$ 。于是我们把 $res_2 + res_3 \times log_2 3$ 作为 $(i,j)$ 的权值，于是我们找到权值最大的 $(i,j)$ 作为答案就是了。

猫 / Tura Mačkica↗

我们考虑当无向边形成一棵树的时候怎么做。

我们发现一条路径合法当且仅当只保留这条路径上的边和点时，每个点的入度都等于出度。于是我们设 $dp_u$ 表示 $u$ 的入度减出度。dfs(u)。回溯之后，当 $dp_u > 0$ 就 dp[u]--,dp[fa]++，表示这条边定向为 $fa \to u$ 。当 $dp_u < 0$ 就 dp[u]++,dp[fa]--，表示这条边定向为 $u \to fa$ 。

在 dfs 完了之后，我们判断一下每个点的 $dp_u$ 是不是都是 $0$ ，如果不是 $0$ 就说明无解。但是欧拉回路还要求连通，使用并查集。我们把所有定了向的 $u,fa$ 都 merge(u,fa)，把所有的有向边 $u \to v$ 都 merge(u,v)，最后判断一下是否连通就是了。

如何做基环树呢？我们考虑掏一条在环上的边 $s \leftrightarrow t$ 出来，枚举它的三个方向： $s \to t$ 、 $t \to s$ 、不经过，然后分别求解就是了。

时间复杂度 $O(n)$ 。

后日谈

不败的天才就此逝去，不屈的帝王就此诞生。

我能成为帝王↗吗？

Thanks for reading!

日记

周四 10月 23 2025

604 字 · 3 分钟

life 日记