526互联

IOI2020国家集训队作业 做题记录

发布时间 2023-07-29 10:33:37作者: 伍叁壹

约定

  • 【码】：标记为该题码量大，考验码力。

IOI2020国家集训队作业 Part 1

  1. CF504E Misha and LCP on Tree【码】：
    序列上的套路拉到树上。运用哈希的可加减乘除性，可以二分 LCP 长度。
    放到树上一样，维护每个点到根的正向和逆向的哈希值，询问时二分 LCP 长度，从起点开始跳长度，跳到当前 LCP 结尾，计算哈希。为了每次 O(1) 求 LCP 结尾，需要长链剖分预处理还有使用 O(1) LCA。理论上 CF 的应该使用双哈希，但是双哈希常数太大。
    8 秒，但我的常数的确挺大。My Submission.

  2. CF566C Logistical Questions：
    很清新的一道树上数学题。不得不说挺偏的而且做过基本这类套路都看得出来了。
    考虑答案重心具有什么性质：从重心开始不论往哪个方向走，路径和必然更大。所以考虑每次往某个点走是否更优。
    但若每一次对所有儿子计算一遍路径和是 O(n^2) 的，考虑求导优化式子。求导后即可 O(n) 计算每一次往哪个点最优。
    但直接跑仍然是 O(n^2) 的，所以使用点分治优化，最终 O(n log n)。
    2 秒，我跑了 529ms。My Submission.

  3. CF603E Pastoral Oddities：
    算是经典加边题型了。
    手玩推出度数全奇的等价条件：图中仅偶数个点。充分显然，必要易构造。
    看到问法：最小化最大边权。显然 Kruskal 排序，静态做法显然。考虑动态加边（这时候可直接上 LCT），发现答案单调。
    由答案单调可发现：一条边的“有用”时间段是固定的；可整体二分。
    对于第一个结论，我们可以找到每条边“有用”的时间段然后线段树分治；对于第二个，直接可撤销并查集维护整体二分。
    所以共三解：LCT、线段树分治、整体二分。后者复杂度 O(m log m log n)。
    4 秒，跑了 483 ms。My Submission.