微软2017年预科生笔试第二场

微软2017年预科生笔试第二场的题目比9月份的校招要难一点。

hiho1497 Queen Attack

为了不MLE,需要按点判断,二分即可
代码

hiho1498 Diligent Robots

这道题目思路也不复杂,首先机器人肯定是越早造越好,因此早期我们投入全部能力造机器人。假设机器人数量为$R$(包括一开始的一个),需要时间

$$
T = T_{build} + T_{work} \\
T_{build} = q \, \lceil log_{2}R \rceil \\
R_{idle} = 2^{\lceil log_{2}R \rceil} - R \\
T_{work} = \frac{n-q \, R_{idle}}{R}
$$
下面就可以枚举$R$,注意由于任务数取值$n$可能到1000000000000,因此单纯的枚举会超时。但事实上可以证明$R$可以只取2的整数幂,即最后一轮的复制也不存在让一群机器人去复制,另一部分去工作的,假设第$X$轮复制时已有$R$个机器人和$n$个任务,如果让所有的机器人参与复制则到全部完成工作耗时
$$
T_{all} = \lceil \frac{n}{2 \, R} \rceil + q
$$
让$S$个机器人参加工作
$$
T_{R - S} = \lceil \frac{n - S \, q}{2 \, R - S} \rceil + q
$$
特别地,让所有机器人参加工作(此情况等于最后一轮为$X-1$的情况,可以不考虑)
$$
T_{none} = \lceil \frac{n}{R} \rceil
$$
通过解不等式,可以发现不管怎么样全复制都是好的。
这里说明一下若$\lceil a \rceil > \lceil b \rceil$,那么$a > b$。由定义$[a] + 1 > [b] + 1$,则$[a] \ge [b] + 1 \gt [b] + (\lbrace b \rbrace - \lbrace a \rbrace)$,即$a > b$。
代码

hiho1499 A Box of Coins