2024-08-15 训练总结

本场比赛发挥较好，把之前掉的 rating 都涨回来了。

其本质原因是想到了 t1 的做法，看来心态还是关系到比赛成功性的，如果觉得难，其实大家都觉得难，不一定要想到的！

作文批改 (File IO) (gmoj.net)

最下面的提示”提示：这题并不难“给了我巨大的心态启发，于是考虑哈希去。

因为 \(0\) 乘以任何数都为 \(0\)，所以我们只需要给 \(t\) 中每一个字符赋一个值，同时使得和为 \(0\) 即可。

那么就是找序列中和为 \(0\) 的区间个数，容易实现，跑了 \(10\) 次哈希。

然后就是 92 分。正解差不多，就是不考虑和为 \(0\)，只需要同余即可了。

行走在最短路上（shortcut） (File IO) (gmoj.net)

这题猜性质大成功，猜测了一个性质并通过了大样例，于是就交了（后面因为被卡常 80）

二分答案，要求就是 \(dis_{1,n}\ge dis_{mid,n}+dis_{1,mid}\)。

最小化 \(dis_{mid,n}\)，最大化 \(dis_{1,n}\)。

我们发现可以钦定每个边的长度。把 \(1,mid\) 同时丢入堆中跑一个 dij 来决定就可以了。

具体地，当一条边被松弛时，看到达的点是要求最小化还是最大化，然后决定选 \(L,R\)。

赛道设计 (File IO) (gmoj.net)

这次训练的一次失误在于没有打出 t4 的暴力。

这是一道大模拟构造题，思维同样在于分治。

我们考虑把 \(LR\) and \(RL\) 删掉，那么原问题最后就会变成 \(LLL,LLLL,LLLLL,RRR,RRRR,RRRRR\)，分类讨论，然后考虑怎么加入 \(LR,RL\)，其实并不难。

^---->        >--v
|    |  --\   |  |
|    |  --/ >-^  |
<----v      ^----<

然后大力分讨即可。

但是在比赛时我还是不会打这种题的，除非走投无路。

性价比远远低于其他题目，而暴力就有 44pts。

不如去想想怎么拿到其他题的部分分。