P10509 停车场 题解

P10509 停车场题目描述你有一片空地。这片空地可以视作一个一个 \(n\times n\) 的正方形。空地外一圈为墙壁你无法拆除它们。现在你要在这片空地上规划停车位使之成为一个停车场。你希望空地的左下角是停车场的出入口。出入口不能规划为停车位。空地和停车位都是 \(1\times 1\) 的正方形且正方形的每条边与墙壁平行或者垂直。每个停车位都应该与至少一个空地四连通即停车场的上、下、左、右方至少有一个空地且这个空地应当能通过若干次向上、下、左、右的移动在不经过任何停车位的情况下到达出入口。下图为 \(n4\) 时停车位数最多的放置方法之一其中红色为车位蓝色为出口白色为空地。请问 \(n2023\) 下最多能安排多少个停车位输入格式无输出格式一个正整数表示你的答案。题解题意找出在 \(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\) 就是结果\(n2023\) 时答案为 \(2727004\)。AC记录AC代码#includebits/stdc.h using namespace std; int main(){ long long n2023,sn,i; for(i2;in;i3){ s2*i; } coutn*n-s; return 0; }