Educational Codeforces Round 109 ABCDE 题解

A. Potion-making

题意

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

题解

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

代码

C++

Java

B. Permutation Sort

题意

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

题解

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

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

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

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

代码

Java

C++

C. Robot Collisions

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

D. Armchairs

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

E. Assimilation IV

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