【题解】Google Kick Start
老年人做点笔试题算了。
注:一切以 Hard 模式为准。
2019
Round F
Flattening
$f[i][k]$ 表示前 $i$ 个数中相邻不同的数量不超过 $k$ 的最少操作数,有转移式 $f[i][k] = \min_{j<i} f[j][k -1]+m(j+1,i)$,其中 $m(l, r)$ 表示把 $l$ 和 $r$ 之间的 $a[i]$ 变为相同需要的最小数,可以线性预处理。
还有一种思维复杂度和时间复杂度更高的做法,$f[i][k][last]$ 表示前 $i$ 个数相邻不同的数量小于 $k$ 且修改后 $a[i]$ 的值是 $last$ 的最小操作数,转移就有点复杂了。
官方题解中有一个观察,修改操作可以用删除替换,不过好像区别不大?官方题解中还提供了一种复杂度更低的做法,二分答案,然而我并不知道怎么判是否可行(我看了差不多十份代码也没找到用二分的)。
1 |
|
Teach Me
考虑问题的反面,有多少对不能 mentor。对于一个人 x,y 不能 mentor 他的充要条件是 y 是 x 的子集。然后枚举子集,哈希后用 map 统计一下就好了。
1 |
|
Round G
https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050e02
Book Reading
考虑被撕掉的每一页,当询问是页数的因数时会减少对答案的贡献。预处理每个数的因数,统计一下就好了。
1 |
|
The Equation
从高到低枚举答案二进制的每一位,如果枚举到的这一位能是 1,那么就放 1,否则只能放 0。判断某一位是不是能放 1,只要让剩下的那些没确定的位放最优(也就是能让异或和结果尽可能小的),再判断是否满足条件即可。
注意数据范围,不要在运算过程中爆 long long。
1 |
|
Shifts
$O(3^{20})$ 显然不怎么行,考虑两边相遇。分别处理 $O(3^{10})$,把每种组合看成坐标的一个点,对于左边的每一个点,需要知道在右边的某个矩形里的点的个数。做法就是按照一维排序,另一维用数据结构维护,代码中用了 pb_ds 里的平衡树,离散化用树状数组或者用 cdq 分治也行。
1 |
|