Badeline

只有一组输入样例。
输入第一行有两个整数 ${ n }$ ， ${ k }$ ，意义见题目描述。（ $1\le n\le 300000, 1\le k \le 200000$ ）
输入第二行是一个字符串 ${ s }$ ， $s_i$ 表示这n秒钟内的移动方向。U表示向上移动，D表示向下移动，L表示向左移动，R表示向右移动，S表示不动。字符串 ${ s }$ 的长度为 ${n }$ ，且只会出现这五种字符。

C++14(g++5.4) 解法, 执行用时: 14ms, 内存消耗: 896K, 提交时间: 2020-07-18 14:03:53

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t,k;
	cin >> t >> k;
	int f=1,t1=0,x=0,y=0,xk=0,yk=0,j=0;
	string m;
	cin >> m;
	for(int i=0;i<t;i++)
	{
		if(m[i]=='U')y++;
		else if(m[i]=='D')y--;
		else if(m[i]=='L')x--;
		else if(m[i]=='R')x++;
		if(k<i+1){
			if(m[j]=='U')yk++;
			else if(m[j]=='D')yk--;
			else if(m[j]=='L')xk--;
			else if(m[j]=='R')xk++;
			j++;
			if(x==xk && y==yk){
				f=0;
				break;
			}
		}
		if(f==0)break;
	}
	if(f==1)printf("yes");
	else printf("no");
 }

C++ 解法, 执行用时: 14ms, 内存消耗: 3108K, 提交时间: 2022-03-02 11:38:31

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,k;
string s;
pair<int,int> p[N];
int main()
{
	int x=0,y=0;
	cin>>n>>k>>s;
	for(int i=0;i<s.length();i++)
	{
		if(s[i]=='L')x--;
		if(s[i]=='R')x++;
		if(s[i]=='D')y--;
		if(s[i]=='U')y++;
		p[i]=make_pair(x,y);
		if(i>=k&&p[i]==p[i-k])
		{
			cout<<"no"<<endl;
			return 0;
		}
	}
	cout<<"yes"<<endl;
	return 0;
}

pypy3(pypy3.6.1) 解法, 执行用时: 177ms, 内存消耗: 41268K, 提交时间: 2020-07-18 13:44:07

n,k=input().split()
n=int(n)
k=int(k)
s=input()
d=[]
x=0
y=0
f=1
for i in range(n):
    if s[i]=='U':
        x+=1
    elif s[i]=='D':
        x-=1
    elif s[i]=='L':
        y+=1
    elif s[i]=='R':
        y-=1
    d.append(str(x)+"+"+str(y))
    if i>=k and d[i]==d[i-k]:
        f=0
if f:
    print("yes")
else:
    print("no")

详情