Day1的3题都有点神，除了T1秒出以外，T2、T3都看了题解才会做，自己还是太弱了啊，以后得努力了。
T1 转圈游戏
显然答案为$\left( x+m \times 10^k \right) \bmod n$，用快速幂算出$10^k \bmod n$就行了。
另外似乎找循环节也行。
代码在此。
T2 火柴排队
$\sum_{i=1}^n{{\left( a_i-b_i\right) }^2}$可以转化为$\sum_{i=1}^n{{a_i}^2}+\sum_{i=1}^n{{b_i}^2}-2\times\sum_{i=1}^n{a_i\times b_i}$
这个式子的前两项与火柴的排列无关，所以可以得出当火柴按高度顺序一一对应时（即a中最高的和b中最高的在同一个位置，相应地两列中次高的也在同一位置，以此类推），距离值最大，证明如下：
若$a,b,c,d$为实数且满足$a\geq c,b\geq d$，则有
$a\times\left( b-d\right)\geq c\times\left( b-d\right)$
$\Rightarrow a\times b-a\times d\geq b\times c-c\times d$
$\Rightarrow a\times b+c\times d\geq a\times d+b\times c$
把这个式子推广一下，就可以得到这题需要的结论了。
有了结论以后，逆序对乱搞就行了。
代码在此。
T3 货车运输
首先可以发现求出最大生成森林后求出的最优解就是原图上的最优解（大家都说是显然的，但我这个蒟蒻看了题解才知道，还不会证，感觉智商瞬间被碾压
），那么Kruskal跑一遍，再求LCA就行了。
求LCA时有一种偷懒的方法，Kruskal用的并查集可以不路径压缩，而是启发式合并，即树高小的树合并到树高大的树下，可以证明树高不超过$\log_2{n}$（我又不会证
），然后就把并查集的森林作为求出来的最大生成森林，暴力跑LCA回答询问，每次回答询问的复杂度为$\mathcal{O}\left(\log_2{n}\right)$（因为树高不超过$\log_2{n}$）。
代码在此。
评论 (0)
