题解：P10509 停车场

Arthur_Douglas · 2024-05-25 22:37:20 · 题解

思路

先公布解： 当 n=2023 时， 暴推打表得出的未化简公式（肯定是赛后交的）：

为什么呢

证明如下！

一条道路中间会有两个车位在每个空地旁边。我们假定停车位数量 MAX 为每个空地都与旁边的两个停车位对应，所以换句话说车位每三个位置就有两个。

但是道路末的空地如果不在边界与三个停车位对应，那么是不是停车位的值可能会比自己原先设定的 MAX 大呢？

我们发现了道路有着一些规律：

如果全图不止一个以任意上左下右的顺序返回出入口的路径，则会发现图中有一个长相为 J 样的空地，因为可证明，每次遇见 J 型路的时候，便会有先左后右与先右后左的顺序，所以为路径增加了一条路径的情况。

若没有 J 型路，全图合法的路径中会产生有且只会有一个从出入口入，从出入口出的路径，而且此图中只会有一个图的道路末，这样是不影响答案产生的。

而我们发现， J 型路中的所有车位只会与其左或右的车位相邻，所以我们发现了，这一特性抵消了 J 型道路末增加车位的贡献，所以可以化简。那所谓的 J 型道路末只会在 J 型道路产生一个时产生有且只有一个。所以还是抵消了。

所以我们猜想，停车位只会是我们猜想的一样的数量。

（重复）也就是说每三个位置就有两个是车位。

所以理论上来讲，车位 MAX 为：\frac{2n^2}{3}。

来，交一发

然后 WA 唤醒了我们。

所以我们要继续寻找问题所在。

我们只是假定一条道路中间有两个停车位，实际上停车位是达不到我们理想的个数的。

因为要是一条所谓的道路没有岔路且没有变换方向，这条道路以及这条道路的相邻车位最多只能覆盖 3n 个格子，而连接两个道路必定会造成至少为 1 的车位浪费，那么要覆盖 n^2 个格子就至少多需要 \frac{n}{3} 个空地。

所以，我们发现停车位的数量就变成了 \frac{2n^2-n}{3}。

再交一发

我们发现，一段路会有空地及其停车位，那么我们不妨设想其是一个长或宽为 3 的矩形。然后在这张 n \times n 的图中拼接。

那么我们继续思考，任意两条路不可能会出现道路相交；如果相交，那么一个停车位就会和两个空地相邻，损耗了一个停车位，所以这是一个不算优的路径。便排除了此类情况。

那么，我们就离答案很近了。我们拿着这些矩形在其中进行拼接，发现无论怎么摆放此 n^2 的矩形在边长为 2023 时总会剩下至少一个空地。

之前所说的 J 型路的拐角处产生的空地要消去的话，需要的道路拼接，若如此做，会有更多的无用的车位冒出来，所以绝对不会考虑此类情况。况且之前我们说到了路末的空地，假如其占一个位置，如果不覆盖将至少把一个路分为两部分，收益变小，所以也绝对不考虑此类情况，

相邻的不同方向路块连接可以形成拐角及 J 型路，只会产生 1 的损耗。而相邻的同向的路连接能且只能从中间连通，会产生 2 个空地的损耗。所以不是最优的情况。

那么如此做，没有被路覆盖的空地应该刚好只有一个。如果有更多的未覆盖空地，那如果填上上一个路定比不填的情况要更优。可以证明：填上一个 3 \times 1 的路会产生 2 个车位且还有 1 个损耗空地，增加了 1 个车位。

这里彼此相邻的同向路依次连接可以移动边界处车位来做到成为 1 个损耗空地，可是我们不思考此类情况。因为我们可以让路变成不同方向。

所以综上，空地的数量就会增加 \frac{n}{3} 个，共 \frac{n^2}{3}+\frac{2n}{3} 个。不难证明，这定是真正的空地的最少个数。

所以得，停车场最少数量为 n^2-(\frac{n^2}{3}+\frac{2n}{3})=\frac{2n^2}{3}-\frac{2n}{3} 个。

证毕。

code

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n = 2023;
    cout << 2 * (n * n - n) / 3;
    return 0;
}

(记得点个赞哩)