D. Ingenuity-2 - 题解

比赛与标签

比赛: Codeforces Round 946 (Div. 3) 标签: constructive algorithms, greedy, implementation 难度: *1400

喵喵，这是什么任务呀？

各位开拓者们，下午好喵~！今天我们接到了一个来自火星的有趣任务！

想象一下，我们的小漫游车（Rover）和小直升机（Helicopter）都乖乖地待在坐标 (0, 0)。我们手上有一串指令 s，包含了 N (北), S (南), E (东), W (西) 四种移动。我们的任务是，把每一个指令分配给小漫游车（R）或者小直升机（H），让它们在执行完所有指令后，能够在同一个地点相会。

有两个小小的要求哦：

每个指令都必须被执行，不多不少。
漫游车和直升机都必须至少执行一个指令，不能有谁在原地偷懒的说！

如果能做到，我们就输出一个由 'R' 和 'H' 组成的分配方案；如果无论如何都做不到，就告诉指挥中心 "NO"，呐。

本喵的思考过程~

这是一个构造题，目标是找到一个可行的分配方案。当我们遇到这种问题时，可以先从“终点相同”这个最关键的条件入手，看看能发现什么秘密，喵~

终点相同的秘密喵~

假设所有指令执行完后，漫游车（R）的坐标是 (x_R, y_R)，直升机（H）的坐标是 (x_H, y_H)。我们希望它们相会，也就是 x_R = x_H 并且 y_R = y_H。

我们再来看看所有指令的总位移。如果只有一个设备执行所有指令，它会移动多少呢？

水平总位移 dx_total = (E的数量) - (W的数量)
垂直总位移 dy_total = (N的数量) - (S的数量)

因为每个指令要么给R要么给H，所以它们俩的位移加起来，一定等于总位移。也就是说： x_R + x_H = dx_totaly_R + y_H = dy_total

结合我们想要的 x_R = x_H 和 y_R = y_H，代入上面的式子，就会得到： 2 * x_R = dx_total2 * y_R = dy_total

哇！发现了不得了的事情！这意味着 dx_total 和 dy_total 都必须是偶数！如果其中任何一个是奇数，那就不可能找到一个整数坐标 (x_R, y_R) 让它们相遇了。

奇偶性大法！

所以，我们的第一步，也是最重要的一步，就是进行奇偶性检查！

数出指令中 'N', 'S', 'E', 'W' 的数量。
计算 dy_total = count('N') - count('S') 和 dx_total = count('E') - count('W')。
如果 dy_total % 2 != 0 或者 dx_total % 2 != 0，那神仙也救不了啦，直接输出 "NO" 就好！

分类讨论，两种策略喵

通过了奇偶性检查，说明解是可能存在的。现在我们就来动手构造一个。本喵发现，根据总位移是否为零，可以分成两种情况来处理，这样思路会特别清晰呐！

情况一：总位移不为零

这是最常见的情况。我们已经知道总位移是偶数，所以漫游车和直升机最终都要到达 (dx_total / 2, dy_total / 2) 这个点。

一个非常优雅的贪心策略是：对于同一种类型的指令，轮流分配给 R 和 H。

比如，我们遇到第一个 'N' 给 R，第二个 'N' 给 H，第三个 'N' 又给 R……
对 'S', 'E', 'W' 也做同样的操作，它们各自有自己的分配顺序，互不干扰。

为什么这样可行呢？我们来分析一下垂直方向（N/S）：

因为 count('N') - count('S') 是偶数，所以 count('N') 和 count('S') 的奇偶性是相同的（同为奇数或同为偶数）。
轮流分配会给 R ceil(count('N')/2) 个 'N' 指令和 ceil(count('S')/2) 个 'S' 指令。
H 则会得到 floor(count('N')/2) 个 'N' 和 floor(count('S')/2) 个 'S'。
由于 count('N') 和 count('S') 奇偶性相同，ceil(cN/2) - ceil(cS/2) 的结果会和 floor(cN/2) - floor(cS/2) 完全一样！不信可以自己试试看哦~
所以它们的垂直位移 y_R 和 y_H 必然相等！水平方向同理。
只要总指令数 n >= 2，这个策略基本能保证 R 和 H 都分到指令。

情况二：总位移为零

这种情况比较特殊，count('N') == count('S') 并且 count('E') == count('W')。这意味着 R 和 H 最终都要回到原点 (0, 0)。

这时候，上面的轮流分配策略会遇到一个小麻烦。比如指令是 NS (n=2)。轮流分配会把 'N' 和 'S' 都给 R，H 就没活干了，这不符合“都要动”的规则。所以对于 n=2 且是 NS 或 EW 这种相反指令对的情况，是无解的，要输出 "NO"。

对于其他总位移为零的情况（比如 n > 2），我们可以用一个更稳妥的办法：

让漫游车 R 领走一对相反的指令，比如第一个 'N' 和第一个 'S'。这样 R 移动了一下又回来了，最终位移是0。
剩下的所有 n-2 个指令全都丢给直升机 H。因为剩下的指令也是南北、东西数量配对的，所以 H 的最终位移也是0。
这样 R 动了2次，H 动了 n-2 次（只要 n>2 就肯定动了），都回到了原点，完美达成任务！
如果指令里没有 N/S 对，那就用 E/W 对，效果是一样的。

总结一下，我们的思路就是：先用奇偶性大法排除无解情况，然后根据总位移是否为零，采用不同的构造策略。是不是很简单呢？喵~

看本喵的代码魔法！

cpp

#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <cmath>

void solve() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    // 步骤1: 统计每种指令的数量
    int countN = 0, countS = 0, countE = 0, countW = 0;
    for (char c : s) {
        if (c == 'N') countN++;
        else if (c == 'S') countS++;
        else if (c == 'E') countE++;
        else if (c == 'W') countW++;
    }

    // 步骤2: 进行奇偶性检查，这是必须满足的条件！
    if (std::abs(countN - countS) % 2 != 0 || std::abs(countE - countW) % 2 != 0) {
        std::cout << "NO\n";
        return;
    }

    // 步骤3: 分类讨论来构造解
    // 情况一: 总位移为零
    if (countN - countS == 0 && countE - countW == 0) {
        // 特殊情况: n=2 且是 NS 或 EW，一方必须拿走所有指令，导致另一方不动，无解
        if (n == 2 && (countN > 0 || countE > 0)) {
            std::cout << "NO\n";
            return;
        }
        
        // 通用解法: 给漫游车R一对相反的指令，其余给直升机H
        // 这样可以保证R和H都移动了 (只要n>2)，且最终都回到原点
        std::string p(n, 'H'); // 默认所有指令都给直升机
        if (countN > 0) { // 优先分配 N/S 对
            int n_idx = -1, s_idx = -1;
            for(int i=0; i<n; ++i) {
                if (s[i] == 'N' && n_idx == -1) n_idx = i;
                if (s[i] == 'S' && s_idx == -1) s_idx = i;
            }
            p[n_idx] = 'R';
            p[s_idx] = 'R';
        } else if (countE > 0) { // 如果没有 N/S 对，就用 E/W 对
            int e_idx = -1, w_idx = -1;
            for(int i=0; i<n; ++i) {
                if (s[i] == 'E' && e_idx == -1) e_idx = i;
                if (s[i] == 'W' && w_idx == -1) w_idx = i;
            }
            p[e_idx] = 'R';
            p[w_idx] = 'R';
        }
        // 因为 countN=countS, countE=countW, 且 n>=1,
        // 所以一定存在至少一对相反的指令 (除非n=0, 但题目保证n>=1)
        std::cout << p << "\n";
    } else {
        // 情况二: 总位移不为零 (但分量都是偶数)
        // 使用轮流分配策略
        std::string p(n, ' ');
        bool n_is_R = true, s_is_R = true, e_is_R = true, w_is_R = true;
        for (int i = 0; i < n; ++i) {
            if (s[i] == 'N') {
                p[i] = (n_is_R ? 'R' : 'H');
                n_is_R = !n_is_R; // 下一个'N'给另一个人
            } else if (s[i] == 'S') {
                p[i] = (s_is_R ? 'R' : 'H');
                s_is_R = !s_is_R;
            } else if (s[i] == 'E') {
                p[i] = (e_is_R ? 'R' : 'H');
                e_is_R = !e_is_R;
            } else if (s[i] == 'W') {
                p[i] = (w_is_R ? 'R' : 'H');
                w_is_R = !w_is_R;
            }
        }
        std::cout << p << "\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

跑得快不快呀？

时间复杂度: O(n) 的说。对于每个测试用例，我们最多需要遍历指令字符串 s 两次：一次是计数，一次是生成结果字符串。所以总的时间和字符串长度 n 是线性关系，非常高效！
空间复杂度: O(n) 的说。我们需要一个长度为 n 的字符串 p 来存储我们的答案，所以空间开销也是线性的。

这次探险的宝藏~

这次解题就像一次寻宝探险，我们收获了不少好东西呐！

从约束反推性质: "终点相同"这个约束直接导出了“总位移分量必须为偶数”这个超强的性质。这是解决构造题的经典思路！先找到必要条件，能帮你过滤掉大量无解的情况。
分类讨论大法好: 当一个策略不能完美解决所有情况时，不要灰心！看看能不能根据问题的某些特征（比如这里的总位移是否为零）把问题分解成几个子问题，然后逐一击破。
注意边界条件: “每个设备至少移动一次”这个小小的要求，正是区分普通情况和特殊情况（比如 n=2, s="NS"）的关键。永远不要小看这些不起眼的角落，它们往往是AC路上的陷阱喵！

希望本喵的这篇题解能帮到大家！如果还有不明白的地方，随时可以来问哦~ 祝大家刷题愉快，多多AC！喵~

D. Ingenuity-2 - 题解 ​

比赛与标签 ​

喵喵，这是什么任务呀？ ​

本喵的思考过程~ ​

终点相同的秘密喵~ ​

奇偶性大法！ ​

分类讨论，两种策略喵 ​

情况一：总位移不为零 ​

情况二：总位移为零 ​

看本喵的代码魔法！ ​

跑得快不快呀？ ​

这次探险的宝藏~ ​