题解：P10509 停车场

· · 题解

题解：P10509 停车场

这篇题解主要是证明结论。

证明

首先，通过分析题目，可以提炼出以下几个要求：

那么，为了达到第一点要求，容易想到我们需要尽量使每个停车位周边只存在一个车位，又因为第三点要求，所以要尽可能使空地相连通，那么就会有一种方式是如下的：

\text{车位 空地 车位}

接着，我们可以发现 2022 是 3 的整数倍，因此前几行都可以铺满，并且最后一行剩下的块数也是 2022，也可以三三相间的摆放，已知我们一共有 n^2-1 个格子，所以我们的初步摆放就摆放了 \dfrac{2\times(n^2-1)}{3} 个车位。

这时我们满足了数量最多的要求，现在我们需要通过部分修改使得其满足联通的要求，可以发现我们上面构造出来的这个三三一组的块一共有 \dfrac{2\times(n-1)}{3} 个，并且两两之间是不连通的，因此我们需要将两两之间打通一下，就又要再减少 \dfrac{2\times(n-1)}{3}-1 个车位，最后，与出口最接近的那个车位也需要改掉，否则将一定无法联通。

总结一下，最后的答案就是