P10509 停车场 题解

P10509 停车场

题目描述

你有一片空地。这片空地可以视作一个一个 \(n\times n\) 的正方形。空地外一圈为墙壁，你无法拆除它们。

现在你要在这片空地上规划停车位，使之成为一个停车场。你希望空地的左下角是停车场的出入口。出入口不能规划为停车位。空地和停车位都是 \(1\times 1\) 的正方形，且正方形的每条边与墙壁平行或者垂直。

每个停车位都应该与至少一个空地四连通（即：停车场的上、下、左、右方至少有一个空地），且这个空地应当能通过若干次向上、下、左、右的移动，在不经过任何停车位的情况下到达出入口。

下图为 \(n=4\) 时停车位数最多的放置方法之一，其中红色为车位，蓝色为出口，白色为空地。

请问 \(n=2023\) 下最多能安排多少个停车位？

输入格式

无

输出格式

一个正整数，表示你的答案。

题解

题意

找出在 \(2023\times 2023\) 的正方形中 \(1\times 1\) 的停车位数最大值（停车位的上、下、左、右至少有一个空地）

思路

多画几个图，就会发现可以用一种通用的方法：（这里以 \(10\times 10\) 举例）

用zorr.pro画图真好用
（灰的是车位，黑的是空地或出入口）
再把黑的位置改一下就会变成这样：

发现了吗？如果把它分解成条状，两两分组，就会变成长度为 \(2、5、8\)，宽度为 \(2\) 的方块和一段长度为 \(n\)，宽度为 \(1\) 的长条，而 \(2、5、8\) 是公差为 \(3\)，首项为 \(2\) 的等差数列
∴答案已经呼之欲出了！公差为 \(3\)，首项为 \(2\)，末项为 \(n\) (或 \(n-1\) 或 \(n-2\))的等差数列的各项和加上 \(n\) 就是结果！！！
\(n=2023\) 时答案为 \(2727004\)。

AC记录

AC代码：

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