D. Colorful Stamp - 题解

比赛与标签

比赛: Codeforces Round 784 (Div. 4) 标签: implementation 难度: *1100

喵喵，题目在说什么呀？

哈喵~！各位算法大师们好呀！今天我们来解决一个超级有趣的染色问题，就像给一排小方块涂上漂亮的颜色一样，喵~

题目是这样子的：我们有一排 n 个白色的小格子。我们有一个神奇的印章，每次可以盖在相邻的两个格子上，把一个染成红色（R），另一个染成蓝色（B）。这个印章可以旋转哦，所以你可以盖出 RB，也可以盖出 BR 的图案。

我们可以随便使用这个印章，也可以在同一个地方盖很多次，每次都会把原来的颜色覆盖掉。现在，题目会给我们一个最终的颜色排列（由 W, R, B 组成的字符串），然后问我们，这个最终的图案能不能通过我们的印章从全白的状态变过来呢？

简单来说，就是：

输入: 一个由 'W', 'R', 'B' 组成的字符串。
目标: 判断这个字符串是否能通过 RB 或 BR 印章从全白字符串 WW...W 变来。
输出: 如果可以，就输出 "YES"，不然就输出 "NO"，的说！

猫猫的思考时间！

这个问题看起来有点复杂，但只要我们抓住关键点，它就会像毛线球一样被我们轻松解开，喵~

首先，我们来想想白色格子 'W' 的特殊性。印章只会产生红色 'R' 和蓝色 'B'，对吧？这意味着，一旦一个格子被染上了颜色，它就再也变不回白色 'W' 了！所以，如果最终的图案里有 'W'，那说明这个格子从始至终都没有被印章盖过，它一直是纯洁的白色，呐。

这真是个惊人的发现！这意味着什么呢？这意味着 'W' 就像一堵墙，把整排格子分成了好几个互不相干的小段！ 每一段都只包含 'R' 和 'B'。我们可以独立地判断每一段是否可以被“画”出来。只要所有的小段都满足条件，整个图案就满足条件啦！

比如说，如果最终图案是 BRBWWRB，'W' 就把它分成了 BRB 和 RB 这两个小段。我们只需要分别检查 BRB 和 RB 是否合法就行了。

那么，一个只包含 'R' 和 'B' 的小段，要满足什么条件才算合法呢？我们再来分析一下印章的性质：

印章大小为2：每次操作都必须影响两个相邻的格子。这意味着我们不可能只给一个格子染色。所以，如果一个 'R' 'B' 小段的长度只有 1（比如 "R" 或者 "B"），那它肯定是无法形成的！这种情况直接判 "NO"，喵！
印章产生一红一蓝：每次盖章，都会同时产生一个 'R' 和一个 'B'。这意味着在一个独立的小段里，我们不可能只创造出一种颜色。想要有红色，就必须有蓝色作伴；想要有蓝色，也必须有红色作伴。所以，如果一个 'R' 'B' 小段里只有 'R' 或者只有 'B'（比如 "RRR" 或者 "BB"），那也是绝对不可能的！这种情况也要判 "NO"。

总结一下我们的策略，就像猫猫抓老鼠一样清晰：

分割：用 'W' 作为分隔符，把整个字符串切成若干个只包含 'R' 和 'B' 的小段。
检查：对每一个小段进行检查：
- 它的长度是不是大于1？
- 它是不是同时包含了 'R' 和 'B' 两种颜色？
判断：如果所有的小段都通过了检查，那么答案就是 "YES"。只要有一个小段不合格，那整个图案就是不可能的，答案就是 "NO"！

是不是很简单呀？让我们用这个思路来写代码吧！

让代码动起来喵！

下面就是根据我们的思路写出的AC代码啦！我已经加上了详细的注释，方便大家理解每一行都在做什么哦~

cpp

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    int t;
    cin >> t; // 读取测试用例的数量
    while (t--) {
        int n;
        cin >> n; // 读取字符串长度
        string s;
        cin >> s; // 读取最终的颜色字符串

        vector<string> segments; // 用来存放被 'W' 分割开的 'R' 'B' 小段
        string cur = ""; // 当前正在构建的小段

        // 第一步：分割字符串
        for (int i = 0; i < n; i++) {
            if (s[i] == 'W') { // 如果遇到 'W'
                if (!cur.empty()) { // 如果当前小段不为空
                    segments.push_back(cur); // 就把它存起来
                    cur = ""; // 然后清空，准备开始新的小段
                }
            } else { // 如果是 'R' 或 'B'
                cur += s[i]; // 就把它加到当前小段的末尾
            }
        }
        // 循环结束后，如果最后一段不是以 'W' 结尾，cur里可能还有内容
        if (!cur.empty()) {
            segments.push_back(cur);
        }

        bool valid = true; // 一个标志，假设初始情况是合法的
        // 第二步：检查每一个小段
        for (string seg : segments) {
            // 条件1：小段长度必须大于1
            if (seg.size() == 1) {
                valid = false; // 不合法！
                break; // 直接跳出循环，因为已经确定答案是 "NO"
            }
            
            // 条件2：小段必须同时包含 'R' 和 'B'
            bool hasR = false, hasB = false;
            for (char c : seg) {
                if (c == 'R') hasR = true;
                else if (c == 'B') hasB = true;
            }
            
            if (!hasR || !hasB) { // 如果缺少 'R' 或者缺少 'B'
                valid = false; // 同样不合法！
                break; // 提前结束
            }
        }

        // 第三步：输出最终结果
        if (valid) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}

跑得快不快呀？

时间复杂度: O(N) 的说。其中 N 是字符串的总长度（所有测试用例的 n 之和）。我们只需要遍历字符串一次来分割它，然后再遍历所有小段的字符一次来检查它们。每个字符最多被访问常数次，所以总的时间是线性的，跑得飞快，喵~！
空间复杂度: O(N) 的说。在最坏的情况下，如果整个字符串都没有 'W'，我们的 segments 向量会存储一个长度为 N 的字符串，所以空间复杂度和输入规模成正比。

温故知新，喵~

通过这道题，我们又学到了一些宝贵的经验呢！

分治思想 (Divide and Conquer)：这道题最核心的思想就是发现了 'W' 的“分隔符”作用，从而把一个大问题分解成了许多独立的小问题。在算法竞赛中，找到这种可以简化问题的“分割点”是非常重要的一步哦！
从操作性质推导约束条件：我们仔细分析了印章的两个性质（大小为2，产生一红一蓝），并从中推导出了一个合法子段必须满足的两个条件。这是解决构造类和判断类问题的常用技巧，从根源出发，找到问题的本质约束。
字符串处理技巧：代码中按分隔符切分字符串的逻辑是一个非常实用的编程模式。虽然简单，但在很多问题中都会用到。注意处理好边界情况，比如字符串开头、结尾或者连续出现分隔符的情况。

希望这篇题解能帮到你！如果还有不懂的地方，随时可以再来问我哦！一起努力，变得更强，喵~！

D. Colorful Stamp - 题解 ​

比赛与标签 ​

喵喵，题目在说什么呀？ ​

猫猫的思考时间！ ​

让代码动起来喵！ ​

跑得快不快呀？ ​

温故知新，喵~ ​