2017.9.23 NOIP2017 金秋杯系列模拟赛 day1 T1

时间:2022-12-16 15:13:07

回形遍历( calc .cpp/c/pas)

时间限制:1s
内存 限制: 256MB

【问题 描 述】

给出一个 n*m 的棋盘,按如下方式遍历,请问(x,y)往后 z 步走到的是哪个格子。

2017.9.23 NOIP2017 金秋杯系列模拟赛 day1 T1

【输入】

输入文件名为 calc.in。
一行,包含五个整数:n,m,x,y,z

【输出】

输出文件名为 calc.out。
输出一行,包含两个整数,表示所在格子的横纵坐标

【输入输出样例】

  calc .in     calc .out  
4 5 3 0 5 2 4

【 样例解释 】

2017.9.23 NOIP2017 金秋杯系列模拟赛 day1 T1

【数据说明】

对于 70%的数据,1<=n,m,z<=1000,0<=x<n,0<=y<m
对于 100%的数据,1<=n,m,z<=100000,0<=x<n,0<=y<m

思路:

  1)70%的思路:

      (使用数组存储的)模拟/搜索

      ①模拟的话,就弄一个fx记录正在往什么方向走,然后用jz数组记录下来走过的路程,然后特判一下如果走到了(x,y)位置,只需要在继续模拟z步,然后最后输出走到了哪里即可

      ②搜索的思路其实跟模拟是一样的。。。

  2)100%的思路:

    因为空间开100000*100000会炸掉,所以上面的模拟/搜索思路已经不能够适用了,所以我们应该想出一种不开数组存数的办法

    思路如下:(以下所说的i==横坐标,y==纵坐标)

      首先你需要拥有一个n*m的矩阵,然后找寻一下规律,如下图:

2017.9.23 NOIP2017 金秋杯系列模拟赛 day1 T1

      首先考虑,如果我们一个一个的来跳的话,跳到最后一定会超时,所以就一排(列)的跳,如图2017.9.23 NOIP2017 金秋杯系列模拟赛 day1 T1

    假设已经跳到了(x,y)所在的行:(之前如何跳就是用当前的i或者是j是否比x或者是y在同一排或者是列,如果不在,就继续成排成列的跳)

    然后跟给出的(x,y)中的j进行比较(因为这一排的i都是跟x相同的,只有j不同)。

    如果j>y了,那么就说明多走了几步,题目中又需要求从(x,y)往后走z步到达的点的坐标,所以用当前的点的j减去y就是当前点多走的步数(记住我们是一走走一排)。

    2017.9.23 NOIP2017 金秋杯系列模拟赛 day1 T1

      如果减出来的数比z大(j-y>z)就说明多走了,所以直接在当前的基础(i,j)上往回走j-y-z步即可,即在(x,y)基础上往右直接走z步如图:2017.9.23 NOIP2017 金秋杯系列模拟赛 day1 T1

2017.9.23 NOIP2017 金秋杯系列模拟赛 day1 T1

      如果减出来的数比z小(j-y<z),那么就说明还需要继续走。但是需要在当前的基础(i,j)上走多少步呢?

        其实就是用z-(j-y)得出还需要往下走z-j+y步,所以就转入往下的操作,如图:2017.9.23 NOIP2017 金秋杯系列模拟赛 day1 T1

 

      (往下左上的操作自己手动模拟就好啦~这里就不给出了。。)

坑点:

  第一种的时候数组千万别开大了啊啊啊啊!原来空间辣么小(256MB),炸掉了qwq

  我safufu的开了100000*100000的数组2333

  ps:计算空间是用100000*100000*4/(1024*2)约是38200MB>256MB

上代码:

1)70分无脑模拟(嘻嘻,至于搜索嘛~自己意会意会咯!)

#include<cstdio>
#include<iostream>
using namespace std;

const int Maxx=1011;
int jz[Maxx][Maxx];
int n,m,x,y,z;

int main() {
    freopen("calc.in","r",stdin);
    freopen("calc.out","w",stdout);
    scanf("%d%d%d%d%d",&n,&m,&x,&y,&z);
    x++,y++;
    int js=0,i=1,j=1,fx=1,Maxn=n*m;
    while(js<Maxn) {
        if(!jz[i][j])
            jz[i][j]=++js;
        if(i==x && j==y)
            Maxn=js+z;
        if(fx==1) {
            j++;
            if(j>m || jz[i][j]!=0) fx=2,j--;
        } else if(fx==2) {
            i++;
            if(i>n || jz[i][j]!=0) fx=3,i--;
        } else if(fx==3) {
            j--;
            if(j<1 || jz[i][j]!=0) fx=0,j++;
        } else if(fx==0) {
            i--;
            if(i<1 || jz[i][j]!=0) fx=1,i++;
        }
    }
    printf("%d %d",i,j);
    return 0;
}

2)正解模拟w

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int main() {
    freopen("calc.in","r",stdin);
    freopen("calc.out","w",stdout);
    int m,n,x,y,z;
    scanf("%d%d%d%d%d",&m,&n,&y,&x,&z);
    int penx=0,peny=0,step=0;
    int i=n-1,j=m-1,flag=1;
    bool right=true,up=false;
    bool first=true;
    int cnt=0;
    while(!(step==n*m-1)) {
        if(flag)  {
            step+=j;
            if(right) {
                peny+=j;
                if(penx==x && peny>=y) {
                    cnt+=peny-y;
                    y=peny;
                    if(cnt>=z) {
                        printf("%d %d",y-cnt+z,x);
//                        fclose(stdin);fclose(stdout);
                        return 0;
                    }
                }
            } else  {
                peny-=j;
                if(penx==x && peny<=y) {
                    cnt+=y-peny;
                    y=peny;
                    if(cnt>=z) {
                        printf("%d %d",y+cnt-z,x);
//                        fclose(stdin);fclose(stdout);
                        return 0;
                    }
                }
            }
            if(!first) j--;
            else first=false;
            right=!right;
        } else {
            step+=i;
            if(up) {
                penx-=i;
                if(peny==y && penx<=x) {
                    cnt+=x-penx;
                    x=penx;
                    if(cnt>=z) {
                        printf("%d %d",y,x+cnt-z);
//                        fclose(stdin);fclose(stdout);
                        return 0;
                    }
                }
            } else  {
                penx+=i;
                if(peny==y && penx>=x) {
                    cnt+=penx-x;
                    x=penx;
                    if(cnt>=z) {
                        printf("%d %d",y,x-cnt+z);
//                        fclose(stdin);fclose(stdout);
                        return 0;
                    }
                }
            }
            i--;
            up=!up;
        }
        flag^=1;
    }
    printf("%d %d",peny,penx);
//    fclose(stdin);fclose(stdout);
    return 0;
}