题解

36 条题解

  • 3
    @ 2018-05-23 20:09:25

    思路:
    1、判断(x,y)在哪一层。
    2、算出该层的最左上角的数字(该层最小的一个数字;作为该层开头)
    和它下面一个数字(该层最大的一个数字;作为该层结尾)。
    3、判断(x,y)在右上半部分还是左下半部分。
    4、从开头或者是结尾,加上或是减去这个点到开头或结尾的长度。
    #include<iostream>
    #include<cmath>
    using namespace std;
    int n,x,y,c,s,e=0,t=0,N;
    int main(){
    cin>>n>>y>>x;
    c=min(x,y);c=min(c,(n-x+1));c=min(c,(n-y+1));
    N=n;
    for(int i=1;i<=c;i++){
    e=e+4*(N-1);
    N=N-2;
    }
    s=e-4*(n-2*c+1)+1;
    if(n%2==1&&c==(n+1)/2){
    s=n*n;e=n*n;
    }
    if(x>=y){
    cout<<(s+(x-c)+(y-c))<<endl;
    }else{
    cout<<(e-(x-c)-(y-1-c))<<endl;
    }
    return 0;
    }

  • 1
    @ 2021-02-25 12:34:01
    #include<bits/stdc++.h>
    using namespace std;
    int n,m,p,q,ans,sum;
    int work(int n,int i,int j)
    {
        if(i==1)
        {
            return j;
        }
        else if(j==n)return n+i-1;
        else if(i==n)return 3*n-2-j+1;
        else if(j==1)return 4 * n - 4 - i + 2;
        return work(n - 2, i - 1, j - 1) + 4 * (n - 1);
    }
    int main()
    {
        cin>>n>>p>>q;
        cout<<work(n,p,q);
    }
    
  • 1
    @ 2018-05-23 20:07:00

    找规律嘛,水题水题

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<map>
    #include<queue>
    #include<vector>
    #include<cstdlib>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    int ans=0;
    int x,y,luyan=1;
    int n,dx,dy;
    
    int main(){
        //freopen("playground.in","r",stdin);
        //freopen("playground.out","w",stdout);
        cin>>n>>dx>>dy;
        if(dx>n/2)  
            y=n-dx+1;
        else
            y=dx;
        if(dy>n/2)
        {
            x=n-dy+1;
        }
        else
        {
            x=dy;
        }
        int m=min(x,y);
        for(int k=1;k<=m-1;k++)
        {
            luyan+=4*(n-1);
            n=n-2;
        }
        int x1=dx-m+1,yy1=dy-m+1; 
        if(x1==1)
        {
            cout<<luyan+yy1-1;
            //fclose(stdin);
            //fclose(stdout);
            return 0;
        }
        if(yy1==1){
            cout<<luyan+4*(n-1)-1-x1+2;
            //fclose(stdin);
            //fclose(stdout);
            return 0;
        }
        if(yy1>x1){
            cout<<luyan+n-1+x1-1;
            //fclose(stdin);
            //fclose(stdout);
            return 0;
        }
        if(x1>yy1) 
        {
            cout<<luyan+4*(n-1)-1-n+2-yy1+1;
            //fclose(stdin);
            //fclose(stdout);
            return 0;
        }
        if(x1==yy1) 
        {
            cout<<luyan+(n-1)+(n-2)+1;
            //fclose(stdin);
            //fclose(stdout);
            return 0;
        }
        //fclose(stdin);
        //fclose(stdout);
        return 0;
    }
    
  • 1
    @ 2016-11-06 19:55:53

    展♂开即可
    ```c++
    #include <iostream>
    #include <algorithm>
    using namespace std;

    int main()
    {
    int n, x, y;
    int i, j, k;

    cin >> n >> x >> y;
    for(i = 1, j = n, k = 0;x != i && x != j && y != i && y != j;i ++, j --)
    k += (j - i) * 4;

    if(x == i)
    cout << k + 1 + y - i;
    else if(x == j)
    cout << k + (j - i) * 3 + 1 - y + i;
    else if(y == i)
    cout << k + (j - i) * 3 + 1 - x + j;
    else if(y == j)
    cout << k + j - 2 * i + 1 + x;
    cout << endl;

    return 0;
    }
    ```

  • 1
    @ 2015-04-23 20:05:15

    好吧,秒杀AC了- -这题目考的TM的是浆糊啊- -做题前想的好好的思路写着写着就乱了。醉了- -5分钟写好调试用了好久好久。自抽。

    那么由我来发一份完整的题解给各位。

    这道题乍看之下非常棘手。但是其实数据还是很水的。我们一开始可能认为啊。这道题有什么数学公式,实际上仔细去思考发现不可能有数学公式可以推出来(如果有,那么几行代码就能解决,把这种题目放在普及组比较难的题目里是绝对不可能的。)因此我们思路应该转到怎么枚举出答案。

    枚举方法很多,楼下很多人看代码似乎跟我的想法很像,我有3 4个思路,不过觉得这个比较好实现就用了这个,其实也是差不多的。我这个代码的时间复杂度最坏情况是(4*30000)左右,很明显已经足够秒杀此题,也就懒得优化了,直接去数一圈了。我以为有个点会过100MS,呵呵,数据水到100都不用- -

    那么怎么去写呢?很简单

    我们发现这个矩阵由一圈一圈组成。什么是一圈一圈,就是这个
    1 1 1 1
    1 2 2 1
    1 2 2 1
    1 1 1 1
    这个算是一圈。我们不难推出,一圈上增加的数就是大圈(1)减去小圈(2)各位对照N=4的样例。

    因此要是我们知道我们求的点在哪一圈,就可以快速把它外围的圈瞬间求出来,之后只要在循环做一圈就OK,如果i,j找到了就是答案,找不到就ans+1就可以得到答案了。

    那么怎么知道这货在第几圈?我们用变量num存它在第几圈。拿i举例,n=5时候,j=1或5答案只会在第一圈,2或4的时候答案就可能在第1或2圈,i同理。我们可以画画图想一想。发现有个很牛叉的结论。

    比如i在最多只能在3圈,j最多可以在2圈,那么答案必在少的这个上。即我们求的点在第2圈的某个点上
    因此num=min(i,j,n-i+1,n-j+1)
    这个结论我不好讲。听不懂的话只能靠意会。各位要可以自己动手或者想下吧。。

    然后我们num-1.把前几圈的值用上面的那个公式直接算好。就跟我程序里一样。

    然后就在4个for,走一圈就行了。主要4个角。不要数重复了。详细看我程序。还要注意一些特殊情况能不能考虑到。

    然后轻松AC。

    ###pascal code
    program P1913;
    uses math;
    var n,i,j,a,b,num,ans,k:longint;
    procedure pd;
    begin
    if (a=i) and (j=b) then begin write(ans); halt; end;
    end;

    begin//main
    read(n,i,j); ans:=0;
    num:=min(i,j); num:=min(num,n-i+1); num:=min(num,n-j+1); dec(num); //找到num
    if n=1 then begin write('1'); halt; end; //特判,保险
    for k:=num downto 1 do ans:=ans+(n-2*k+2)*(n-2*k+2)-(n-2*k)*(n-2*k); //计算前num-1圈的值
    inc(num); //答案肯定在第num圈
    a:=num; b:=num; //从起点准备枚举
    if (a=i) and (j=b) then begin write(ans+1); halt; end; //特判,刚好在起点。
    for b:=num to n-num+1 do //从左到右
    begin
    inc(ans); pd;
    end;

    for a:=num+1 to n-num+1 do //从上到下
    begin
    inc(ans); pd;
    end;

    for b:=b-1 downto num do //右到左
    begin
    inc(ans); pd;
    end;

    for a:=a-1 downto num do //下到上
    begin
    inc(ans); pd;
    end;

    write('yes,you can AC it'); //反正也输不出来,拿出来激励人
    end.

    • @ 2015-11-07 10:57:12

      分析点赞♂

  • 0
    @ 2021-06-12 16:47:31

    模拟大法

    #include<stdio.h>
    int n,x,y;
    int min(int n1,int n2){
        if(n1<n2)return n1;
        else return n2;
    }
    int solve(){
      scanf("%d%d%d",&n,&x,&y);
      int layer=min(x,n+1-x);//确定层,n方阵,如n=7,x=5就是第二层
      layer=min(layer,min(y,n+1-y));
      int num=0,side=n-1;
      for(int i=1;i<layer;i++,side-=2){
        int layer_total;
        if(side==0)layer_total=1;
        else layer_total=side*4;//当前层一圈总个数
        num+=layer_total;
      }
      num++;
      int nx=layer,ny=layer;
      if(nx==x && ny==y)return num;
      for(int i=1;i<=side;i++){
        ny++;num++;//y列向右递增
        if(nx==x && ny==y)return num;
      }
      for(int i=1;i<=side;i++){
        nx++;num++;//x行向下递增
        if(nx==x && ny==y)return num;
      }
      for(int i=1;i<=side;i++){
        ny--;num++;//y列向左递增
        if(nx==x && ny==y)return num;
      }
      for(int i=0;i<side;i++){
        nx--;num++;//x行向上递增
        if(nx==x && ny==y)return num;
      }
      return -1;
    }
    int main(){
      int res=solve();printf("%d",res);
      return 0;
    }
        
        ```
    
  • 0
    @ 2018-11-03 22:26:40

    Water!!

    #include<cstdio>
    int read()
    {
        int a=0,f=1; char c=getchar();
        while(c<'0'||c>'9') { if(c=='-') f=-f; c=getchar(); }
        while(c>='0'&&c<='9') a=a*10+c-'0',c=getchar();
        return a*f;
    }///读入优化不解释
    int n=read(),i=read(),j=read(),x=1,y=1,num=1,h=n,l=n,h1=1,l1=2;///l1第一次只能走到2了
    int main()
    {
        while(y!=i||x!=j)
        {
            if(y==i)///如果是这一排
            {
                printf("%d",num+j-x);///之前走的步数加上还需要走的步数
                return 0;
            }
            num+=h-x;///加上这一排需要走的步数
            x=h--;///x为当前可以走到的地方,之后这个地方就不可以走了
     
            if(x==j)///如果是这一列
            {
                printf("%d",num+i-y);///之前走的步数加上还需要走的步数
                return 0;
            }
            num+=l-y;///加上这一列需要走的步数
            y=l--;///y为当前可以走到的地方,之后这个地方就不可以走了
     
            if(y==i)///如果是这一排
            {
                printf("%d",num+x-j);///之前走的步数加上还需要走的步数
                return 0;
            }
            num+=x-h1;///加上这一排需要走的步数
            x=h1++;///x为当前可以走到的地方,之后这个地方就不可以走了
     
            if(x==j)///如果是这一列
            {
                printf("%d",num+y-i);///之前走的步数加上还需要走的步数
                return 0;
            }
            num+=y-l1;///加上这一列需要走的步数
            y=l1++;///y为当前可以走到的地方,之后这个地方就不可以走了
        }
        printf("%d",num);
    }
    
  • 0
    @ 2018-07-20 16:18:11

    #include <iostream>

    using namespace std;

    int main()
    {
    int n,x,y;
    cin>>n>>x>>y;
    int l=min(min(x,n+1-x),min(y,n+1-y));
    int begin=4*(l-1)*(n-2*l+2)+4*(l-1)*(l-1)+1;
    if(l==x)
    cout<<begin+y-l<<endl;
    else if(l==n-x+1)
    cout<<begin+3*(n-2*l+1)-y+l<<endl;
    else if(l==y)
    cout<<begin+4*(n-2*l+1)+l-x<<endl;
    else
    cout<<begin+n-2*l+x-l+1<<endl;
    return 0;
    }

  • 0
    @ 2018-07-20 16:09:48

    这题有多弱智呢?
    估计连学过小奥的四年级小学生都能说出解题流程

    #include <iostream>

    using namespace std;

    int main()
    {
    int n,x,y;
    cin>>n>>x>>y;
    int l=min(min(x,n+1-x),min(y,n+1-y));
    int begin=4*(l-1)*(n-2*l+2)+4*(l-1)*(l-1)+1;
    if(l==x)
    cout<<begin+y-l<<endl;
    else if(l==n-x+1)
    cout<<begin+3*(n-2*l+1)-y+l<<endl;
    else if(l==y)
    cout<<begin+4*(n-2*l+1)+l-x<<endl;
    else
    cout<<begin+n-2*l+x-l+1<<endl;
    return 0;
    }

  • 0
    @ 2018-06-07 18:45:30
        #include <iostream>
        using namespace std;
        int n,a,b,nowx,nowy,lowx=1,lowy=1,num=0;
        void solve(int n){
            int x=1,y=1,x1=n,y1=n,turn=1,i,line=n;
            while(true){
                if(x!=a&&y!=b&&x1!=a&&y1!=b){
                    num+=line*4-4;
                    x++;y++;x1--;y1--;
                    line-=2;
                    nowx--;nowy--;
                    lowx++;lowy++;
                }
                else if(x==a||y==b||x1==a||y1==b){
                    while(i++){
                        if(turn==1)
                        {
                            if(x==a&&y==b) {cout<<num+1<<endl;return;}
                            else
                            {
                                if(y<nowy) {y++;num++;}
                                else if(y==nowy) turn=2;
                            }   
                        }
                        else if(turn==2)
                        {
                            if(x==a&&y==b) {cout<<num+1<<endl;return;}
                            else
                            {
                                if(x<nowx) {x++;num++;}
                                else if(x==nowx) turn=3;
                            }
                        }
                        else if(turn==3)
                        {
                            if(x==a&&y==b) {cout<<num+1<<endl;return;}
                            else 
                            {
                                if(y>lowy) {y--;num++;}
                                else if(y==lowy)
                                {
                                    turn=4;lowy++;lowx++;
                                }
                            }
                        }
                        else if(turn==4)
                        {
                            if(x==a&&y==b) {cout<<num+1<<endl;return;}
                            else
                            {
                                if(x>lowx) {num++;x--;}
                                else if(x==lowx)
                                {
                                    turn=1;nowx--;nowy--;
                                }
                            }
                        }
                    }
                }
            }
        }
        int main()
        {
            cin>>n>>a>>b;
            nowx=nowy=n;
            solve(n);
            return 0;
        }
    

    暴力计算某坐标数值,优化版。

  • 0
    @ 2018-05-18 21:39:58

    观察一下规律,跟着数字增长的方向走,不难发现:

    如果是第 1 行,那么第 j 列的数字就是 j ;

    如果是第 n 列,那么第 i 行的数字就是 n + i - 1;

    后两条规律有点难找,但是不要放弃,继续观察:

    如果是第 n 行,那么第 j 列的数字就是 3*n-2-j+1

    如果是第 1 列,那么第 i 行的数字就是 4*n-4-i+2

    如果对于上述推导过程不是很理解,不妨打开 Excel,自己画图观察。

    推导完公式,剩下的就简单多了。不难想出一个递归解法:把螺旋矩阵一层一层地剖开,看看目标位置在哪一层,然后加上这一层最左上角的数字
    (4*(n-1)),即为要求的数字。

    上代码:
    #include<bits/stdc++.h>

    using namespace std;

    int work(int n, int i, int j) {
    if (i == 1)
    return j;
    if (j == n)
    return n + i - 1;
    if (i == n)
    return 3 * n - 2 - j + 1;
    if (j == 1)
    return 4 * n - 4 - i + 2;
    return work(n - 2, i - 1, j - 1) + 4 * (n - 1);
    }

    int main()
    {
    int m,x,y;
    cin>>m>>x>>y;
    cout<<work(m,x,y);
    return 0;
    }

  • 0
    @ 2018-04-22 22:44:44

    从1开始暴力计算到某一数据的坐标。

    #include <iostream>
    using namespace std;
    int n,a,b,nowx,nowy,lowx=1,lowy=1,num=0;
    void solve(int n)
    {
        int x=1,y=1,turn=1,i;
        for(i=0;;i++)
        {
            if(turn==1)
            {
                if(x==a&&y==b) {cout<<num+1<<endl;break;}
                else
                {
                    if(y<nowy) {y++;num++;}
                    else if(y==nowy) turn=2;
                }   
            }
            else if(turn==2)
            {
                if(x==a&&y==b) {cout<<num+1<<endl;break;}
                else
                {
                    if(x<nowx) {x++;num++;}
                    else if(x==nowx) turn=3;
                }
            }
            else if(turn==3)
            {
                if(x==a&&y==b) {cout<<num+1<<endl;break;}
                else 
                {
                    if(y>lowy) {y--;num++;}
                    else if(y==lowy)
                    {
                        turn=4;lowy++;lowx++;
                    }
                }
            }
            else if(turn==4)
            {
                if(x==a&&y==b) {cout<<num+1<<endl;break;}
                else
                {
                    if(x>lowx) {num++;x--;}
                    else if(x==lowx)
                    {
                        turn=1;nowx--;nowy--;
                    }
                }
            }
        }
    }
    int main()
    {
        cin>>n>>a>>b;
        nowx=nowy=n;
        solve(n);
        return 0;
    }
    
  • 0
    @ 2018-03-18 20:07:57

    #include<iostream>
    using namespace std;
    int min1(int a,int b){
    return a<b?a:b;
    }
    int min2(int a,int b,int c,int d){
    return min1(min1(a,b),min1(c,d));
    }
    int main(){
    int n,i,j,abc=0,sum=0;
    cin>>n>>i>>j;
    int x=n/2;
    int temp=min2(i-1,j-1,n-i,n-j);
    for(int i1=n;;i1=i1-2){
    sum+=4*i1-4;abc++;
    if(abc==temp) break;
    }
    if(i<=j) sum+=(i+j-2*temp-1);
    else sum+=(2*n-2*temp-i-j-1+2*n-4*temp);
    cout<<sum;
    return 0;
    }//努力看能看懂的

  • 0
    @ 2017-06-06 16:24:30
    /*
    不用数组的暴力模拟,时间能过,主要是绕过了数组太大的问题
    */
    #include <bits/stdc++.h>
     using namespace std;
     
     int main()
     {
       int size, row, col;
       int count = 1;
       int i = 1, j = 1;
       cin >> size >> row >> col;
       int up = 2, left = 1, down = size, right = size;
       while(count < size * size)
       {
        while(j < right)
        {
            if(i == row && j == col) 
            {
              cout << count << endl;
              return 0;
            }
                j++;
            count++;
        }
        right--;
        while(i < down)
        {
            if(i == row && j == col) 
            {
              cout << count << endl;
              return 0;
            }
            i++;
            count++;
        }
        down--;
        while(j > left)
        {
          if(i == row && j == col) 
            {
              cout << count << endl;
              return 0;
            }
            j--;
            count++;
        }
        left++;
        while(i > up)
        {
          if(i == row && j == col) 
            {
              cout << count << endl;
              return 0;
            }
            i--;
            count++;
        }
        up++;
       }
        cout << count << endl;
        return 0;
     }
    
    
  • 0
    @ 2017-01-31 09:43:45

    你们 为什么 可以写那么短,我写了快一百行了....
    Var
    n,x,y:longint;

    Procedure zx(a,b,h,l,k:longint);
    Var
    i,q,s:longint;

    Begin
    if (x=h) and (y=l) then
    begin
    writeln(a);
    exit;
    end;
    s:=a; q:=l;
    for i:=s to s+k-2 do
    if x=h then
    begin
    if y=q then
    begin
    writeln(i);
    exit;
    end;
    inc(q);
    end
    else
    break;
    s:=s+k-1; q:=h;
    for i:=s to s+k-2 do
    if y=l+k-1 then
    begin
    if x=q then
    begin
    writeln(i);
    exit;
    end;
    inc(q);
    end
    else
    break;
    s:=s+k-1; q:=l+k-1;
    for i:=s to s+k-2 do
    if x=h+k-1 then
    begin
    if y=q then
    begin
    writeln(i);
    exit;
    end;
    dec(q);
    end
    else
    break;
    s:=s+k-1; q:=h+k-1;
    for i:=s to s+k-2 do
    if y=l then
    begin
    if x=q then
    begin
    writeln(i);
    exit;
    end;
    dec(q);
    end
    else
    break;
    End;

    Procedure dfs(h,l,i,j,k:longint);
    Var
    ch:boolean;
    Begin
    if k<0 then
    k:=1;
    ch:=false;
    if (x=h+k-1) and (y>=l) and (y<=l+k-1) then
    ch:=true;
    if (x=h) and (y>=l) and (y<=l+k-1) then
    ch:=true;
    if (x>=h) and (x<=h+k-1) and (y=l+k-1) then
    ch:=true;
    if (x>=h) and (x<=h+k-1) and (y=l) then
    ch:=true;
    if ch then
    begin
    zx(i,j,h,l,k);
    exit;
    end
    else
    dfs(h+1,l+1,j+1,j+2*(k-2)+2*(k-4),k-2);
    End;

    Begin
    readln(n,x,y);
    dfs(1,1,1,2*n+2*(n-2),n);
    readln;
    End.

  • 0
    @ 2017-01-21 07:52:27

    var
    n,i,j,q:longint;
    ans:int64;
    function min(a,b:longint):longint;
    begin
    if a<b then exit(a);exit(b);
    end;
    begin
    readln(n,i,j);
    q:=min(i,min(j,min(n-i+1,n-j+1)));
    if i<=j then
    ans:=4*n*q-4*q*q+6*q-4*n-3+i+j
    else
    ans:=4*n*q-4*q*q+2*q+1-i-j;
    writeln(ans);
    end.

  • 0
    @ 2016-10-02 15:41:59

    深搜,从外圈一层层拨♂开
    用数学推导出处于边界的数值,
    若不在边界则深搜至下一圈。
    ```pascal
    program Rectangle;
    var n,i,j:longint;

    procedure Getlost(lol:longint);
    begin
    writeln(lol);
    halt;
    end;

    procedure Diehere(c,x,y,n:longint);
    begin
    if not((x=1)or(x=n)or(y=1)or(y=n)) then Diehere(c+4*n-4,x-1,y-1,n-2);
    if x=1 then Getlost(c+y-1);
    if x=n then Getlost(c+3*n-2-y);
    if y=1 then Getlost(c+4*n-x-3);
    if y=n then Getlost(c+n+x-2);
    end;

    begin
    readln(n,i,j);
    Diehere(1,i,j,n);
    end.
    ```

  • 0
    @ 2016-08-28 17:42:22

    疯狂地模拟。。。。。。
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    #include<cstdio>
    #include<cstdlib>
    using namespace std;
    int n,im,jm,i=1,j=1,ls,lx,lz,ly,dir;
    long int ans=1;
    bool epo=false;
    int main()
    {
    scanf("%d%d%d",&n,&im,&jm);
    ls=1;
    lx=n;
    lz=1;
    ly=n;
    dir=2;
    while(1)
    {
    if(dir==1&&j==jm) {ans+=i-im;break;}
    if(dir==2&&i==im) {ans+=jm-j;break;}
    if(dir==3&&j==jm) {ans+=im-i;break;}
    if(dir==4&&i==im) {ans+=j-jm;break;}
    if(dir==1) {ans+=lx-ls;lx--;i=ls;dir=2;continue;}
    if(dir==2)
    {
    ans+=ly-lz;
    if(epo==false) epo=true;
    else lz++;
    j=ly;
    dir=3;
    continue;
    }
    if(dir==3) {ans+=lx-ls;ls++;i=lx;dir=4;continue;}
    if(dir==4) {ans+=ly-lz;ly--;j=lz;dir=1;}
    }
    printf("%ld\n",ans);
    return 0;
    }

  • 0
    @ 2016-08-05 18:09:47

    如果在最外圈则特判,否则转化为在内圈找,坐标相应变化即可。
    ```
    #include <iostream>
    #include <cstdio>
    using namespace std;

    int num(int beg, int n, int i, int j)
    {
    if (i == 1) return beg+j-1;
    if (j == n) return beg+n+i-2;
    if (i == n) return beg+n+n-2+n-j;
    if (j == 1) return beg+n+n+n-3+n-i;
    return num(beg+4*(n-1), n-2, i-1, j-1);
    }

    int main()
    {
    int n, i, j;
    cin >> n >> i >> j;
    cout << num(1, n, i, j) << endl;
    return 0;
    }
    ```

  • 0
    @ 2016-07-12 16:16:34

    还用发题解吗?

信息

ID
1913
难度
5
分类
(无)
标签
递交数
2027
已通过
624
通过率
31%
被复制
16
上传者