「Summary」2022-07-05 做题记录

额。

2022-07-05

$\mathbb{Tanya \ and \ Password}$

link

欧拉路显然题

把纸条的前两个字母，后两个字母扯开，分别 hash ，判欧拉路即可。

$\mathbb{Johnny \ and \ Megan's \ Necklace}$

link

我不会经典优化套路

答案的值域很小，可以直接暴力枚。
但是直接连边是 $\Theta(n^2)$ 的，然后可以搞一个《经典优化套路》。
分析连边的性质，显然是跟 lowbit 有关，若这条边的边权为 $k$ ，则两点点权的后 $k - 1$ 位相同。
可以建虚点 $sta = (1 << i) - 1$ , 权值为 $val$ 的点向 $val\& sta$ 连边，然后 $O(n)$ 判是否有欧拉回路。