2025 年 5 月日祭

今日歌曲：Fifteen

又断更了半个月。

前几周学了一下 AC 自动机，~~但是学了跟学了一样。~~

前几天终于把那套题出完了，~~但是出了跟出了一样。~~

昨天考试，听了评讲，~~但是改了跟改了一样。~~

晚上打 ARC，~~但是打了跟打了一样。~~

[Atcoder ARC197C] Removal of Multiples

唐题啊，但是赛时一直在想整除分块之类的，结果没想出来。

但是这题也就真纯唐，用线段树维护区间内留下的数的数量即可。需要证个上界。
[Atcoder ARC197D] Ancestor Relation

好题啊好题。记表示矩阵的第行的内容（用 bitset 维护）。

考虑什么时候有。因为与孩子有关系的节点一定与祖先有关系，但与祖先有关系的节点不一定与孩子有关系。所以有或，前者对应是的祖先，后者则对应是的祖先。容易证明这是一个充要条件，那么若，则一定不存在与。

接下来考虑一种特殊情况：，此时在一条没有任何分岔的一条“链”上，那么这条链上的节点的位置就可以互换。设一组相同的点的数量为，那么这一组点可以带来的贡献。

此外，，显然需要有。那么我们就总结出以下三条条件或贡献：
- 。
- 或，当且仅当。（等价于：，当且仅当或。）
- 对于极多的个相同的数，可以带来的贡献。
于是按以上三点计算即可。

由于宇宙射线的影响，这里遗失了一篇日祭。主播不想补日祭了。

前几天又断更了，应该是在补 CQ CCPC 的题吧。主播不想补日祭了。

（我明明写了的，可不知道这篇日祭怎么就消失了。）

今日歌曲：High Infidelity

前天又学了一下 exgcd。主播不想补日祭了。

今天考试。

A - 三重移位（[Atcoder ARC136B] Triple Shift）

略为神秘。观察到，进行一次操作后，逆序对个数的变化量一定是偶数，所以与的逆序对个数的差值必须是偶数。另外，当中存在重复的元素，那么相当于可以造一对逆序对出来，此时一定有解。
B - 最小差分和（[Atcoder ARC147C] Min Diff Sum）

题解。

更好的做法如下：假设当前有序，那么可以拆贡献。拆下来是。于是让尽量小，尽量大。将降序排序，将升序排序即可。（主播不想写了，看不懂就去看原题题解吧。）
C - 前缀与后缀（[洛谷 P9180] [COCI 2022/2023 #5] Slastičarnica）

[To do]
D - 贪吃蛇（[洛谷 P7078] [CSP-S2020] 贪吃蛇）

[To do]

今日歌曲：You’re on Your Own, Kid

今天叕考试。

A - 红魔乡（[TopCoder 15693] Fixed Point Reversals）

显然好做。把翻转区间看成交换元素即可，唯一的限制是当交换的两个元素在的两侧时，这两个元素需要关于对称。
B - 妖妖梦（[洛谷 P4576] [CQOI2013] 棋盘游戏）

当且仅当黑棋和白棋出生在一起时，白棋能赢，否则赢家一定是黑棋。那么黑棋就尽量快速解决战斗，白棋就尽量多拖延，所以白棋转移状态时取最大值，黑棋选择状态时取最小值即可。
C - 永夜抄（[TopCoder 10945] Rectangular Island）

long double 还是太玄学了，竟然草过去了。发现左右移动和上下移动其实是相对独立的，所以单独处理即可。设表示在左右方向上移动了步，还在格子里的概率，同理，它们是可以处理出来的。接下来枚举表示左右方向上移动的次数，那么此时的贡献应该是。显然容易维护，可是发现这东西容易炸掉，又发现在计算和时一共恰好迭代了次，所以在计算和时每迭代一次时乘上即可。
D - 花映冢

题目：给定一个图，点数和边数都是级别的，可能有环、自环和重边，求是否存在一条从出发的路径可以经过所有点至少一次。（可以重复经过边或点）。

题解：显然先把自环和重边判了，接下来 Tarjan 缩点，再拓扑排序即可。

今天补题。见 5.22 与 5.24。

今日歌曲：Cruel Summer

今天继续补题。见 5.22。