国庆-DAY5总结

YYY posted @ 2015年10月12日 12:02 in OI相关 with tags gcd 最小生成树 , 406 阅读

_THIS_IS_START_OF_ARTICLE_

resistance : superoj912

假设有电阻(A/B)

发现可以加一个电阻得到 (A/(B+A)) 或 ((A+B)/B)

因此可以把A,B辗转相减直到0，操作次数就是答案

然后发现这个过程是在求GCD，可以用欧几里得算法求GCD

Mst ： superoj913

如果要变某一个边，一定是加入一个变化过的并不在MST上的边(u,v)，

并去掉MST上的某一个边w，并且w是MST上u,v之间最大的边，可以n^2预处理之。

Deconvolution ：superoj914

暴力即可

_THIS_IS_END_OF_ARTICLE_

YYY