普及组周赛27

A

首先能围住一定是在 x 轴和 y 轴上都有

由两点之间线段最短可知，围栏的长度就是这两点间的距离

$dis = \sqrt{x^2+y^2}$

所以找最短的 x 和 y 就可以啦。

B

就推导一下就可以啦

$4xy = (x + y - 1) ^ 2$
$(x + y)^2 - (x - y)^2 = (x + y - 1) ^ 2$
$2x + 2y - 1 = (x - y)^2$
$2a_i + 2a_{i-1} -1 = (a_i - a_{i-1})^2$
$2a_{i+1} + 2a_i -1 = (a_{i+1} - a_i )^2$
$2a_{i+1} - 2a_{i-1} = (a_{i+1} - a_{i-1}) * (a_{i+1} - 2a_i + a_{i-1})$
$a_i+1 > a_i > a_i-1$
$(a_i+1 - a_i) - (a_i - a_i-1) = 2$
$a_i - a_{i-1} = 2i -1$
$a_i = i^2$

code

C

如果 k > 1 那么成倍增长一定比一个一个加快，所以模拟就可以了。

code

D

两两之间的最短路

我们有F-W 蒜法

for(int k = 1 ; k <= n ; k ++ ){
    for(int i = 1 ; i <= n ; i  ++){
        for(int j = 1 ; j <= n ; j ++ ){
            dis[i][j] = min(dis[i][k] + dis[k][j] , dis[i][j]);
        }
    }
}

其中最外层是中转点(一定要放在最外层) 但中转点的顺序不影响，所以把这个拆开来就行。

code

题解 | 普及组周赛27

普及组周赛27

A

B

C

D