Hobo Chen

Google APAC 2017 C 题解

不知道从哪里翻出了这个题解,只翻到了Round C,那就放出来吧;大概是2017年夏天写的。

代码/测试数据可以在这个GitHub仓库中的google-apac子目录中找到。

Round C

A Monster Path

简单的DFS即可通过。

输入数据中的地图中字符使用空格隔开需要注意一下。

时间复杂度$O(4^S), S \leq 9$。

B Safe Squares

一个简单的DP,印象中Leetcode里这道题的难度是Medium。

$$ dp[i][j] = 以[i, j]为右下角的正方形数目$$,那么转移就很简单了。

最终答案是$\sum_{i, j}dp[i][j]$。

最终答案需要long long来保存。

时间复杂度$O(RC),R\leq3000,C\leq3000$。

C Evaluation

有向图判断是否连同以及有环。

注意,当某个变量只作为参数出现是不合法的(无法计算出),所以需要判断是否连通。

我的代码中判环使用拓扑排序

时间复杂度$O(n)$。

D Soldiers

一个博弈。

局面分为两种:

  • 存在一个士兵同时有最大攻击和最大防御,Alice胜
  • 不存在局面一的条件,那么分别删除最大攻击和最大防御的士兵们;答案即这个子问题的解

如果某次删除了所有的士兵,Bob胜。

上面的做法时间复杂度$O(n^2)$,但可以做到$O(n\log n)$。