最近在清AtCoder的Beginner Contest的水题的时候刷到了一道蛮有意思的水题，也因为经验不够被这道题卡了不少时间，于是想要把自己的思路与做法记录一下。
题意
大致就是模拟一下坐标，然后求走过的坐标是否有重叠，如果有输出Yes，没有就输出No.要注意的是初始坐标与最后一个坐标也要判断。
思路过程
乍一看，好像是随随便便就能秒的题目。
看起来整个题目要做的，就是模拟高桥君走过的坐标，然后遍历坐标，如果遍历到了重复的坐标就输出Yes，没有的话就输出No.
很天真的我就这么干了，于是被鸽子狠狠踢了。
再仔细看看题目，数据的范围是$1≤N≤2×10^{5}$，欸不对啊，如果暴力遍历的话是绝对会TLE的。
随后选择了开结构体，开自定义sort对坐标进行排序，之后一个一个在前后去进行比较，这样时间复杂度就能够得到大大的降低。
然后过了，下面忘了
上代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
#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;
}
|