P8668题解

szh_AK_all · 2023-07-21 17:43:43 · 题解

题目传送门

这道题可以用暴力枚举来做，但很容易超时，本人认为没必要用枚举法，因为只需要判断语句就够了。下面先看一幅图。

其实做这道题就跟找规律一样，我们把图片分为 4 个部分，便产生出了两种做法。

一、根据 4 个象限将图片分为 4 部分，依次考虑 4 个象限的情况；二、根据每条线的走向及位置，按照每个点所在的线划分，分为：横轴上方，横轴下方，纵轴右方，纵轴左方四种线段，再依次考虑。

下面讲述第二种做法。

首先，考虑横轴正上方的线段。我们先看 (1,1) 这个点（根据左上角的位置找规律），需要 4 步。再看 (2,2) 这个点，需要 16 步。到这里，我们似乎发现了什么，接着看 (3,3)，发现，每条处在横轴正上方的线段的最右边的点需要的步数，都可以表达为 x\times 2\times x\times 2 步，那么处在它旁边的点就好办了。规律在代码中呈现。

其次，考虑其他三种线段，规律还是挺好找的。下面直接给出代码。

Code

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    long long x,y,k;
    long long o=0;
    cin>>x>>y;
    if(y>=(-x)&&y<=x)//纵轴右方
    {
        k=x*2*x*2+(x-y);
    }
    else if(y<=(-x)&&y>x)//纵轴左方
    {
        long long x2=x;
        x=-x;
        k=(x*2-1)*(x*2-1)+(y-x2-1);
    }
    else if(y>=0)//横轴上方
    {
        k=2*y*2*y-(y-x);
    }
    else if(y<0)//横轴下方
    { 
        long long io=-y*2;
        k=(io*(io+1))+(-y-x+1);
    }
    cout<<k;
}

另外，还有一个重要的点，就是判断点的位置。规律可以根据代码理解。