最近在清AtCoder的Beginner Contest的水题的时候刷到了一道蛮有意思的水题,也因为经验不够被这道题卡了不少时间,于是想要把自己的思路与做法记录一下。

题意

大致就是模拟一下坐标,然后求走过的坐标是否有重叠,如果有输出Yes,没有就输出No.要注意的是初始坐标与最后一个坐标也要判断。

思路过程

乍一看,好像是随随便便就能秒的题目。
看起来整个题目要做的,就是模拟高桥君走过的坐标,然后遍历坐标,如果遍历到了重复的坐标就输出Yes,没有的话就输出No.
很天真的我就这么干了,于是被鸽子狠狠踢了。
再仔细看看题目,数据的范围是$1≤N≤2×10^{5}$,欸不对啊,如果暴力遍历的话是绝对会TLE的。
随后选择了开结构体,开自定义sort对坐标进行排序,之后一个一个在前后去进行比较,这样时间复杂度就能够得到大大的降低。
然后过了,下面忘了

上代码

#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=200001;
int cnt;
char inst[MAXN];

struct path
{
    int x,y;
}p[MAXN]={0};

bool cmp(path a, path b)
{
    if (a.x != b.x)
    {
        return a.x < b.x;
    }
    return a.y < b.y;
}

int main()
{
    cin >> cnt;
    for (int i=1; i<=cnt; i++)
    {
        cin >> inst[i];
    }
    for (int i=1; i<=cnt; i++)
    {
        p[i].x=p[i-1].x;
        p[i].y=p[i-1].y;
        if(inst[i]=='R')
        {
            p[i].x++;
        }
        else if(inst[i]=='L')
        {
            p[i].x--;
        }
        else if(inst[i]=='U')
        {
            p[i].y++;
        }
        else if(inst[i]=='D')
        {
            p[i].y--;
        }
    }
    sort(p,p+cnt+1,cmp);
    for (int i=1; i<=cnt; i++)
    {
        if (p[i].x==p[i-1].x&&p[i].y==p[i-1].y)
        {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}