AtCoder Beginner Contest 335 C - Loong Tracking 题解

前言

一眼题没场切，我是普及 3= 小飞屋，罚自己写篇题解。

题意

平面直角坐标系上有 $N$ 个点，每个点 $i$ 的初始坐标为 $(i,0)$ 。

现在进行 $Q$ 次操作：

1 C 代表把编号为 $1$ 的点向方向 $C$ 移动一个单位长度（R 代表 $x$ 轴正方向，L 代表 $x$ 轴负方向，U 代表 $y$ 轴正方向，D 代表 $y$ 轴负方向），同时对于每个编号大于 $1$ 的点 $i$ ，将点 $i$ 移动到点 $i-1$ 原先的位置；
2 x 代表查询编号为 $x$ 的点当前的坐标。

思路

方法 $1$ ： $\mathcal{O}(NQ)$ ，暴力更新坐标

对于每次操作 1 从点 $1$ 开始暴力更新每个点 $i$ 的坐标即可。

方法 $2$ ： $\mathcal{O}(Nk)$ （ $k$ 代表操作 `1` 的次数），暴力递推

我们可以用一个二维数组 $f1[N][2]$ 记录点 $1$ 在每一次操作 1 后的坐标，初始值 $f1[0] = \{1,0\}$ ，对于其他点 $i$ 的坐标直接递推点 $i-1$ 在上一次操作后的坐标即可。

用 $f_{i,j}$ 代表点 $i$ 在经过第 $j$ 次操作 1 后的坐标：

f_{i,j}=f_{i-1,j-1}

递推终止的条件是 $f_{1,j}=f1[j]$ 和 $f_{i,0}=\{i,0\}$ 。

代码：

//point为结构体，存储x和y两个信息
point f(int i,int op){    //第i个点在第op次操作后的坐标
    if(i==1)	return f1[op][0];
    else if(op==0)	return (point){i,0};
    else	return f(i-1,op-1);
}

方法 $3$ ： $\mathcal {O}(1)$ ，递推优化

其实本题的递推压根就用不着那么多的状态，真正会被用到的状态只有点 $1$ 当前的坐标和每个点的初始坐标两种，方法 $2$ 耗时太久的原因就是一步一步从 $i-1,j-1$ 的转移太慢。

优化方法很好想，当 $i>j$ 时，递推最终会转移到 $f_{i-j,0}$ 处，而点 $i-j$ 的坐标就是 $(i-j,0)$ ；

当 $i\leq j$ 时，递推最终会转移到 $f_{1,j-(i-1)}$ 处，所以直接查询 $f1$ 数组里点 $1$ 在第 $j-(i-1)$ 次操作后的坐标即可。

代码

map<char,int> dx = {{'L',-1},{'R',1}};    //map默认值为0
map<char,int> dy = {{'U',1},{'D',-1}};

struct point{
    int x,y;
}f1[200005];

void solve() {
    int n,q;cin>>n>>q;
    int cnt = 0;    //操作1的次数
    f1[0].x = 1,f1[0].y = 0;  //点1初始坐标为(1,0)
    for(int i=1;i<=q;i++){
        int op;cin>>op;
        if(op==1){
            char d;cin>>d;
            cnt++;f1[cnt].x = f1[cnt-1].x+dx[d];f1[cnt].y = f1[cnt-1].y+dy[d];  //更新点1此时的坐标
        }
        else if(op==2){
            int x;cin>>x;
            if(x>cnt)   cout<<x-cnt<<" "<<0<<"\n";
            else    cout<<f1[cnt-(x-1)].x<<" "<<f1[cnt-(x-1)].y<<"\n";
        }
    }
}