遇到过两种螺旋折线的题目

No.1  蓝桥杯第九届省赛C++大学B组第七题

螺旋折线

如图p1.png所示的螺旋折线经过平面上所有整点恰好一次。  
对于整点(X, Y)，我们定义它到原点的距离dis(X, Y)是从原点到(X, Y)的螺旋折线段的长度。  

例如dis(0, 1)=3, dis(-2, -1)=9  

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

【输入格式】
X和Y  

对于40%的数据，-1000 <= X, Y <= 1000  
对于70%的数据，-100000 <= X， Y <= 100000  
对于100%的数据, -1000000000 <= X, Y <= 1000000000  

【输出格式】
输出dis(X, Y) 
【样例输入】
0 1

【样例输出】
3
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗  < 1000ms

思路：

这个题呢，我们可以找出规律来

我们先观察（3，3）这个点   d(3,3)=6+5+5+4+4+3+3+2+2+1+1;

这个数一看就很有规律嘛，我们再看d(3,-3)=6+6+5+5+4+4+3+3+2+2+1+1;

很显然  我们首先呢  找一下这个数列的通项公式   1*2+2*2+3*2+4*2+5*2+......+n*2

2,4,6,8,10....显然的等差数列  那么前n项的和就是  Sn= n*(n*2+2)/2 

化简就是 = n*(n+1)        故  = n*(n-1)

得到了这个公式后呢  这个题就算完成了一半了

然后呢我们对平面上的区域做个简单的划分

网上有很多种划分方法，我这个是我看到这个题后自己写的一种，并不是最优秀的

四个象限  我们把它划分为8个区域（看起来很多  其实并不复杂

站在不同区域的角度  n是不一样的

对于区域1、8、4、5     n就是|x|*2（y可以变 x是不变的）   对于2、3、6、7来说，n就是|y|*2

虽然有八个区域 但是我们计算的时候 其实是四种情况

  1. 对于区域1和8的坐标  我们先算出它跑到x=y这条线是多远（比如点(3,1),它到(3,3)距离是2），然后再加上n+
  2. 对于区域2和3呢  我们先算出它距离x=-y这条线有多远，然后再加上 就好了
  3. 对于区域4和5呢 我们计算出它距离y=x+1这条线有多远  然后再加上 n-1+
  4. 对于区域6和7呢 我们计算出它距离y=-x这条线有多远  然后再加上   (区域6和7的n比其他三块区域的n小1)

注意  有的同学可能会觉得 这样划分  5区域会有问题

因为  5区域我们取|x|*2  为n  但是5区域有个拐弯  x轴坐标是变了的

其实没问题  注意  题目说了 输入的坐标值是整数！整数！所以，下图两个绿色线中间的区域是没有输入数据的，所以5区域其实到拐角（在x坐标未改变之前）就结束了，x坐标改变后就到了6区域了。

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
using namespace std;
int x,y,d,n;
long long sum;
int main(){
    scanf("%d%d",&x,&y);
    if(x>=0&&y>=0){//第一象限
        if(x>=y){//区域1
            n=x*2;
            d=x-y+n+n*(n-1);
        }
        else{//区域2
            n=y*2;
            d=y+x+n*(n-1);
        }
    }
    else if(x<=0&&y>=0){//第二象限
        x=-x;
        if(x>y){//区域4
            n=x*2;
            d=x-1+y+ n-1 +(n-2)*(n-1);
        }
        else{//区域3
            n=y*2;
            d=y-x+n*(n-1);
        }
    }
    else if(x<=0&&y<=0){//第三象限
        x=-x;y=-y;
        if(x>y){//区域5
            n=x*2;
            d=x-1-y+n-1+(n-2)*(n-1);
        }
        else{//区域6
            n=y*2;
            d=y+x+ n*(n+1);
        }
    }
    else if(x>=0&&y<=0){//第四象限
        y=-y;
        if(x>=y){//区域8
            n=x*2;
            d=x+y+n+n*(n-1);
        }
        else{//区域7
            n=y*2;
            d=y-x+n*(n+1);
        }
    }
    printf("%d\n",d);
    
    return 0;
}

 

No.2 

题解：

这个题会发现，一圈走下来的步数是和边长有关系的。

当时我的做法是一层一层往里面走，一次走一层，直到走不了一层了为止

也过了  不过不是最优秀的做法

最好的二分层数  这样的话log复杂度就能找到临界层

另外  从里往外走也可以，总的步数减去里面的剩下的就是走的步数， 思路是一样的 同样二分层数  找到临界层

贴一下我比赛时候的代码 （没二分）

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
ll x1,y1,n1,k1;
void s(ll x,ll y,ll n,ll k){
    while(1){
        if(  (4*n-4)>k  ){
            x1=x;y1=y;
            n1=n;k1=k;return ;
        }
        else{
            k=k-(4*n-4);
            x+=1;y+=1;
            if(n<=3){
               x1=x;y1=y;n1=n;k1=k; return;
            }
            n-=2;
        }
    }
}
ll n,k;
int main(){

    scanf("%lld%lld",&n,&k);
    if(k==0){printf("1 1\n");return 0;}

    s(1,1,n,k);

    if(k1==0){printf("%lld %lld\n",x1,y1);return 0;}
    while(1){
            if(k1>=n1-1){//right
                k1-=(n1-1);
                y1=y1+n1-1;
            }
            else{
                y1=y1+k1;k1=0;
            }
            if(k1==0){printf("%lld %lld\n",x1,y1);return 0;}

            if(k1>=n1-1){//down
                k1-=(n1-1);
                x1=x1+n1-1;
            }
            else{
                x1=x1+k1;k1=0;
            }
            if(k1==0){printf("%lld %lld\n",x1,y1);return 0;}

            
            if(k1>=n1-1){//left
                k1-=(n1-1);
                y1=y1-(n1-1);
            }
            else{
                y1=y1-k1;k1=0;
            }
            if(k1==0){printf("%lld %lld\n",x1,y1);return 0;}

            
            if(k1>n1-1){//up
                k1-=(n1-1);
                x1=x1-(n1-1);
            }
            else{
                x1=x1-k1;k1=0;
            }
            if(k1==0){printf("%lld %lld\n",x1,y1);return 0;}

    }

    return 0;
}