20220729NOI模拟赛--考后总结

时间安排

7:30–7:35 读题。没看懂T1。
7:35–9:00 T3,猜结论交点在起点连线上，于是二分分界点，比较时间，要大量分讨。写完发现跑的巨慢，卡常。
9:00–10:30 T2,n<=5000 可以拓扑。链可以分治，归并。二叉树不知道怎么写，想到随机取点，然后做链，发现次数为 $n^2$ 左右，过不了。
10:30–11:00 T3,思考链怎么做，没什么想法。
11:00–11:30 T1,注意到当 $n>>{\log }_{2}m$ 时，答案就是 ${\log }_{2}m$，但当 $n<<{\log }_{2}m$ 时我就不会算了。不过注意到 $\log$ 很小，出题人如果憨了点估计造不出这样的数据。于是直接输出 ${\log }_{2}m$ 。
赛后:
T1 果真A掉了。小数据没有能卡的，大数据 $n,m$ 同阶，没有一点强度。
T2 的拓扑有个问题，丢了 30 。

回顾&反思

T1: 算是个简单DP，然后是二分答案。比赛的时候没有太读懂题，有点可惜。二分答案的技巧还是要掌握。

T2: 拓扑错了丢掉 30 太可惜了。这种交互题一定要多対拍。

T3: 比赛猜的结论错了，很自闭。将路径相交问题变为函数求交点的思想非常妙。将路径用函数表示，那么路径相遇问题就变为了求交点问题，将路径树剖，那么每一段都是连续的链，不用考虑多叉的问题。在求交点的时候，将线段排序后，在有交点之前，相对关系不变。这样维护好线段的大小后，对于一个线段来说，取交点的最优线段必然是与之相邻的。妙妙妙。