search

lucifer1004 / cp-wiki

lucifer1004 的 CP 笔记
https://cp-wiki.vercel.app
130 stars 15 forks source link

Google Kick Start 2021 Round A 题解 #30

Open utterances-bot opened 3 years ago

utterances-bot commented 3 years ago

Google Kick Start 2021 Round A 题解 | CP Wiki

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

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

codelh7 commented 3 years ago

有两个问题想请教一下：

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

@codelh7

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

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

mike-box commented 3 years ago

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

zxzyy10 commented 3 years ago

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