哈喵~ 主人，欢迎来到我的题解小屋！今天我们要解决的是一道关于鼓点节奏的有趣问题呢。别担心，有本喵在，再复杂的问题也会变得简单起来的！我们这就开始吧！

题目大意

这道题是说呀，我们面前有两面鼓，一个在左边，一个在右边。敲一下左边的鼓记作 "L"，敲一下右边的鼓记作 "R"。

奇妙的是，每次敲击发出的声音次数不固定哦。敲一下左边的鼓（一个 "L"），可能会听到一声 "L"，也可能会听到两声 "LL"。同样，敲一下右边的鼓（一个 "R"），也可能产生 "R" 或 "RR" 的声音。

现在，我们有一串敲击序列 p 和一串听到的声音序列 s。主人需要判断，声音序列 s 是否可能由敲击序列 p 产生。

举个栗子：如果敲击 p = "LR"，那么可能产生的声音 s 就有 "LR", "LRR", "LLR", "LLRR" 这四种。但是像 "LLLR" 或者 "LRL" 这样的声音就不可能产生了。

题解方法

喵~ 仔细思考一下，虽然每次敲击产生的声音数量不确定，但有些东西是永远不会变的！

最重要的一点就是 顺序！如果敲击顺序是先敲了一堆左边的鼓，再敲了一堆右边的鼓，那么听到的声音也必须是先一堆 "L"，再一堆 "R"，这个先后顺序是不能乱的。比如 p = "LRLR"，声音就不可能是 "LLRR"，因为敲击是左右交替的，声音也必须是 "L" 和 "R" 交替出现才行。

这启发了我们一个绝妙的点子！我们可以把连续相同的敲击和连续相同的声音各自看成一个“块”。

比如，敲击 p = "LLRRRL"，我们可以把它看成是：

1. 一个包含 2 个 "L" 的块
2. 一个包含 3 个 "R" 的块
3. 一个包含 1 个 "L" 的块

同样，对于一个可能的声音 s = "LLLLRRRRRLL"，我们可以看成：

1. 一个包含 4 个 "L" 的块
2. 一个包含 5 个 "R" 的块
3. 一个包含 2 个 "L" 的块

现在问题就清晰多啦！要让 s 能够由 p 产生，必须满足以下几个条件：

1. 块的数量必须完全相同。p 分成了几块，s 也必须分成几块。如果数量不同，说明声音的节奏模式和敲击的节奏模式对不上，比如 p="LR" 有两块，s="LL" 只有一块，这肯定不行。
2. 对应块的字符必须相同。p 的第一块是 "L" 块，s 的第一块也必须是 "L" 块；p 的第二块是 "R" 块，s 的第二块也必须是 "R" 块……以此类推。
3. 声音块的大小要合理。对于每一个对应的块，假设 p 中有 count_p 次敲击，s 中有 count_s 次声音。因为每次敲击最少产生 1 声，最多产生 2 声，所以 count_s 必须满足 count_p <= count_s <= count_p * 2。
   • count_s 不能小于 count_p（每次敲击至少有1声）。
   • count_s 不能大于 count_p * 2（每次敲击至多有2声）。

只要 p 和 s 拆分成的块能满足以上所有条件，那么 s 就是一个可能产生的声音，答案就是 "YES"！否则，只要有任何一个条件不满足，答案就是 "NO"。

这种把连续相同元素合并成 (元素, 数量) 对的思想，就是我们接下来要用到的 行程长度编码 (Run-Length Encoding) 啦！

题解

下面就是解题代码的详细说明啦，本喵会一步一步带你看懂的~

#include <iostream>
#include <string>
#include <vector>
#include <utility>

void solve() {
    std::string p, s;
    std::cin >> p >> s;

    // --- 第一步：对 p 进行行程长度编码 ---
    // 这个 vector 用来存放 p 的编码结果，每个元素是 (字符, 连续出现的次数)
    std::vector<std::pair<char, int>> p_rle;
    if (!p.empty()) {
        p_rle.emplace_back(p[0], 1); // 先把第一个字符放进去
        for (size_t i = 1; i < p.length(); ++i) {
            // 如果当前字符和上一个相同，就增加计数
            if (p[i] == p_rle.back().first) {
                p_rle.back().second++;
            } else {
                // 如果不同，就新建一个块
                p_rle.emplace_back(p[i], 1);
            }
        }
    }

    // --- 第二步：对 s 进行行程长度编码 ---
    // 和处理 p 的方法一模一样喵
    std::vector<std::pair<char, int>> s_rle;
    if (!s.empty()) {
        s_rle.emplace_back(s[0], 1);
        for (size_t i = 1; i < s.length(); ++i) {
            if (s[i] == s_rle.back().first) {
                s_rle.back().second++;
            } else {
                s_rle.emplace_back(s[i], 1);
            }
        }
    }

    // --- 第三步：比较两个编码结果 ---

    // 条件1：块的数量必须相同
    if (p_rle.size() != s_rle.size()) {
        std::cout << "NO\n";
        return;
    }

    bool possible = true;
    for (size_t i = 0; i < p_rle.size(); ++i) {
        // 检查每个对应的块
        // 条件2：字符必须相同
        // 条件3：s 的计数不能小于 p 的计数
        // 条件4：s 的计数不能大于 p 的计数的两倍
        if (p_rle[i].first != s_rle[i].first ||      
            p_rle[i].second > s_rle[i].second ||      
            s_rle[i].second > p_rle[i].second * 2) {  
            possible = false; // 只要有一个条件不满足，就不可能了
            break; // 直接跳出循环
        }
    }

    if (possible) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    // 这是一个小优化，让输入输出更快，对付大数据时很有用哦
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍：行程长度编码 (Run-Length Encoding, RLE)

喵哈！最后来聊聊我们这次的大功臣——行程长度编码 (RLE)！

它是一种非常简单直观的数据压缩算法。它的核心思想是：用一个计数值来代替一连串连续重复的数据。

它是如何工作的呢？

想象一下，你有一串数据 AAAAABBBCCDAA。 如果用 RLE 来表示，就会变成 (A, 5), (B, 3), (C, 2), (D, 1), (A, 2)。 看，是不是简洁了很多？我们不再记录每一个 A，而是记录“有 5 个 A”，然后是“有 3 个 B”，以此类推。

为什么它在这里很有用？

在这道题里，我们关心的不是单个的 L 或 R，而是它们连续组成的“块”的性质。p = "LLRRRL" 和 s = "LLLLRRRRRLL"，它们的本质节奏都是 L块 -> R块 -> L块。RLE 恰好能帮我们提取出这种“块”结构的信息，包括每个块的类型（是 L 还是 R）和大小（长度）。

通过 RLE，我们把原始的、长长的字符串比较，转化为了对几个关键“块”的属性比较，让问题变得清晰又简单，是不是很厉害呀！

好啦，这次的题解就到这里啦！希望本喵的讲解对主人有帮助哦~ 如果还有不懂的地方，随时可以再来问我！喵~