题目描述

难度分:$1400$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的字符串$s$，只包含NSEW四种字母，表示北南东西四个方向。

有两个机器人，一开始都在坐标原点。选择$s$中的某些字母分配给第一个机器人，其余字母分配给第二个机器人。机器人按照字母方向移动，一个字母移动一个单位长度。如何分配字母，可以让两个机器人最终在同一个位置？

注意：两个机器人都至少要走一步。

输出一个长为$n$的字符串$t$，其中$t[i]=$R 表示$s[i]$分给了第一个机器人，$t[i]=$H表示$s[i]$分给了第二个机器人。

多解输出任意解。如果无法做到，输出NO。

输入样例

10
6
NENSNE
3
WWW
6
NESSWS
2
SN
2
WE
4
SSNN
4
WESN
2
SS
4
EWNN
4
WEWE

输出样例

RRHRRH
NO
HRRHRH
NO
NO
RHRH
RRHH
RH
RRRH
RRHH

算法

构造

设N会让纵坐标自增，S会让纵坐标自减，E会让横坐标自增，W会让横坐标自减。假设总共的横坐标偏移量是$dx$，纵坐标的偏移量为$dy$，要想两个机器人最终在同一个位置，那这两个偏移量都必须要可以均分，否则是做不到的。因此，$dx$和$dy$都应该是偶数。

接下来遍历$s$串，考虑在有解的情况下如何均分这两个偏移量，先考虑均分纵坐标偏移量$dy$。令两个机器人的纵坐标偏移量分别为$y_1$和$y_2$：

1. 如果遇到N，$y_1$和$y_2$谁小就把$s[i]$分配给谁。如果相等，规定第一次分配给R，之后交替分配。
2. 如果遇到S，$y_1$和$y_2$谁大就把$s[i]$分配给谁。如果相等，规定第一次分配给R，之后交替分配。

同理设两个机器人的横坐标偏移量分别为$x_1$和$x_2$，考虑分配横坐标的偏移量即可。最后还需要注意一下构建出来的答案串是否既有R又有H，不是的话也是无解。

复杂度分析

时间复杂度

最多遍历$3$次$s$串就可以构造出答案，因此时间复杂度是线性的，为$O(n)$。

空间复杂度

除了输入的$s$和答案串$ans$，仅使用了有限几个变量来统计几个字母的频数。因此，额外空间复杂度为$O(1)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int T;
    cin >> T;
    while(T--) {
        int n;
        string s;
        cin >> n >> s;
        unordered_map<char, int> counter;
        for(char c: s) {
            counter[c]++;
        }
        int dy = abs(counter['N'] - counter['S']);
        int dx = abs(counter['W'] - counter['E']);
        if(dy % 2 || dx % 2) {
            cout << "NO\n";
        }else {
            string ans(n, 'X');
            char pre = '*';
            int y1 = 0, y2 = 0, hcnt = 0, rcnt = 0;
            for(int i = 0; i < n; i++) {
                if(s[i] == 'N') {
                    if(y1 < y2) {
                        y1++;
                        ans[i] = 'R';
                        pre = 'R';
                        rcnt++;
                    }else if(y1 > y2) {
                        y2++;
                        ans[i] = 'H';
                        pre = 'H';
                        hcnt++;
                    }else {
                        if(pre == '*' || pre == 'H') {
                            ans[i] = 'R';
                            pre = 'R';
                            rcnt++, y1++;
                        }else {
                            ans[i] = 'H';
                            pre = 'H';
                            hcnt++, y2++;
                        }
                    }
                }
                if(s[i] == 'S') {
                    if(y1 < y2) {
                        y2--;
                        ans[i] = 'H';
                        pre = 'H';
                        hcnt++;
                    }else if(y1 > y2) {
                        y1--;
                        ans[i] = 'R';
                        pre = 'R';
                        rcnt++;
                    }else {
                        if(pre == '*' || pre == 'H') {
                            ans[i] = 'R';
                            pre = 'R';
                            rcnt++;
                            y1--;
                        }else {
                            ans[i] = 'H';
                            pre = 'H';
                            hcnt++, y2--;
                        }
                    }
                }
            }
            int x1 = 0, x2 = 0;
            for(int i = 0; i < n; i++) {
                if(s[i] == 'E') {
                    if(x1 < x2) {
                        x1++;
                        ans[i] = 'R';
                        pre = 'R';
                        rcnt++;
                    }else if(x1 > x2) {
                        x2++;
                        ans[i] = 'H';
                        pre = 'H';
                        hcnt++;
                    }else {
                        if(pre == '*' || pre == 'H') {
                            ans[i] = 'R';
                            pre = 'R';
                            rcnt++;
                            x1++;
                        }else {
                            ans[i] = 'H';
                            pre = 'H';
                            hcnt++;
                            x2++;
                        }
                    }
                }
                if(s[i] == 'W') {
                    if(x1 < x2) {
                        x2--;
                        ans[i] = 'H';
                        pre = 'H';
                        hcnt++;
                    }else if(x1 > x2) {
                        x1--;
                        ans[i] = 'R';
                        pre = 'R';
                        rcnt++;
                    }else {
                        if(pre == '*' || pre == 'H') {
                            ans[i] = 'R';
                            pre = 'R';
                            rcnt++;
                            x1--;
                        }else {
                            ans[i] = 'H';
                            pre = 'H';
                            hcnt++, x2--;
                        }
                    }
                }
            }
            if(rcnt == 0 || hcnt == 0) ans = "NO";
            cout << ans << endl;
        }
    }
    return 0;
}