文章P10509 停车场 题解分享给大家，欢迎收藏极客资料网，专注分享技术知识

题目链接

P10509 停车场

题目描述

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

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

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

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

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

输入格式

无

输出格式

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

题解

题意

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

思路

多画几个图，就会发现可以用一种通用的方法：（这里以 \(10\times 10\) 举例）
（白的是车位，黑的是空地或出入口）
再把黑的位置改一下就会变成这样：
发现了吗？如果把它分解成条状，两两分组，就会变成长度为 \(2、5、8\)，宽度为 \(2\) 的方块和一段长度为 \(n\)，宽度为 \(1\) 的长条，而 \(2、5、8\) 是公差为 \(3\)，首项为 \(2\) 的等差数列
∴ 答案已经呼之欲出了！公差为 \(3\)，首项为 \(2\)，末项为 \(n\) 的等差数列的各项和加上 \(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;
}

文章来源:https://www.cnblogs.com/huan9178/p/21013962
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！