2023/12/01(#3)：不要这般留我一人在世

请装作，还没醒来的样子。

心は孤独だ
心是孤独的

愛は見えない
仍旧看不见爱

数値に出来ない感情
这份感情无法以数值衡量

でも震えている
但我还能动弹

脈を打ち続ける
脉搏仍在跳动

波に浮かぶ残骸のように
如同漂浮在浪中的残骸

《Before I Rise》，太感动了。

[AGC002D] Stamp Rally

无聊，建出 Kruskal 重构树就做完了。

[AGC002E] Candy Piles

Portal.

挺有意思的博弈论。

将权值从大到小排序，可以转化为网格图，那么从 $(0,0)$ 开始，操作就相当于向右或向上走一步。

两种操作

谁走到边界上的点谁就输了，因此如果从边界上的点开始，那么后手必胜。对于任意一个不在边界上的点，如果它的上面和右面都是后手必胜点，那么这个点一定是后手必败点，否则结果相反。

红色后手胜，蓝色先手胜

找到最大正方形，然后向上和右扩展即可。

红色

[AGC002F] Leftmost Ball

Portal.

为什么我不会？？？？？？？

考虑最终形成的合法序列，一定是 $k$ 个白色球加上 $n$ 中颜色的球各 $k-1$ 个，合法情况是前缀白球个数大于等于其它颜色数。

$f_{i,j}$ 表示 $i$ 个白球，放了 $j$ 个颜色的方案数。

决策有两种：

• 放置一个白球，有 $f_{i,j}\stackrel{+}{\leftarrow} f_{i-1,j}$；
• 加入新颜色的球，即从 $f_{i,j-1}$ 转移。系数是多少？首先需要在 $n-j+1$ 中选择一个作为这时放置的颜色，将其中一个放置在第一个空位，然后剩下的 $k-2$ 个在后面的 $nk-i-(j-1)(k-1)-1$ 中找 $k-2$ 个放即可。

然后就完了。代码。

中点

又大意了，上午好像有点摆。

祝各位 CTT RP++。

我也想去 CTT

怎么都老年选手了还这么菜啊。

[CF521E] Cycling City

Portal.

随便找到一棵生成树，条件是存在一条树边被两条非树边覆盖掉。那么直接暴力覆盖（最多完整遍历树两次），然后暴力求就行了。代码。

[南京 2020] Fireworks

直接三分就行。

[南京 2020] Ah, It’s Yesterday Once More

Portal.

有点鬼畜的题。按照阶梯构造一下就行了。

[CF526G] Spiders Evil Plan

Portal.

首先 $k$ 条路径可以覆盖 $2k$ 叶子的树。也就是说，选择 $y$ 个点就是能选择 $2y$ 个叶子，然后极小连通块的边权和尽量大。

以 $x$ 为根时如何选择叶子呢？考虑进行一次长链剖分，那么 $x$ 所在的长链的叶子也一定选择了，然后按照边权排序贪心即可。

多次询问怎么办？由于树上经过 $x$ 的最长链一定经过直径的某一端，那么以直径的两个端点分别做一次长链剖分，然后要想办法将 $x$ 加入连通块，只有两种方法：

• 将贡献最小的长链去掉，然后加入 $x$ 所在长链；
• 找到离 $x$ 最近长链的下半部分并替换。

倍增跳长链求出替换的东西即可。代码。

ED

摆的有点抽象了，本来这篇应该再多三道题的。

感觉昨天造了一天数据之后的效率不太行，看看明后天能不能恢复一点。别，慌。

再次疯狂吧！！