)
省流
极限翻车又极限翻盘，打出一个银尾。
11.4
内含剧透，请vp后再来。
不是题解！！！！！！！
赛前
在准备的时候，隔壁的 foracy 突然说要和我们队一起来竞争式学习，于是抱着挑战者的心态就上了。
赛时
一开始 yrjzs 和 jianfeijian 很快爆了 G，然后我读了一下 L 给空闲的 jianfeijian 讲了之后，他也很快爆了 L。此时 \(22min\)。
然后我和 yrjzs 一起看了 J，题目是给了一颗非叶子节点的儿子数量均大于等于二的树。给定两个点 \(x\) 和 \(y\)，执行以下操作，以 \(c_i\) 的价格购买一个节点 \(i\)，把 \(u\) 的任意两个不同子节点丢掉，然后获得一个 \(u\)。要求用最少的钱从只有一个 \(x\) 变成只有一个 \(y\)，或输出不可能。显然只有 \(x\) 在 \(y\) 的子树上时才可以搞定，然后提前预处理处每个父节点最便宜和次便宜的儿子，一路合并上去找到 \(y\) 就行。交了第一发没开 ll 挂了，修改后，因为一开始以为高度最高为 \(log\)，实际上还是 \(n\) 的，所以 T 掉了。考虑优化，首先通过 dfs 搞出每个点的进入和离开时间，如果 \(x\) 进入的比 \(y\) 晚离开的比 \(y\) 早就是在 \(y\) 的子树上。然后预处理出每个节点合成出根节点的价格，直接像前缀和一样减就可以了。\(88min\) 两罚通过。
我在码时 yrjzs 和 jianfeijian 一起搞了 F 题，然后 jianfeijian 又自己搞了 I 题，然后 yrjzs 上机，我去思考简老师的 I。I 题给了一个 \(n \leq 2000\) 个点的树，以及两两点之间路径的异或和，要求构造这样一个树。jianfeijian 搞了个很奇怪的构造，但我直接证了他的复杂度是 \(O(n^3)\) 的，就换思路。我发现无妨假设 \(1\) 为根节点，然后对于 \(x\) 和 \(y\) 如果 \((x,y) \oplus (1,x) \oplus (1,y) = x\)，那么 \(x\) 就是 \(y\) 的祖先。得到所有祖先关系后，利用一个类似拓扑排序的方式就可以构造出整颗树。\(173min\) 解决。
此时罚时非常好，只要他们两个搞出来 F 就稳银了，不过长期没搞出来，我只好亲自上。
在数轴上有 \(n \leq 2e5\) 只企鹅，每只企鹅有个目标，以相同速度向目标企鹅前进，如果遇到自己的目标企鹅就停下来。问每只企鹅停下来的时间。一开始想搞成一个环然后慢慢解套，感觉相当麻烦。然后试着考虑贪心，发现直接朝着目标走，最近的那个企鹅一定最先停下来，然后再修改以这只企鹅为目标的企鹅的停下来的时间即可，用一个堆就可以维护。在 \(290min\) 伴着队友之前的一发罚时通过，总罚时 \(643\)。
赛后
简而言之，就是任重而道远吧，这么顺利的一场都只打了银，而且稍微出一点差错就坠落到铜牌了。继续卷吧。
感觉赛时实战说不定就 J 先卡半天，然后 F 彻底卡死，I 题没有想法，最后铁首回家。希望这几天能让效果变好些吧。
2025年11月4日