[ABC375C] Spiral Rotation
题意
给出一个边长为偶数 \(n\) 的只由 # 和 . 组成的矩阵。
你需要按顺序对于 \(i=1,2,\cdots,\frac{n}{2}\) 将满足 \(i\le x,y\le n+1-i\) 的单元格 \((y,n+1−x)\) 替换成单元格 \((x,y)\) 的字符，问操作完后的矩阵。
\(2\le n\le 3000\)。
思路
C题最恶心的一集。
如果你对着题意直接模拟的话复杂度为 \(O(n^3)\)，显然不能通过，但你一直对着题目看就会发现你也看不出什么，最起码我是看不出来。
于是通过对暴力程序的亿点点找规律可以发现题意可以转换成：
将正方形矩阵分成 \(\frac{n}{2}\) 圈，例如 \(n=8\) 如下：
11111111
12222221
12333321
12344321
12344321
12333321
12222221
11111111
对于第 \(i\) 圈，将它顺时针旋转 \(i\times 90°\)，问操作完后的矩阵。
转换完后思路就很清楚了，对于第 \((i,j)\) 个单元格可以通过 \(\min\{i,n-i+1,j,n-j+1\}\) 算出在第几个圈，然后直接模拟旋转即可。
代码
#include <bits/stdc++.h>
using namespace std;
int n;
char s[3005][3005],s2[3005][3005];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>s[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
//转360°可以视为转0°
if(min(min(i,n-i+1),min(j,n-j+1))%4==1)
s2[j][n-i+1]=s[i][j];
else if(min(min(i,n-i+1),min(j,n-j+1))%4==2)
s2[n-i+1][n-j+1]=s[i][j];
else if(min(min(i,n-i+1),min(j,n-j+1))%4==3)
s2[n-j+1][i]=s[i][j];
else
s2[i][j]=s[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<s2[i][j];
}
cout<<endl;
}
return 0;
}