自动搬运

查看原文

来自洛谷，原作者为

	weifengzhaomi 加油，不要辜负对朱前泰说的话

搬运于2025-08-24 23:13:57，当前版本为作者最后更新于2025-04-20 11:22:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

写蓝题绿题题解没过，愤恨恨来写黄题题解我没不信过不了了。

前记：本人在一开始算的时候没考虑到部分方块，截止目前，有三分之一是我提交的了。

题意：

本题给了我们一个钉板，要我们算出一共有多少个大小不一的正方形。

为了方便处理，我们可以把钉板存入数组中。

为了方便，我们设 $n = 10$，也就是顶板的大小。

const int s[10][10] = {
	{1,1,0,1,0,1,1,1,1,1},
	{1,1,1,0,0,1,1,1,1,0},
	{1,1,0,0,1,0,1,1,1,1},
	{1,0,1,1,0,1,1,1,1,0},
	{1,0,1,0,1,1,1,1,0,0},
	{1,0,0,1,0,1,0,1,0,1},
	{1,1,1,1,1,1,1,1,1,0},
	{0,1,1,1,1,1,1,1,1,0},
	{0,1,1,0,1,0,1,1,1,1},
	{1,0,1,0,0,1,0,1,0,0}
	// 1就是有钉子，0就是没有
};

思路：

思路 1.0：

可以发现，这个钉板只有 $10 \times 10$ 的大小。

于是我们可以手算，然后提交答案。

时间复杂度 $O(1)$。

思路 2.0：

什么？要手算？我从来不手算。

但是手算有点麻烦，我们可以用编程来计算。

枚举每个顶点，然后判断 4 个角是不是都有钉子。

然后统计答案。

时间复杂度 $O(n ^ 4)$。

思路 3.0：

然而枚举四个角不但浪费了很多时间，还有很多本身就不是一个正方形的，这个时候要怎么办？

我们可以换一种思路，枚举正方形的每条边，然后枚举当前的位置，判断四个角有没有顶点，有的话更新一下答案。

时间复杂度 $O(n ^ 3)$。

最终在各种思路的推算下，得出答案为 $21$。

虽然这道题思路 1 和 2 就可以过了，但是我们还是进行了优化，尽管没有任何意义，但是也可以提升一下思维，说不定在以后就有的能用得上呢。