Google Kickstart 2017 Round G题解

Google Kickstart 2017 Round G,当时参加了Google招聘的云中讲堂,建议我们刷一刷Round G。然后就被虐了,只过了A和BC的小数据,55分Rk338滚粗。今天重新做了下,发现其实并不是很难,关键还是手速和脑子要快。

A. Huge Numbers

首先快速幂算阶乘的时候用了< n,完美地WA了两发,快速幂过了小数据,用祖传的公式过了大数据。
$$
A^x = A^{x mod \phi(c) + \phi(c)} (mod c) \\
x \ge \phi(c)
$$
后来看题解发现可以将$A^{N!}$展开成
$$
A^{1^{2^{3…}}}
$$
的形式,然后递归地来做。
AC代码

B. Cards Game

有N个卡片,正反各有一个正整数。玩家初始分数0分,每次选两张卡片,分别将其中一张的正面和另一张的反面异或,并将结果加到总分上。结束后将一张卡片丢弃,另一张放回,由此重复一直到只有一张卡片。求最终最小的分数。
没有经受住过小数据的诱惑,直接爆搜了下,复杂度$O(2^N * N^2)$。
查看题解,题解使用图论的观点来看,由于每次操作都有一张卡片被消去,我们假设卡片$i$被$j$消去,可以看做从$i$到$j$存在一条边。
于是恍然大悟,这条就是个最小生成树啊,套个模板就出来了。注意大数据需要用LL。
AC代码

C. Matrix Cutting

有一个N*M的矩阵,现在按照行或列切分矩阵,每次讲一个大矩阵切分为两个小矩阵,就奖励原矩阵中的最小值对应的分数。整个过程一直以得到N*M个1*1的矩阵为止,求可能得到的最多分数。
这条小数据只有一行哎,于是暴搜(都可以不加记忆化)过了小数据。
大数据看起来有可以用二维线段树做,不过由于本人还是太弱,所以最后没时间做了。后来发现可以直接套用二维记忆化搜索强行莽掉。
AC代码
在实际跑的时候,常数太大了,我用VS开Release才能在6分钟左右算完。我打算写一个CodejamSolver来多线程跑,然后再join。