CF2094D Tung Tung Sahur 题解

_Star_Universe_ · 2025-05-03 12:55:52 · 题解

CF2094D

题意 & 思路

有两个字符串 p,s，保证两个字符串仅由 R 和 L 组成，p 中的 R 可以对应 s 中的 R 和 RR，p 中的 L 可以对应 s 中的 L 和 LL。在这样的规则下如果 s 可能是由 p 转化而来的，输出 YES，否则输出 NO。

先把两个字符串分别分成较长的字符相同的连续段，如果段数不匹配显然不可能。将分割出的连续段一一比对，若应该对应的两段字符不同（如 LL:RRR），则不可能变换成功。最后，因为敲一下左鼓或右鼓至少响一次，至多响两次，所以令 len_p 为 p 中某子串的长度，s 中与其对应的子串长度为 len_s，有：len_p \le len_s \le 2 \cdot len_p，满足输出 YES，不满足输出 NO。