Odalys

雀氏码农场，一道构造后的大模拟，一道恶心的数据结构，相形见绌的网络流。 感觉对期望的理解始终不强。 这题又利用了期望的线性性。考虑每个点被删除的概率。总期望就是每个点被删除的期望之和，不难发现就是每个点被删除的概率之和。 每个点何时会被删除？设他的度数为 $d_i$ ，那他会被删除的概率就是 $1- {1\over d_i + 1}$。 不会的 DS 题 大模拟题。…

有个换根的操作十分麻烦，于是考虑并不真正地换根。 考虑以 $1$ 为根建树，如果你目前被换成的根为 $rt$ ，那对于点对 $(u,v)$ 的 $lca$ 是什么。 手玩一下不难发现是 $lca(u, rt), lca(u, v), lca(v, rt)$ 中深度较为深的那个。 那么现在我们要处理的问题就变成了维护 $lca$ 的子树和。 维护子树和，是 $dfn$ 的一个经典运用，考…

感觉这场比赛还是存在很多问题的，比如说 T2，T3 完全没有认真思考而是武断地将其规约到我不会的知识点然后摆烂，并且死磕人类智慧的 T4 考试的时候想到的两条结论： 选择多的放在统一生产线上并不优秀，所以贪心地把大区间独立为生产线。 若要选择一些在同一生产线上一定会选择按左端点排序后相邻的一段。 然后结合一些这些结论，假如说有一个区间 $A$ 完全包含了区间 $B$…

Links 考虑两种限制： 对于第一种限制，我们设 $F(u)$ 为 $u$ 点在 $S$ 到 $T$ 的最短路径上出现的次数，那第一个限制就是要满足 $F(a) + F(b) = F(t)$ 这个 $F$ 可以用两次最短路求出。 对于第二种限制，我们可以考虑枚举每个 $u$ 算答案时来满足，即，你枚举一个 $u$ ，那 $v$ 的 $F$ 值你可以算出来，那你用一个桶装 bitset 即可找出满…

这一部分的总结先鸽一会。 莓在执行任务时，收集到了 $n$ 份岩浆能源，其中第 $i$ 份的能量值是 $w_i$ ，她 决定将它们分成恰好 $k$ 组带回基地，每一组都要有至少 $1$ 份能源。 每一组能源会对运输设备产生负荷值，若该组有 $x$ 份能源，这 $x$ 能源能量值之和为 $y$, 则产生的负荷值为 $x\times y$ 。 每种分组方案产生的负荷是每一组能源产生的负荷值总和，莓…

实际：100 + 70 + 0 + 0 能做：100 + 100 + 0 + 0 这场的 T1 比较简单但花了 2h 才写出来，导致浪费了很多时间 考虑两个点之间的连边只有出现奇数次的才会再最后被算到 于是使用 ll 模拟 bitset 即可。 ~这种题为啥我会开始认为没有单调性呢？~ 于是二分一个答案 $x$ ，现在要求每个段平均值大于等于 $x$ 要能分到 $k$…

设 $E_i$ 为 $i$ 到 $i + 1$ 期望步数

期望：100 + 0 + 0 实际： 0 + 0 + 0 又 boom 0 了 T1 没调出来 + 暴力写挂 传世经典 考虑合并两棵树 $x,y$ 对答案的影响，设第一棵树的大小为 $siz_u$ ，原答案为 $ans_u$ 。 设合并点为 $a,b$ 路径长度为 $v$. 那合并后的答案就是： ans_x+ans_y+v\times siz_x\times siz_y + s…

预期: 100 + 100 + 100 + 60 = 360 实际: 100 + 50 + 100 + 60 + 310 最高: 100 + 100 + 100 + 60 = 360 挂分挂在了 cout 上 /sad T1 考场上 1min 就猜到了结论，没开 ll 吃了 1min 罚时，于 9min AC 如果是正式比赛可能会花个 20 分钟打个表验证一…

写了 100 + 30 + 30 + 0 可以 100 + 30 + 100 + 0 阶梯 NIM 忘记了，那没事了 T3 属于是学傻了，使用到了正睿集训遇到的小技巧然后生生转成了一道 Ynoi ，然鹅以前记过的一个简单结论可以快速做出此题 给你一些二元组 $a,b$ ，求 $x,y$ 使得…