Google Kickstart 2018 Round A题解

Kickstart,我又回来了,今年是校招年了,所以加油吧。

A. Even Digits

这道题蛮简单的,就是要求离$N$最近的都是数位上都是偶数的数,所以可以向上或者向下找。简单的说就是最高位++或者--,然后剩下来通通改成8或者0。不过我们需要额外考虑一下借位和进位的情况,对于向下来说,不存在,因为1下面是0,不需要借位。对于向上来说9上面是10,要进一位,但是我们注意到进的1是奇数,所以我们还要将它变成2,这无疑是比向下的方法去多了,所以我们不需要考虑9的进位。

AC代码

B. Lucky Dip

有物品$V_i$,假如最多有$K$次放回重抽的机会,问最后手上的物品期望最高是多少。首先由于是不放回的,所以每次的概率其实都是平均的。所以$K = 0$时就是平均数,下面我们思考最优策略是什么。其实很简单,我们枚举$i$,我们的策略就是在对$V_i$不满意的时候逆天改命。下面就是判断标准,是与平均数比吗,还是和中位数比呢?我们假设第$d$次的期望是$prev = dp[d]$,现在我们决定要不要抽第$d + 1$次,这取决于我们实际抽到的$V_i$是否高于期望$prev$。

AC代码