Ingenuity-2

题面翻译

你有两个机器人，分别是 Rover (R) 和 Helicopter (H)。它们初始都在同一平面直角坐标系 \(xOy\) 的 \((0, 0)\) 处。定义北为 \(y\) 轴正方向，东为 \(x\) 轴正方向。

现有一串由以下四个字符指令组成的指令串 \(s\)：

• N 向北移动一步，即 \((x, y) \to (x, y + 1)\)；
• S 向南移动一步，即 \((x, y) \to (x, y - 1)\)；
• E 向东移动一步，即 \((x, y) \to (x + 1, y)\)；
• W 向西移动一步，即 \((x, y) \to (x - 1, y)\)；

问是否存在一种将每个指令都分配给两个机器人的方法，使得它们最终停在同一个位置？如果存在，给出一组构造；如果不存在，报告无解。

题目描述

Let's imagine the surface of Mars as an infinite coordinate plane. Initially, the rover Perseverance-2 and the helicopter Ingenuity-2 are located at the point with coordinates $ (0, 0) $ . A set of instructions $ s $ consisting of $ n $ instructions of the following types was specially developed for them:

• N: move one meter north (from point $ (x, y) $ to $ (x, y + 1) $ );
• S: move one meter south (from point $ (x, y) $ to $ (x, y - 1) $ );
• E: move one meter east (from point $ (x, y) $ to $ (x + 1, y) $ );
• W: move one meter west (from point $ (x, y) $ to $ (x - 1, y) $ ).

Each instruction must be executed either by the rover or by the helicopter. Moreover, each device must execute at least one instruction. Your task is to distribute the instructions in such a way that after executing all $ n $ instructions, the helicopter and the rover end up at the same point, or determine that this is impossible.

输入格式

The first line of input contains $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of instructions.

The second line of each test case contains a string $ s $ of length $ n $ consisting of the characters 'N', 'S', 'E', 'W' — the sequence of instructions.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10 ^ 5 $ .

输出格式

For each test case, if the required distribution of instructions exists, output a string $ p $ of length $ n $ consisting of the characters 'R', 'H'. If the $ i $ -th operation should be executed by the rover, then $ p_i=\text{R} $ , if the $ i $ -th operation should be executed by the helicopter, then $ p_i=\text{H} $ . If there are multiple solutions, output any of them.

Otherwise, output NO.

样例 #1

样例输入 #1

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

样例输出 #1

RRHRRH
NO
HRRHRH
NO
NO
RHRH
RRHH
RH
RRRH
RRHH

提示

Let's consider the first example: the string $ S = \texttt{NENSNE} $ . One of the possible solutions, shown in the figure below, is $ p = \texttt{RRHRRH} $ , using which both the rover and the helicopter will end up one meter north and one meter east.

For WWW, the solution is impossible.

AC_code

这里的思路是当前给1，则后1个肯定给2(同理依次)
此时若第一个多一个N则应有多一个S抵消(N==S)，由于每个机器人要至少给一条：则可以EW(相反与NS)先给2，再给1

#include <iostream>

using namespace std;

const int N = 2 * 1e5 + 10;

char ans[N], s[N];//公共串ans记录路径
int n, w[128];
void solve() 
{
    cin >> n >> s + 1;
    int ok = 0;

    //标记当前应分配给谁
    w['N'] = w['S'] = 0;
    w['W'] = w['E'] = 1;
    
    for(int i = 1; i <= n; ++ i) {
        ans[i] = w[s[i]] == 0 ? 'R' : 'H';
        // cout << i << ' '<< ans[i] << endl;
        //看是否有ok=3(至少12都接受过指令)
        if(ans[i] == 'R') ok |= 1;
        if(ans[i] == 'H') ok |= 2;
        w[s[i]] ^= 1;//0变1，1变0
    }
    //虽然新solve读入串会覆盖旧串，但下面puts输出ans所有的值(采用ans[n+1] = 0避免)
    ans[n + 1] = 0;
    if(ok == 3 && w['N'] == w['S'] && w['W'] == w['E'])
        puts(ans + 1);
    else 
        puts("No");
    return ;
}

int _;
int main()
{
    cin >> _;
    while(_ --) {
        solve();
    }
    return 0;
}

感觉发现性质和运用性质的能力一样重要
构造N == S，E == W即可，并且位运算在优化代码和构造中真的有很大的用处

本人思路

求除几种抵消操作后，是否可以构造出相同操作，抵消操作：NS上下，WE左右，以及NESW自转一圈

并错误的认为如果序列是奇数一定是"No"

发现有路径问题，这时采用的是枚举主要R的做法，先减去NESW转圈，再减去NS，EW抵消问题，想着后续处理路径，眼瞎忽略了至少HR各走一步限制，导致后续问题，并且后续处理路径也很容易夭折