[ABC375C] Spiral Rotation

WuMin4 / 2024-10-23 / 原文

[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$ 如下：

对于第 $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; 
}