Google Kick Start 2021 Round A 题解

[utterances-bot]

Google Kick Start 2021 Round A 题解 | CP Wiki

接下来枚举L型的中心点。确定中心点之后，需要考虑四个朝向：

https://cp-wiki.vercel.app/tutorial/kick-start/2021A/

[codelh7]

有两个问题想请教一下：

1. 第三题：“显然最高的格子不需要再加高了”。 这个可以稍微证明一下嘛？虽然好像直观上是这样的。
   2.第四题：这样的构图方式好妙啊。。。咋想到的呀？有类似的题吗？

[lucifer1004]

@codelh7

1. 最高的格子显然不会因为周围的格子比它高而需要加高；同理，排除最高的格子后，第二高的格子也不会因为周围的格子比它高而需要加高，也就是说，第二高的格子最多需要加到最高的格子那么高；依此类推。那么在最小化代价的要求下，自然是不需要加高的。这个应该是不证自明的。

2. 把棋盘的行和列当成节点来建图还算是个比较常见的建图模式。比较近的题目有ARC112D - Skate。

[mike-box]

第四题好难啊，看了半天都没有一点思路。

[zxzyy10]

你好想请教一下第四题是否有prim算法的做法实现，自己想了一下发现初始化都没法做。