专栏文章

题解：P14044 [SDCPC 2019] Wandering Robot

AAA12_G
P14044题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minvmf7g
此快照首次捕获于
2025/12/02 09:05
3 个月前
此快照最后确认于
2025/12/02 09:05
3 个月前
查看原文

思路

仅需计算第一次和最后一次。
最后一次是因为每次会对上一次产生一个相对偏移，最后一次是偏移最远的。
第一次是因为这个数据：
CPP
1
17 2
LLLLLLLDRRRRRRRRU
答案是 88（在第一次运行到 D），但是算最后一次，就是 77。
原因：第一次可能存在一个点，与后续偏移方向相反，它是答案，但是不会被计算。中间的可以证明不存在这样的。

代码

需要开 long long！！！！
CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
void mian()
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int x = 0, y = 0;
    int ans = 0;
    for (int i = 1; i <= n; i ++)
    {
        if (s[i - 1] == 'U') y ++;
        else if (s[i - 1] == 'D') y --;
        else if (s[i - 1] == 'L') x --;
        else if (s[i - 1]) x ++;
        ans = max (ans, abs (x) + abs(y));
    }
    x = x * (k - 1), y = y * (k - 1);
    for (int i = 1; i <= n; i ++)
    {
        if (s[i - 1] == 'U') y ++;
        else if (s[i - 1] == 'D') y --;
        else if (s[i - 1] == 'L') x --;
        else if (s[i - 1]) x ++;
        ans = max (ans, abs (x) + abs(y));
    }
    cout << ans << endl;
}
signed main(){
    int T;
    cin >> T;
    while (T --) mian();
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...