Google Kickstart 2017 Round C题解

C轮感觉比校招笔试轮次的DE要简单点了,这次有四道题都很有意思。

A. Ambiguous Cipher

题目就是要解一个模意义下的线性方程。由于加减乘对模运算是封闭的,所以可以直接解。注意解下来的结果还要模一下26。
用numpy搞了一波,特判下奇异矩阵,对应无穷多解的情况。
AC代码

B. X Squared

一开始找规律觉得只要除了允许其中一行和一列拥有一个叉,其他的每个行列必须有且只有两个叉。结果果断WA了,对拍下看看

5
.X..X
...XX
XX...
..X..
X..X.

上面的这个样例输出POSSIBLE,但实际上却是IMPOSSIBLE的,看来我的条件只是必要条件。还能加上啥条件呢?初等变换得到的矩阵都是等价的,不过看来这性质用不上。
然后发现之前的性质挖掘不彻底,事实上矩阵在任意行列互换后位于同行/列的元素依然位于同行/列,于是矩阵中一定存在两行中的两个X的距离是相等的。果断又WA了,后来发现不仅距离要相等,而且是要平行的。
AC代码

C. Magical Thinking

小数据$N=1$,感觉是送分啊。直接看大数据,$N \le 2$。想了一会儿方程,发现是DP。
其实思路很简单,$dp[i][r1][r2]$表示到第$i$个题目前同学1对了$r1$条且同学2对了$r2$条时自己可能获得的最多分数。根据$N$取值可以分别分4、2种。而得分$s[0..1]$的作用就是当$r1 \ge s[0]$时他这条就不能再对了。
但是代码在小数据上都卡了很久。最后发现原因是出现了dp[2][6]这样的值,为什么进行到2的时候能对6个呢?将里面r1的循环改成了r1 <= min(s[0], i),就AC了。
AC代码

D. The 4M Corporation