Codeforces Round #718 ABCDE 题解

A. Sum of 2050

题意

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

题解

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

代码

Submission #114043964 - Codeforces
Codeforces. Programming competitions and contests, programming community

B. Morning Jogging

题意

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

题解

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

代码

Submission #114044015 - Codeforces
Codeforces. Programming competitions and contests, programming community

实现思路

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


C. Fillomino 2

题意

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

题解

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

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

代码

Submission #114044045 - Codeforces
Codeforces. Programming competitions and contests, programming community

D. Explorer Space

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

Codeforces Round #718 Explorer Space - DP
题意有一个n×m的棋盘。相邻两个各自都有边,每条边都有一个长度。 现在问你,从任意点(i,j)出发,走k步后回到(i,j)所经过的最小长度是多少。过程中可以多次路过(i,j)。

E. Group Photo

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

Codeforces Round #718 Group Photo - 二分
题意n个人拍照,要把这些人分成两部分,一部分人拿C的牌子,一部分人拿P的牌子。现在要求拿C的人的下标满足
展示评论