CSP-S 2022 赛后总结

Max_s_xaM · 2022-10-29 22:57:37 · 个人记录

CSP-S 2022 赛后总结

比赛复盘

看完题，感觉 T2 可做，分正数、负数、零三种情况，用 ST 表维护最值，分别与数列 B 的最大、最小值相乘，使最小值最大。零的情况用 lower_bound 查找，没判找不到的情况，挂了。耗时 1h。

T1 先用 O(n^2) 的 bfs 求多元最短路，再维护以点 i 为终点，通过另一个景点（不超过 k 次转车）到 1 号点的分数第 1 至 3 大值。枚举两个不同的点 i 和 j，考虑将刚刚维护的值合并。枚举第 1 至 3 大值，如果通过的点不重复，就更新答案。总时间复杂度 O(n^2)。耗时 1.5h。

T3 想了大约 0.5h，没想出来。剩 1h，开始写 T3, T4 暴力。Vscode 中途出了问题，耽误导致最后 T4 没调完。

总结

提高代码速度和准确性；注意比赛时间分配，最后 1.5h 必写暴力；重视模拟赛。