GDOI2026 邮寄
_ckx_
·
·
生活·游记
Day -114514
我*！妙妙题！加入做题计划，加入做题计划，加入做题计划···
为什么一点写代码的欲望都没有？就只想腐败？？？
Day 0
吃完午饭出发前往纪中。
我去还没出校门呢学肠直接玩起舟了，可恶我没手机。
到纪中了，签到领胸牌，这就是纪中吗！全维偏序我们学校。
欧格丽酒店，下午玩 MC，晚上吃肯德基。
Day 1
开场看 T1。
期望？
::::info[T1 考场思路]{open}
首先想了一个猎奇求重链期望长度的算法，但是复杂度 O(n)，看一眼 n \le 5000 立马丢了。
然后想到先拆贡献，转成每条边为轻链的概率乘下面那个点的子树的 siz，那么对于一个 u，假设他有 m 个儿子 0,1,2,...,m-1（为了公式编辑方便一些），那么对于一条 (u,v) 的边，它的贡献为：
ans \gets ans + \sum_{l_0,l_1,...,l_{m-1}}{siz_v \frac{slen_u-l_v}{slen_u}} \prod
_{i=0}^{m-1}{f_{i,l_i}}
其中 slen_u 表示 u 的儿子的 l 之和，f_{i,j} 表示 i 所在的重链目前长度为 j 的概率，后面那个连乘就是当前这个 l 序列的概率。
首先枚举一个 l_v，然后对着这个柿子看了半天后发现 slen_u-l_v 这个东西好像也可以再枚举，复杂度也是对的。
:::info[复杂度证明]
参考树上背包复杂度，其实就是考虑一个点对只会在它们的 Lca 处被枚举到 O(1) 次，所以总复杂度 O(n^2).
:::
然后这个玩意就简单了，只需要知道所有合法 l 序列的后面那个连乘的结果的和就行了，由于我们枚举的 slen_u-l_v 相当于是 u 的儿子长度序列中扣掉了一个 l_v，所以我们要算出扣掉 v 后的序列的概率，这个东西可以退背包或者搞个前后缀后合并两边。
最后的柿子就是：
ans \gets ans+\sum_{i}\sum_{j}{siz_v\frac{j}{i+j}d_{v,j}}
其中 d_{v,j} 表示扣掉 v 之后的 slen_u=j 的合法 l 序列的概率的和。
这题终于结束了，共用 1.5h。
::::
### 怎么会有堂食没有预处理逆元导致 $O(n^2)$ 变 $O(n^2logV)$ 呢？？？
终于不紧张了，开 T2！
我去，一点不会，30 pts 跑路...
T3！
依旧一点不会，打了 $m \le 2$ 的 24pts 跑路（我居然写了 150 行）。
出场感觉还行，syj 没调出来，为他悼棺 2s。
下午依旧 MC，晚上烧烤，爽。
### Day 2
我去，惊鸿一瞥：
### 交互型 传统型 传统型
？？？？有点意思
终于理解完 T1 完整题面后由于没想到前缀后缀 $\min$，搞了个神秘双指针做法过了，依旧 1.5h。~~做法写起来太麻烦了，懒得写了。~~
T2！
我去，第一眼直接吓哭了，$10^{-10}$ 秒断定我做不出来，想摆了。
居然可以把那玩意直接放编译选项里吗，我去，不早说，那我研究了那么久的 cmd 算什么。
T3！
当时直接看错题了，写了半天假的暴力，后面发现错了就开摆了。
一堆空集和空集的集合比较字典序 hyw。
剩下 1.5h 小恐龙+补觉。
出场后依旧为同学悼棺，吃完午饭就做车回学校了。
### 最后
做了一道紫和一道蓝，做了这么多题还是没有白费的，继续努力罢。