不知道从哪里翻出了这个题解,只翻到了Round C,那就放出来吧;大概是2017年夏天写的。
代码/测试数据可以在这个GitHub仓库中的google-apac子目录中找到。
Round C
A Monster Path
简单的DFS即可通过。
输入数据中的地图中字符使用空格隔开需要注意一下。
时间复杂度$O(4^S), S \leq 9$。
B Safe Squares
一个简单的DP,印象中Leetcode里这道题的难度是Medium。
,那么转移就很简单了。
最终答案是$\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)$。