20220814NOI模拟赛--考后总结

时间安排

8:30–8:35 读题。
8:35–9:00 目测一下，T1可以点分治，T2估计是个均摊复杂度的东西，部分分可以套路做，T3不知道是个什么东西。
9:00–10:30 T1,二分答案点分治，得到一个路径长的下界，然后暴力合并。写完后发现跑了 20 s，非常自闭。略微重构了一下，写的好看点卡到3s左右。
10:30–11:00 T2, or 和 and 的部分分是个套路。对于均摊复杂度没什么想法。想到按位做什么的，不过没什么用。
11:00–11:30 T3, $n\le 10$ 直接阶乘枚举。其他没什么想法。想到折半状压什么的，不过没有有点用。
11:30–12:30 思考T2.
12:30–13：30 卡T1的常。

回顾&反思

T1: 点分治，比赛上写了好久，对这一部分有点陌生了。貌似有其他更优秀的做法，仿照 “超级钢琴”?
T2: 吉司机论文题。对吉司机要复习复习。
T3, 行列式+随机化，利用行列式与阶乘的关系转化，由于行列式是乘积的关系，题目要求的是和的关系，那么把权值放在行列式中元素的指数上就可以了。具体不是很懂。
T3 题解