洛谷P2239题解

洛谷P2239题解

题目信息：

题目传送门：https://www.luogu.com.cn/problem/P2239

题目知识点：模拟，数学

题目简述：

一个边长为n的矩阵，要螺旋形填充数字v，v从1开始每次递增，需要计算出(i,j)的v值

数据规模：1<=n<=300000,v<=9*10^10，v要开long long

分析1

第一个思路是绘图，从起点开始运动，每次运动到越界或者有赋过值的点就改变方向，这样的好处是不用考虑点具体的运动规律，但是很不幸maxn高达30000，如果真的用了这个方法只能和蒟蒻一样喜提MLE

参考代码

---

#include<cstdio>
const int maxn = 30005;
const int dx[4] = { 0,1,0,-1 };
const int dy[4] = { 1,0,-1,0 };

int buf[maxn][maxn];
int n, i, j, flag;

int main() {
	scanf("%d%d%d", &n, &i, &j);
	int v = 1;
	int x = 1, y = 1;
	for (int i = 1; i <= n * n; i++) {
		buf[x][y] = v++;

		x += dx[flag];
		y += dy[flag];
		if (x<1 || x>n || y<1 || y>n || buf[x][y]) {
			x -= dx[flag];
			y -= dy[flag];
			flag = (flag + 1) % 4;
			x += dx[flag];
			y += dy[flag];
		}
	}
	printf("%d\n", buf[i][j]);
	return 0;
}

分析2

想要找到i,j位置没有必要开一个表，分析运动路径即可
以n == 4为例子运动的长度为3 3 3 2 2 1 1，归纳发现除了第一次剩下的每有两次运动长度-1，而每次运动到头改变方向，由此可以写出代码

代码

#include<cstdio>
#define ll long long
int n, r ,c;
const int dx[4] = { 0,1,0,-1 };
const int dy[4] = { 1,0,-1,0 };
int x = 1, y = 1, dire;
ll v = 1;

int main() {
	scanf("%d%d%d", &n, &r, &c);

	for (int i = 1; i < n; i++) {
		x += dx[dire];
		y += dy[dire];
		v++;
		if (x == r && y == c) {
			printf("%d\n", v);
			return 0;
		}
	}
	dire = 1;
	int t = n-1,cnt = 0,round=0;
	while (x!=r||y!=c) {
		x += dx[dire];
		y += dy[dire];
		cnt++; v++;
		if (cnt == t) {
			dire = (dire + 1) % 4;
			round++;
			if (round % 2 == 0)t--;
			cnt = 0;
		}
	}
	printf("%lld\n", v);
	return 0;
}

最后