题目信息
题目链接
题目描述
给定一个字符串 \(S\)，设其长度为 \(n\)，每个字符要么是 + 要么是 -。
定义一个片段为 \(S\) 的一个子串 \(S[l,r]\) 满足下面三个条件：
- \(l=1\) 或者 \(S_{l-1} \ne S_l\)。
- \(r=n\) 或者 \(S_{r+1} \ne S_r\)。
- \(S_l=S_{l+1}=\dots=S_{r-1}=S_r\)。
定义一次变换为：
- 选择 \(S\) 的两个相邻且长度不同的片段，改变长度较小的那个片段的所有字符为其相反字符。（
+变为-，-变为+）
现在有 \(q\) 次询问，每次询问给出只包含 + 和 - 并且长度相同的字符串 \(S_i,T_i\)，请你判断 \(S_i\) 是否能够通过若干次变换得到 \(T_i\)。
输入格式
第一行一个整数 \(q\) 表示询问次数。
接下来 \(q\) 行每行两个字符串 \(S_i,T_i\)，含义如题所示。
输出格式
对于每次询问输出一行一个字符串 Yes 或 No 表示是否可以完成题目所给要求。
样例输入 #1
3
++- +++
++-- ++++
++-+--+- ++++++++
样例输出 #1
Yes
No
Yes
样例输入 #2
3
++-+-- ++----
++-+-- +++---
-++- -++-
样例输出 #2
Yes
No
Yes
数据范围
注：本题只放部分数据，完整数据请左转 LOJ P2770 评测。
设 \(len=\sum |S_i|\)。
| 子任务编号 | 分值 | $1 \le len \le $ | 特殊性质 |
|---|---|---|---|
| \(1\) | \(20\) | \(16\) | \(T_i\) 中没有 - |
| \(2\) | \(30\) | \(10^3\) | \(T_i\) 中没有 - |
| \(3\) | \(20\) | \(10^6\) | \(T_i\) 中没有 - |
| \(4\) | \(20\) | \(10^3\) | 无 |
| \(5\) | \(10\) | \(10^6\) | 无 |