列表

详情

NC207701. Badeline

描述

Madeline来到了旧址（旧址是这一关卡的名字），患有抑郁症的Madeline臆想出了另一个自己Badeline，这个另一个自己正要阻止Madeline登上Celeste山。

在旧址中，Madeline被Badeline追着，如果Madeline与Badeline在某个时间点在同一个位置相当于Madeline登山失败。

为了简化模型，Madeline和Badeline在一个无限大的二维的坐标系内。一开始Madeline在某个位置，然后Madeline在接下来的秒钟内向四个方向移动或者不动，这四个方向分别是上下左右四个方向。如果在这第秒到第秒内Madeline与Badeline在任何一个时间点都没有在同一个位置就相当于成功通过旧址。

如果Madeline此时的坐标是，向上移动则下一秒的位置是在，向下移动则下一秒的位置是在，向左移动则下一秒的位置是在，向右移动则下一秒的位置是在，不动则下一秒的位置是在。

Badeline在第秒时的位置是Madeline在第秒时的位置。而第秒到第秒内Badeline不在任何位置上，即第秒到第秒内Madeline与Badeline不会在同一个位置。在第秒时Badeline在Madeline第秒时的位置。

现在给定Madeline在第秒到第秒内的移动，Madeline想让你判断一下这样移动的话会不会登山失败。

输入描述

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

输出描述

如果登山失败则输出no。
否则输出yes。

示例1

输入: 

2 1
LR

输出: 

yes

原站题解

import java.util.Scanner;
public class Main {
public static void main(String[] arg) {
Scanner scanner = new Scanner(System.in);
// todo
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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")

上一题

© 2025 nowcoder.com