Day -4
教练从代码源整来一套模拟赛，yx 又登顶了/kt/kt/kt。
T1 太恐怖了，完全不会，但是 cly 一眼秒。排序之后如果不考虑合法性，一定是 \(1\leftrightarrow 2,2\leftrightarrow 3\dots 2n-1\leftrightarrow 2n\)。然后加上限制，发现如果当前配对 \(2i-1\leftrightarrow 2i\) 不合法，就说明它需要和左边的数字对或者右边的数字对进行重组，而重组的代价是原本一个间隔没有被算到答案里，现在需要算两次。容易发现这样一定是最优的方案，否则会造成更多的贡献。然后就可以直接 DP 了。\(f_{i,0}\) 设强制第 \(i\) 个数字对右边的间隔不选的最小代价，\(f_{i,1}\) 为强制选的最小代价，转移方程是平凡的。
T2 大模拟，复刻今年 T3 是吧。
T3 不会。
T4 神奇题目。赛时思路：分块。块外的点要到达块内需要到达块内的某个点一定需要经过最边上的 \(20\) 个点，然后每个块内预处理每个点到这 \(20\) 个点的最短路，然后大块之间在连边，处理两两关键点间的最短路。计算答案就是枚举两个点所在块的关键点。但是两点在同一块内要暴力跑块内最短路，如果数据够毒把边全部集中在一个块内然后对着这个块疯狂询问就噶了。
分析一下复杂度。设块长为 \(B\)，对于一条边，如果两端点在同一块内则会对 \(20\) 个关键点产生贡献，设 \(a\) 为这种边，所以第一部分预处理复杂度是 \(\mathcal O(20a\log a)\)。对于第二部分，需要处理任意两关键点最短路，边数最多为 \(\dfrac{n}{B}100+m-a\)，需要跑 \(\dfrac{n}{B}20\) 次，理论复杂度 \(\mathcal O(\dfrac{n}{B}20(\dfrac{n}{B}100+m-a))\) 但是实际跑的非常快。第三部分自然就是 \(\mathcal O(q 20^2)\)。然后就会发现 \(B\) 全部在分母上。但是如果两点在同一块内就要暴力，经过测试和调整，最后 \(B\) 取的 \(1500\)。看似过不了一点实际跑的还是很快的，CF 能过，但是赛时被卡 T 了/fn/fn。
正解是分治，每次选取分支中心左右的 \(20\) 个点，预处理到各自部分的最短路。如果两个端点在两部分内，则证明一定需要经过这些关键点，答案更新完毕。否则需要继续向下递归，复杂度 \(\mathcal O(10m\log m+q\log m)\)。
标签：20,NOIP,短路,leftrightarrow,mathcal,游记,复杂度,关键点 From： https://www.cnblogs.com/WrongAnswer90-home/p/17833306.html