SD 互测

Day 1

T1 一眼二分答案。

T2 神秘数位 dp，花20min 左右过了样例，感觉有点虚还写了个拍子（暴力写的比正解慢），交的时候忽然发现最后的 \(ans\) 没有取模，非常可怕，幸好改过来了。

T3 开始读错题了，真无语，以为每个盘子只能用一次。。。由于看错题，想了好久还是不会，然后先开的 T4。

想了一会，感觉只会 \(\mathcal O(n^2\log n)\)，发现了一点性质但是没注意，赛后发现甚至比较接近正解，感觉再想下想想说不定有希望。。赛时由于感觉时间不多了打的暴力，拿了链和菊花的部分分 48pts 直接跑路。

回来看 T3，发现读错了题，非常自闭，稍微想了想感觉差不多会了。

首先转化为图论模型，\(f_{i,j}\) 表示走到了第 \(i\) 个桩，用的第 \(j\) 个圆的最小代价，然后随便跑最短路。\(m\) 看似大的可怕，但由于 \(r\) 的限制，有用的实际不多，开始的时候单调栈优化一下，踢出 \(r_i<r_j\) 并且 \(c_i>c_j\) 的 \(i\)，然后暴力 \(\mathcal O(Tn^2m^2\log(n^2m^2))\)。跑大样例发现 200ms 左右，虽然复杂度是假的，但是感觉问题不是特别大。这个东西赛后测的发现是能过的，但是赛时的代码出问题了，导致挂了 32pts，疼死了。

正解是后缀优化建图，即 \(r_i>r_j\)，若 \((u,x)\) 转移到 \((v,j)\) 合法，则转移到 \((v,i)\) 也合法，所以直接只转移最小的 \(j\)，然后点内差分之后后缀优化建图复杂度就是 \(\mathcal O(Tn^2m\log (n^2m))\)，赛时为什么想不到呢/kk/kk。

更优秀的做法是 \(\mathcal O(Tn^2m)\)，咔头了。

T4 咕咕咕

最后总分 \(100+100+68+52=320\)，T4 数据真的水，一个 \(2\times 10^4\) 的数据竟然放的 \(\leq 5\times 10^3\)，多过了一个点。竟然 rk5/jy。

总结：首先 T3 读错题是致命的，直接少了近 1h 的有效思考时间，T4 也没来得及深入思考。其次 T3 没想到后缀优化建图，本来能过的暴力也挂了。

ps:

高二学长们每周五下午第二节是唯一的体育，教练说要打比赛的时候都觉得体育上不了了，但是我们的山东一哥 do_while_true 只花了一个小时就 AK 了，并且他是本场唯一 AKer。然后他直接去上体育了/kt/kt/kt。