专栏文章

题解：P12242 [蓝桥杯 2023 国研究生组] 钉板上的正方形

wweifengzhaomi
P12242题解参与者 3已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@mipjw8h0
此快照首次捕获于
2025/12/03 13:12
3 个月前
此快照最后确认于
2025/12/03 13:12
3 个月前
查看原文
写蓝题绿题题解没过，愤恨恨来写黄题题解我没不信过不了了。
前记：本人在一开始算的时候没考虑到部分方块，截止目前，有三分之一是我提交的了。

题意：

本题给了我们一个钉板，要我们算出一共有多少个大小不一的正方形。
为了方便处理，我们可以把钉板存入数组中。
为了方便，我们设 n=10n = 10，也就是顶板的大小。
CPP
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×1010 \times 10 的大小。
于是我们可以手算，然后提交答案。
时间复杂度 O(1)O(1)。

思路 2.0：

什么？要手算？我从来不手算。
但是手算有点麻烦，我们可以用编程来计算。
枚举每个顶点，然后判断 4 个角是不是都有钉子。
然后统计答案。
时间复杂度 O(n4)O(n ^ 4)。

思路 3.0：

然而枚举四个角不但浪费了很多时间，还有很多本身就不是一个正方形的，这个时候要怎么办？
我们可以换一种思路，枚举正方形的每条边，然后枚举当前的位置，判断四个角有没有顶点，有的话更新一下答案。
时间复杂度 O(n3)O(n ^ 3)。
最终在各种思路的推算下，得出答案为 2121。
虽然这道题思路 1 和 2 就可以过了，但是我们还是进行了优化，尽管没有任何意义，但是也可以提升一下思维，说不定在以后就有的能用得上呢。

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...