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

wflengxuenong · 2025-05-15 14:39:52 · 个人记录

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

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

题目 数学题。

50 分做法：

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

O(n) 做法：

我们找出了所有的 a_{i,j}，但只输出了一个，浪费了大量时间。 参考以下蛇形方阵：

直接推式子有些难推，我们分类讨论：

• 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

不是以上情况怎么办呢？ 我们给矩阵缩小一下：

可以看到，中间的九个元素都减少了 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\\28&29&30&31&32&33&34&9\\27&48&49&50&51&52&35&10\\26&47&60&61&62&53&36&11\\25&46&59&64&63&54&37&12\\24&45&58&57&56&55&38&13\\23&44&43&42&41&40&39&14\\22&21&20&19&18&17&16&15\end{bmatrix}

  一轮缩小，减少了 4\times(8-1)=28。 二轮缩小，减少了 4\times(6-1)=20。 三轮缩小，减少了 4\times(4-1)=12。

  很明显会缩小 $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)$。 代码： ```cpp #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; } ```