题解：P14044 [SDCPC 2019] Wandering Robot

zhz_cptbtptp · 2025-09-24 21:40:27 · 题解

题意：这道题的意思就是循环 k 次的长度为 n 的指令，求它的最大曼哈顿距离。

解题：我们很容易可以看出每一次循环是在它的上一次循环的位置做出改变的，并且每一次的改变相同。所以我们只需要求出第一次循环机器人与原点的最大曼哈顿距离，乘上 k 即可求出总的最大曼哈顿距离。

详细代码：

#include<bits/stdc++.h>
#define int long long//不开long long见祖宗
using namespace std;
const int maxn=1e5+5;
struct point{//存第一次循环机器人的坐标
    int x,y;
}e[maxn];

int t;

void sol(){
    int n,k,x,y,ans;
    cin>>n>>k;
    x=0,y=0,ans=0;//多测不清零，爆零两行泪
    for(int i=1;i<=n;i++){
        char c;
        cin>>c;
        if(c=='U') y++;
        if(c=='D') y--;
        if(c=='L') x--;
        if(c=='R') x++;
        ans=max(ans,abs(x)+abs(y));//统计第一次循环最大的曼哈顿距离
        e[i].x=x,e[i].y=y;
    }
    for(int i=1;i<=n;i++){
        ans=max(ans,abs((k-1)*x+e[i].x)+abs((k-1)*y+e[i].y));//第一次已经循环过了，所以k-1
    }
    cout<<ans<<'\n';
}

signed main(){
    cin>>t;
    while(t--){
        sol();
    }
    return 0;
}