GDOI 2026 游记

Day -11 ~ Day -2

Day -1

Day 0

Day 1

• 思考怎么统计答案，对于一个点 $u$，如果他的 $\mathrm{fa}$ 选择了他为重链，那么 $\mathrm{fa}$ 的其他儿子的子树就都要多走一条轻边，那我就是要求一个点被选中的概率。
• 概率有两部分组成：当前链长，儿子总链长，于是设 $f_{u,i}$ 表示 $u$ 点重链长为 $i$ 的概率，$s_{\mathrm{fa},i}$ 表示 $u$ 点儿子总链长（不包括 $u$）的概率，$f\to s$ 是树形背包。
• 忘记了树形背包正确复杂度写法，于是使用循环计算运行次数，捣鼓出了没假的写法。
• 发现 $s\to f$ 有类似 $F_{i}\gets G_iH_j(i+j)$ 转移结构，不会优化成 $n^2$，含泪 $\sum \mathrm{dep}_u\times \mathrm{sz}_u≈n^3$。
• $n=1500\to 300\operatorname{ms}$，$n=5000\to 8\operatorname{s}$，预期得分 $64'$。
• 鉴于 NOIP 本机 $10\operatorname{s}$ 测评通过，希望狗运多过几个点。
• 当前时间 $2\operatorname{h}30\min$。

• 完全没思路的题，直接拼分走起。
• A、B 很快拿下，但是 B 的构造结果似乎和答案不一样，但是长度一样。
• C 想了许久，想到一种别样的构造，还是只有长度和答案一样。
• D 没调出来，恼火。
• 预期得分 $45'$，但是鉴于 B、C 没写 checker，很有可能挂到 $15'$。
• 当前时间 $4\operatorname{h}$。

• 依旧拼分，时间不多了，随便拼。
• 拿下纯暴力 $8'$。
• 开始乱搞：异或和一样就 Yes，否则 No。
• 发现某性质样例全是 Yes，猜测该性质全是 Yes，预期得分 $14'$。

---

---

---

---

---

---

---

---

Day 2

• 写完了 T1 $n\log n+n$，预期得分 $60'$，随机数据下与样例 $2$ 都小于 $n$。

• 相信出题人会卡我，改写 $2n+\log n$，性质 B 写的 $n+\log n$，预期得分 $72'$。

• 没想到 T2 暴力，于是挂机了一个小时。

• 结束挂机，写了 T2 的 $p\binom n k$，预期得分 $16'$。

• 没搞懂 T3 的比大小是什么意思，写了个 $4'$ 菊花摆烂了，这几分也改变不了什么。