[ARC039C] 幼稚園児高橋君 题解

· · 题解

牛马链表题，相信做完之后你一定会跟我一样神清气爽。

思路

题目叙述的比较清楚了，相当于我们往一个方向走时，要维护这个方向上第一个没有走过的点。考虑暴力，直接 for 循环往要走的方向一直走，时间复杂度 O(n^2)，肯定过不去。

考虑进行优化。先考虑水平方向上走（竖直方向上同理），我们会发现若一段连续的点 (i,j),(i+1,j),(i+2,j),(i+3,j)\cdots(i+k-1,j),(i+k,j) 都被走过，那么只有 (i,j),(i+k,j) 这两个点有用。因为我们不可能走到已经走过的点上，所以我们在左右走动时，不可能直接跳过 (i,j) 或 (i+k,j) 去走到它们中间的点。所以我们考虑在水平方向上维护两个链表，分别记录点 (i,j) 左边第一个没走过的点的右边那个点和右边第一个没走过的点的左边那个点（相当于该区间的左右端点），移动时更改答案坐标并加入当前点就好了（竖直方向上同理维护两个链表）。

注意，有个坑点：

我们假设加入当前点，且正在维护它的左边区间左端点，那么它的右边区间右端点的左端点可能也会更新。相当于没加入它之前，左区间和右区间分开，加入之后两个区间合并到一起，自然要维护。

代码实现

这里采用二维 map，时间复杂度 O(n \log ^ 2 n)，但是跑得还挺快？（雾）

其实可以用一维 map，具体实现不再赘述，复杂度少个 \log。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define re register

using namespace std;
const int N=2e5+10;
int n,len,x,y;
string s;
map < int ,map<int,int> > hl,hr,hu,hd,f; 

inline int read(){char cr=getchar();int x_=0,fui=1;while(cr<48){if(cr=='-')fui=-1;cr=getchar();}while(cr>47)x_=(x_*10)+(cr^48),cr=getchar();return x_*fui;}
inline void mwrite(int aq){if(aq>9)mwrite(aq/10);putchar((aq%10)|48);}
inline void write(int af,char cr){mwrite(af<0?(putchar('-'),af=-af):af);putchar(cr);}

inline void add(int x,int y)
{
    f[x+N][y+N]=1;
    if(!f[x-1+N][y+N]) hl[x+N][y+N]=x+N;
    else 
    {
        hl[x+N][y+N]=hl[x-1+N][y+N];
        if(!f[x+1+N][y+N])
        hr[hl[x-1+N][y+N]][y+N]=x+N;
        else
        hr[hl[x-1+N][y+N]][y+N]=hr[x+1+N][y+N];
    }
    if(!f[x+1+N][y+N]) hr[x+N][y+N]=x+N;
    else 
    {
        hr[x+N][y+N]=hr[x+1+N][y+N];
        if(!f[x-1+N][y+N])
        hl[hr[x+1+N][y+N]][y+N]=x+N;
        else
        hl[hr[x+1+N][y+N]][y+N]=hl[x-1+N][y+N];
    }
    if(!f[x+N][y-1+N]) hd[x+N][y+N]=y+N;
    else 
    {
        hd[x+N][y+N]=hd[x+N][y-1+N];
        if(!f[x+N][y+1+N])
        hu[x+N][hd[x+N][y-1+N]]=y+N;
        else 
        hu[x+N][hd[x+N][y-1+N]]=hu[x+N][y+1+N];
    }
    if(!f[x+N][y+1+N]) hu[x+N][y+N]=y+N;
    else 
    {
        hu[x+N][y+N]=hu[x+N][y+1+N];
        if(!f[x+N][y-1+N])
        hd[x+N][hu[x+N][y+1+N]]=y+N;
        else
        hd[x+N][hu[x+N][y+1+N]]=hd[x+N][y-1+N];
    }
}
inline int go_left(int x,int y)
{
    int nw;
    if(!f[x-1+N][y+N]) 
    {
        hl[x+N][y+N]=x-1+N;
        nw=x+N;
    }
    else
    {
        nw=hl[x+N][y+N]=hl[x-1+N][y+N];
    }
    return nw;
}
inline int go_rignt(int x,int y)
{
    int nw;
    if(!f[x+1+N][y+N]) 
    {
        hr[x+N][y+N]=x+1+N;
        nw=x+N; 
    }
    else
    {
        nw=hr[x+N][y+N]=hr[x+1+N][y+N];
    }
    return nw;
}
inline int go_down(int x,int y)
{
    int nw;
    if(!f[x+N][y-1+N]) 
    {
        hd[x+N][y+N]=y-1+N;
        nw=y+N;
    }
    else
    {
        nw=hd[x+N][y+N]=hd[x+N][y-1+N];
    }
    return nw;
}
inline int go_up(int x,int y)
{
    int nw;
    if(!f[x+N][y+1+N]) 
    {
        hu[x+N][y+N]=y+1+N;
        nw=y+N;
    }
    else
    {
        nw=hu[x+N][y+N]=hu[x+N][y+1+N];
    }
    return nw;
}
signed main() 
{
    n=read();
    cin>>s;
    len=s.length();
    f[N][N]=1;
    hl[N][N]=N,hr[N][N]=N,hu[N][N]=N,hd[N][N]=N;
    for(re int i=0;i<len;++i)
    {
        if(s[i]=='L') x=go_left(x,y)-N-1;
        if(s[i]=='R') x=go_rignt(x,y)-N+1;
        if(s[i]=='U') y=go_up(x,y)-N+1;
        if(s[i]=='D') y=go_down(x,y)-N-1;
        if(!f[x+N][y+N]) add(x,y);
    }
    write(x,' '),write(y,'\n');
    return 0;
}