2024/02/12(#14)：万物生辉

伪造的。

Fake Love.

最近在玩《秽翼》，感觉是非常厉害的作品！整个作品的世界观目前感觉非常震撼！

可以联想到《斗牛》的歌词：

性向善，才是人类最后的骄傲和胜算！

找到自己认为对的事情，然后一直坚持下去

[PKUWC2024] Caught in the Middle

Portal.

发现 Bob 想要赢是非常困难的，将 R 视为左括号保留右面的东西，L 视为右括号保留左面的东西，然后完美括号匹配是后手赢，因为可以下模仿棋杀掉一个完美括号匹配，否则先手可以先把它变成完美括号匹配。代码。

[Baltic OI 2018] Love Polygon

Portal.

一开始形成二元环得扔了，直接模拟即可。注意自环不能连，可能两个自环分成一组，也可能自环被其它拓扑排序时遍历到得节点拯救。代码。

以后尝试能不能将作息调整的正常一点！

想在这里放一张图，但是不知道放什么好！

今天还再次听了几次《神树》，似乎终于能理解一点这首歌了！！

[UOJ838] 龙门对决

Portal.

树形 DP 计算出无头骑士和有头骑士的数量就行了，注意逆元会爆炸。代码。

[BalticOI 2018] Genetics

Portal.

超级无敌炫酷牛 X 乱搞题，惊讶到了。

好像只会 $O(n^3)$，事实上也的确如此。用 $4\times n$ 个 bitset 维护是一个不错的选择，随机一个顺序可以在 LG 上过掉，但是还是比较慢。代码。

需要聪明一点的做法。比如，统计差异的和？随机分几组看上去就不错，但是很可惜，会被构造一种满足有很多近似解的数据给卡掉。那么加权 Hash 给字符串加权就可以了，可以在 QOJ 上通过。代码。

[eJOI2022] Adjacent Pairs

Portal.

首先，如果在修改的过程中不存在已经初始存在的对，那么直接枚举对的其中一个数几个。否则枚举最终修改对来统计答案即可。代码。

[eJOI2022] Where Is the Root?

Portal.

就是你要去问 $9$ 次一个集合的 LCA 是否在集合内去找一个 $500$ 的已知树的形态的树的根。

首先是一个事实，如果我带上所有叶子去问的话，那么 LCA 一定是根。

那么直接将所有的叶子加入询问，二分即可。但是这样会有一个问题，就是在剩下两个点的时候，它们都是叶子，然后就把另一个叶子扔了，就寄了。

把到其中一个叶子的孤独链（边上不含有任何东西）给杀了，然后问剩下的就可以了。代码。

[eJOI2022] Game With Numbers

Portal.

可以发现这个东西是这样的，如果 $m$ 比较大，那么每次至少玩家二能杀掉一半的数，答案最后就变成 $0$ 了。

然后只有 01 关系，$O(nm)$ 建立 01 Trie，直接 DP 即可。代码。

[CF1768F] Wonderful Jump

Portal.

直接 DP：

$$f_i=\min_{j<i}\{f_j+(i-j)^2 \times \min a_{i\cdots j}\}$$

如何优化？首先可以发现，最小值的取值一定在跳的区间的左端或者右端，否则拆开跳一定更优。

还有一个诡异的是 $a$ 的值域，考虑一个一个跳，有：

$$(i-j)^2 \times \min a_{i\cdots j}\le (i-j)\times n\\ ~ \\ i-j \le \frac{n}{\min a_{i\cdots j}}$$

枚举每个 $a_i$ 作为最小值进行转移，根号分治一下可以得到 $O(n\sqrt{n})$。代码。

[CF1764H] Doremy’s Paint 2

Portal.

首先破环成链，然后从后往前推，$f_i$ 表示 $i$ 能够存活到的时间，使用珂朵莉树维护 $f$ 的连续段，每次相当于 $l$ 取 $\max$，$l+1\sim r$ 区间染色，在 BIT 上维护答案即可。代码。

《秽翼》真的是太感人了

对我来说好像有点感人过度了。

我，存在的意义是什么？

也许现在会有些许迷茫吧，所以才要去拼命的寻找。