GDOI2026游寄

· · 生活·游记

Day 0

由于noip很答辩，今年省队没戏了，所以就当玩玩，心态很好。 晚上 11:30 才睡，是不是太晚了？

Day 1

倒开，先把 t2t3 暴力以及部分分打了，两个半小时打了 42 分，我这也太慢了。

看 t1，感觉可做，只打了 10 分的不总司令于是就直接推正解去了。（神秘伏笔）

发现转移方程中有分母加减操作，不好处理，然后我猜了一个结论：计算某个节点连接他与他父亲的边的贡献时，可以直接用其兄弟的重链长度期望值之和作为分母。并写了代码，然后发现是错的。这前前后后大概有 1 小时。

发现这是个背包的形式，eps 秒想到前后缀背包 dp，然而这是 O(n^3)。

尝试继续化简式子，我发现可以加入一个辅助数组，记录以某个节点的儿子为链顶的重链长度和为 L 的概率，这样式子明显变成一个树形背包的样子。

不过辅助数组可以直接树形背包求，但答案的式子中还需要去除背包中的一个元素。

想起做过的退背包，可以实现该功能，豁然开朗。这一路思维链很紧凑，这题也很好。

但现场此时可是 12 点多，人也困，导致这一路很显然的推理过程却想了好久。

此时也只剩 30 分钟了。

写写写。

最后，在最后 1 分钟过了小样例，感觉稳了。

回酒店后，记忆复原了一下代码，然后发现不对！大样例过不了？那这和过编有啥区别？？

然后我发现是退背包的过程出了问题。我们都知道退背包的过程是一个多项式除法，由于树形背包的缘故，直接暴力除即可，不需要啥 NTT。但我赛时的除法过程中，忘记乘了两个多项式的倍数关系，也就是 1 倍关系做减法了，而且甚至小样例没跑出来，导致直接保龄了，唯一剩下的还是最初那 10 分。呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜。

心情炸了，纪念馆也不逛了，ABC 也没打了，打了一下午晚上的游戏，这 142=52 的遗憾得多久才能平复啊。

由于 D1 没图论，感觉第二天会考 tarjan（没猜对），于是敲了些板子，晚上 11 点睡的，没有想象中的睡不着。

Day 2

先定策略，考虑 D1 炸了，所以 D2 必须激进，直接正序开，怎么说都得给 T1 做出来。

我起了，省选出交互题了，还是绿题（实际上是蓝）。

T1 1 小时不到秒了，怕不稳，写了个拍子，然后遇到了一件不知为何之事，卡了我将近 1 小时。

我拍的时候测小数据时，采用了 n=50,T=100 的造数据规模。然而每拍一段时间就会 wa 一下，然后手动运行 wa 的这个数据却又是 correct，给我人都整蒙了。

然后有一次无意中点到了 Ctrl+z，发现撤回后的结果并不是上一次的数据，而是让当前这 100 组多测数据截到 50 组，然后跑这 50 组的结果刚好是 wa（T 还是 100，所以 wa）。这给我打入未知领域了，以前从未见过，到现在我也不知道怎么回事，有无大佬帮我分析一下？

之后我就只开 T=10 的多测，就啥问题都没有了。

接着花了一个半小时给 T3 打了 24 分。

然后又花了剩余的所有时间给 T2 打了 0 分的好成绩。（这 T2 连暴力我都一分不会，给我自己菜笑了）

估分 10 + 30 + 12 + 100 + 0 + 24 = 176 菜完了。