蓝桥杯刷题|04普及-真题

[蓝桥杯 2018 省 B] 螺旋折线

题目描述

如图所示的螺旋折线经过平面上所有整点恰好一次。

对于整点 (X,Y)，我们定义它到原点的距离 dis(X,Y) 是从原点到(X,Y) 的螺旋折线段的长度。

例如 dis(0,1)=3，dis(−2,−1)=9。

给出整点坐标 (X,Y)，你能计算出 dis(X,Y) 吗？

输入格式

X 和 Y。

输出格式

输出dis(X,Y)

输入输出样例

输入 #1  0 1

输出 #1  3

说明/提示

对于 40%的数据，−−1000≤X,Y≤1000。

对于 70% 的数据，− ≤X,Y≤ 。

对于 100% 的数据，− ≤X,Y≤ 。

思路

对于这个题，我把图中所有的点都列了出来然后发现规律

（0，0）        0

对于绝对值最大是1的

（-1，0）       1

（-1，1）       2

（0，1）        3

（1，1）        4

（1，0）        5

（1，-1）       6

（0，-1）       7

（-1，-1）      8

对于绝对值最大是2的

（-2，-1)        9

（-2，0)        10

（-2，1)        11

（-2，2)        12

       

 (-1，2）        13

 (0，2）        14

 (1，2）        15

 (2，2）        16

（2，1）        17

（2，0）        18

（2，-1）        19

（2，-2）        20

（1，-2）        21

（0，-2）        22

（-1，-2）        23

（-2，-2）        24

对于绝对值最大是3的

（-3，-2）        25

（-3，-1）        26

（-3，0）        27

（-3，1）        28

（-3，2）        29

（-3，3）        30

（-3，3）        31        

（-2，3）        32

（-1，3）        33

（0，3）        34

（1，3）        35

（2，3）        36

       

（3，2)           37

（3，1)           38

（3，0)            39

（3，-1)           40

（3，-2)           41

（3，-3)          42

       

（2，-3)          43

（1，-3)          44

（0，-3）        45

（-1，-3）        46

（-2，-3）        47

（-3，-3）        48

假设最大的绝对值为n,可以发现每一种距离的范围都是 到 (不包括 ）因此可以根据n来缩小计算的范围

代码1

#include<iostream>
#include<cmath>//包含求绝对的函数 
using namespace std;
int main()
{
  long long int x,y,num=0,a;
  cin>>x>>y;
  long long int n=(abs(x)>abs(y))?abs(x):abs(y);
  long long int X=(-1)*n,Y=(-1)*(n-1);//第一个坐标
  for(long long int i=(2*n-1)*(2*n-1)+1;i<(2*n+1)*(2*n+1);i++)
  {
    if(X == ( - 1 ) * n && Y > (-1)*n && Y < n ) Y ++;
    
    else if ( X < n && X >= ( - 1 ) * n && Y == n)X++;
    
    else if(X == n && Y <= n && Y > ( - 1 ) * n)Y--;
    
    else if(X < n && X > ( - 1 ) * n && Y == ( - 1 ) * n) X--;
    else;
    
    if(Y==y&&X==x)
    {
      num=i;
      break;
    } 
  } 
  cout<<num<<endl;
  
  
  return 0;
}

这样对于大的数字就会超时，只能得84分

后面我又根据横坐标和做坐标相同，可以将每个分为4部分，每次找到这一部分的第一个在开始遍历，就又缩小计算的范围，缩短时间。

代码2

#include<iostream>
#include<cmath>//包含求绝对的函数 
using namespace std;
int main()
{
  long long int x,y,num=0,a;
  
  cin>>x>>y;
  long long int n=(abs(x)>abs(y))?abs(x):abs(y);
  long long int X=0,Y=0;
  if(x==(-1)*n){a=0;X=(-1)*n,Y=(-1)*(n-1);}
  if(y==n){a=1;Y=n,X=(-1)*(n-1);}
  if(x==n){a=2;X=n,Y=n-1;}
  if(y==(-1)*n){a=3;X=n-1,Y=(-1)*n;}
  //a代表第几部分
  long long int b=(2*n-1)*(2*n-1)+a*2*n;
  
  for(long long int i=b;i<b+2*n;i++)
  {
    if(Y==y&&X==x)
    {
      num=i;
      break;
    }
    
    if(X == ( - 1 ) * n && Y > (-1)*n && Y < n ) Y++;
    
    else if ( X < n && X >= ( - 1 ) * n && Y == n)X++;
    
    else if(X == n && Y <= n && Y > ( - 1 ) * n)Y--;
    
    else if(X <= n && X > ( - 1 ) * n && Y == ( - 1 ) * n) X--;
    else;
    
  
  } 
  cout<<num<<endl;
  
  
  return 0;
}

最后吧这个放在一起方便观察