Educational Codeforces Round 109 ABCDE 题解

A. Potion-making

题意

每次你可以导入一升材料,材料分为纯水和魔法精华。现在要调出魔法精华占比恰好为k%的药水。问你最小要多少升。

题解

其实就是$\frac k {100}$的分式化简。化简后的分母就是答案。

代码

C++

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

Java

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

B. Permutation Sort

题意

给你一个1-n的序列a。现在一次操作中你可以选择任意一段,并把这一段改成任意顺序。但是这一段不能是全部。问你要把1-n的序列调成从小到大最少要多少步。

题解

首先,如果本身就是有序的,那么直接输出0。

如果首位已经是1或者末位已经是n,则一步就能搞定。

但如果首位是n且末位是1,则需要3步。第一步把1或者n换到中间,第二步恢复首位或者末位,第三步把其他位置排序。

否则,可以跳过上面的第一步,只需两步即可。

代码

Java

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

C++

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

C. Robot Collisions

这个题的本质是从右往左,依次尝试往右找机器人匹配。如果不行就转化为一开始就往左的机器人来和后面的机器人匹配即可。

Educational Codeforces Round 109 Robot Collisions 题解(Java/C++)
题意有n个机器人分布于0到m之间。这些机器人从他们初始位置开始可能往左走也可能往右走。碰壁之后自动回头。如果某一个整秒,两个机器人处于同一个位置,则这两个机器人爆炸。问这些机器人的爆炸时间。
点击查看具体题解

D. Armchairs

想不到贪心的做法。还是直接dp简单些。就是维护第i个1做到第j个0时,最小的开销即可。

Educational Codeforces Round 109 Armchairs 题解(Java/C++)
题意有n个板凳,有不超过$\frac{n}{2}$个人已经坐在上面,现在每次你可以让任意一个人坐到另外一个空位上,开销是两个空位的下标的差。问你,把这些人挪了之后,所有之前坐了人的空位都不坐人的最小开销。
点击查看具体题解

E. Assimilation IV

就是一个逆向思维加上基础数论的简单题。

Educational Codeforces Round 109 Assimilation IV 题解(Java/C++)
题意你有n个城市。每回合你要选一个城市来修纪念碑。一开始纪念碑的辐射范围是1,此后每回合辐射范围加一。总共修n个纪念碑。现在有m个点,给你每个点到每个城市的距离。对于每一种修法的排列,分数就是至少被一个城市的纪念碑辐射到的。问所有排列的分数总和。