A签到
C简单题
D最短路、树相关 待补
F数学、思维
首先由于$n’$最终取值范围为$[1,n]$，所以枚举$n’$可以得到一个$O(n)$的做法
然后把$[1,n]$分块为$[1,\sqrt m],[\sqrt{m}+1,\min\{n,m\}]$两部分，枚举第一部分n’取值，复杂度$O(\sqrt n)$，对于第二部分，可以把式子写成$m’=n’k$，此时$k$的取值范围为$[1,\sqrt m]$，枚举k，对于每个固定的k，可以找到一个贪心方案使代价最小，所以第二部分的代价也是$O(\sqrt m)$.
阅读全文
MorphLing
4月 29, 2021