Wandering Robot

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $k$ ( $1 \le n \le 10^5, 1 \le k \le 10^9$ ), indicating the length of the basic instruction sequence and the repeating parameter.

The second line contains a string $A = a_1a_2\dots a_n$ ( $|A| = n$ , $a_i \in \{\text{'L'},\text{'R'},\text{'U'},\text{'D'}\}$ ), where $a_i$ indicates the $i$ -th instruction in the basic instriction sequence.

It's guaranteed that the sum of $|A|$ of all test cases will not exceed $2 \times 10^6$ .

pypy3 解法, 执行用时: 454ms, 内存消耗: 30192K, 提交时间: 2022-04-03 10:06:44

t = int(input())
while t:
    t -= 1
    n, k = map(int, input().split())
    s = input()
    ans = 0
    x, y = 0, 0
    for i in s:
        if i == 'U':
            y += 1
        if i == 'D':
            y -= 1
        if i == 'L':
            x -= 1
        if i == 'R':
            x += 1
        ans = max(ans, abs(x)+abs(y))
    x = x*(k-1)
    y = y*(k-1)
    for i in s:
        if i == 'U':
            y += 1
        if i == 'D':
            y -= 1
        if i == 'L':
            x -= 1
        if i == 'R':
            x += 1
        ans = max(ans, abs(x)+abs(y))
    print(ans)

C++ 解法, 执行用时: 53ms, 内存消耗: 800K, 提交时间: 2022-06-18 20:41:47

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T,n,k,x,y,l,s;
string S;

int main(){
	int i;
	cin>>T;
	while(T--){
		cin>>n>>k;
		cin>>S;
		x=y=s=0;
		for(i=0;i<n;i++){
			if(S[i]=='U')y++;
			else if(S[i]=='D')y--;
			else if(S[i]=='L')x--;
			else if(S[i]=='R')x++;
			l=abs(x)+abs(y);
			s=max(s,l); 
		}
		x*=(k-1),y*=(k-1);
		for(i=0;i<n;i++){
			if(S[i]=='U')y++;
			else if(S[i]=='D')y--;
			else if(S[i]=='L')x--;
			else if(S[i]=='R')x++;
			l=abs(x)+abs(y);
			s=max(s,l); 
		}
		cout<<s<<endl;
	}
}

详情