Codeforces Round #718 ABCDE 题解

A. Sum of 2050

题意

给你一个$n$，问你这个数最少由若干个$2050\cdot 10^k$组成。

题解

显然$n$必然被2050整除。那么$\frac n {2050}$的十进制的每一位都由对应的$10^k$组成就好。所以就是求$\frac n {2050}$每一位的数字之和。

代码

B. Morning Jogging

题意

有$n$个检查站，任意两个检查站之间有$m$条路，每条路的开销为$b_{(i,j)}$。现在有$m$个人去探路，每个人的开销是他走过的所有路中的最小的$b_{(i,j)}$。要求每条路都被走过，且开销最小。问怎么走。

题解

显然，对所有路排序，把开销前$m$小的路依次分给$m$个人。后面的路随便怎么分都一样。

代码

实现思路

对所有边按长度排序是非常常见的。但这里实现起来比较恶心的地方在于，完了之后相当于有一些预定的选择之后，再把边填回去。
所以我自己的做法是，选出$m$条边之后，再按检查点和边重新排序。

C. Fillomino 2

题意

给你一个$n\times n$的棋盘。对角线上已经填了一些数字。现在呢，要你把棋盘的下半部分填满。要求相同数字必须相连，且数字$x$必须出现$x$次。

题解

参考下图可知，因为红色的部分已经用完了次数，所以在红色左边的蓝色都是直接拿上面一位的值，红色右边的绿色都是直接拿右边一位的值。

同理，第二次是2的次数用尽，同样的方法可以构建下一层。

代码

D. Explorer Space

就是一个非常普通的DP。没啥好说的

E. Group Photo

就是一个简单的二分，只是有很多情况要分类讨论。可能更多是个模拟题。