P2239螺旋矩阵

传送

看到这数据范围，显然咱不能暴力直接模拟（二维数组开不下，而且会T掉）

我们目前有两种选择：

1.优化暴力走这边（jyy tql%%%）

2.数学做法

我们看一下题目中的那个矩阵

我们能不能找到些什么规律

由肉眼观察得

(1,1)=1

(n,n)=2*n-1

(1,n)=3*n-2

(2,1)=4*n-4

好像似乎有那么点规律

所以我们不妨把当前的矩阵分成4部分

i=1,ans=j

j=n,ans=2*n-1-（n-i）=n-1+i（这里可以理解为从(n,n)向上的(n-i)行的数）

i=n,ans=3*n+(j-1)=3*n-1-j（由(1,n)向右找(j-1)列）

j=1,ans=4*n-4-(i-2)=4*n-2+i（由(2,1)向下找（i-2）行）

如果给的i,j不在这些特殊位置呢？

那我们就把当前的矩阵扒掉最外边的皮，此时n-2,i-1, j-1，再看当前的i,j是否在新的矩阵的特殊位置，不在就继续扒，最后肯定会找到的。因为我们扒掉了矩阵的最外边，所以每扒一层，答案要加上4*(n-1)（n为当前的n）

这样我们就可以递归求解了

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

int n,a,b;

int solve(int n,int i,int j)

{

    if(i==)return j;

    if(j==n)return n-+i;

    if(i==n)return *n--j;

    if(j==)return *(n-)-(i-);//懒得化简了qwq

    return solve(n-,i-,j-)+(*n-);

}

int main()

{

    scanf("%d%d%d",&n,&a,&b);

    printf("%d",solve(n,a,b));

}

巴特西

P2239螺旋矩阵

最新文章

热门文章