P2239 [NOIP2014 普及组] 螺旋矩阵讲解

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-05-15 14:39:52

转载：https://www.luogu.com.cn/article/ur0hlq2a

题目数学题。

$50$ 分做法：

先暴力做出这个 $n\times n$ 的矩阵，最后直接输出。时间复杂度为 $O(n^2)$，$n\in[1,30000]$，超时，考虑优化。

$O(n)$ 做法：

我们找出了所有的 $a_{i,j}$，但只输出了一个，浪费了大量时间。参考以下蛇形方阵： $$\begin{bmatrix}1&2&3&4&5\&17&18&19&6\ &24&25&20&7\&23&22&21&8\&12&11&10&9\end{bmatrix}$$ 直接推式子有些难推，我们分类讨论：

$i=1,j\in(1,n):a_{i,j}=j$
$i\in(1,n),j=n:a_{i,j}=n+i-1$
$i=n,j\in(1,n):a_{i,j}=3n-j-1$
$i\in(1,n),j=1:a_{i,j}=4n-i-2$

不是以上情况怎么办呢？我们给矩阵缩小一下： $$\begin{bmatrix}1&2&3\\8&9&4\&6&5\end{bmatrix}$$ 可以看到，中间的九个元素都减少了 $16$，也就是 $4(n-1)$。那么设这个函数为 $f(n,i,j)$，最后一种情况为：

$i\in(1,n),j\in(1,n):f(n-2,i-1,j-1)+4(n-1)$ 总体复杂度为 $O(n)$，可以通过。代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define INF 0x2a2a2a2a
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define rer(i,x,y,cmp) for(int i=x;i<=y&&cmp;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int n,i,j;
inl int find(int n,int i,int j){
	if(i==1) return j;
	if(j==n) return n+i-1;
	if(i==n) return (n<<1)+n-j-1;
	if(j==1) return (n<<2)-i-2;
	return find(n-2,i-1,j-1)+((n-1)<<2);
}
signed main(){
	FAST;
	cin>>n>>i>>j;
	cout<<find(n,i,j);
	return 0;
}

$O(1)$ 做法：

虽说已经可以通过此题，但如果 $n$ 的规模再大一些，达到 $n\in[1,10^9]$，那就必须 $O(1)$ 解决了。我们找一个更大的矩阵： $$\begin{bmatrix}1&2&3&4&5&6&7&8\8&29&30&31&32&33&34&9\&48&49&50&51&52&35&10\&47&60&61&62&53&36&11\&46&59&64&63&54&37&12\&45&58&57&56&55&38&13\&44&43&42&41&40&39&14\&21&20&19&18&17&16&15\end{bmatrix}$$ 一轮缩小，减少了 $4\times(8-1)=28$。二轮缩小，减少了 $4\times(6-1)=20$。三轮缩小，减少了 $4\times(4-1)=12$。 $b=\{28,20,12\}$，翻转一下变成 $b'=\{12,20,28\}$，可以看出这是一个等差数列。很明显会缩小 $x=min(i,j,n-i+1,n-j+1)$ 次。 $b'$ 的末项是 $4(n-1)$，公差是 $8$，首项就是 $4(n-1)-8(x-2)$，得 $b_{sum}$： $$b_{sum}=\frac{(4(n-1)-8(x-2)+4(n-1))\times(x-1)}{2}$$ 总体复杂度为 $O(1)$。代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define INF 0x2a2a2a2a
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define rer(i,x,y,cmp) for(int i=x;i<=y&&cmp;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int n,i,j,x,y;
signed main(){
	FAST;
	cin>>n>>i>>j;
	x=min(min(i,n-i+1),min(j,n-j+1));
	y=((((n-((x-2)<<1)-1)<<2)+((n-1)<<2))*(x-1))>>1;
	i-=x-1;
	j-=x-1;
	n-=((x-1)<<1);
	if(i==1) cout<<y+j;
	else if(n-j+1==1) cout<<y+n+i-1;
	else if(n-i+1==1) cout<<y+(n<<1)+n-j-1;
	else cout<<y+(n<<2)-i-2;
	return 0;
}

lxn 的博客

博客