#2770. 「ROI 2017 Day 2」存储器

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Planet6174

题目描述

题目译自 ROI 2017 Day 2 T1. Накопитель

假设有一个字符串 P[1\ldots N] 仅含有 +- 两种字符(你就当做这是 Pascal 里的字符数组 qwq)。如果 P 的子串 P[L\ldots R\;\!] (L\le R) 同时满足:

  • 子串里只有一种字符 c
  • L=1 , 或子串左边的第一个字符 P[L-1] c 不同;
  • R=N , 或子串右边的第一个字符 P[R+1] c 不同;

那么 P[L\dots R\;\!] 即为 P 的一个「片段」。

给你 q 组询问,每次询问包含两个字符串 s_i, t_i ,这两个字符串都只含有 +- 两种字符。
试问:能否将 s_i 通过若干次「变换」修改为 t_i
在每一次变换中,你可以在字符串中找两个「相邻」且「长度不同」的片段,将二者中较短的片段里面所有的字符改为另一种字符(+ 改成 -- 改成 +)。改完后,如果满足条件,这个片段会和两边融合,成为新的一大块片段。

输入格式

第一行,一个整数 q
在接下来的 q 行中,每行有两个仅包含 + - 的字符串 s_i, t_i ,用空格分隔。

样例

样例输入 1

3
++- +++
++-- ++++
++-+--+- ++++++++

样例输出 1

Yes
No
Yes

样例输入 2

3
++-+-- ++----
++-+-- +++---
-++- -++-

样例输出 2

Yes
No
Yes

数据范围与提示

子任务编号 分值 \sum\lvert s_i \rvert 额外限制
1 20 \sum\lvert s_i \rvert ⩽ 16 t_i 中没有 -
2 30 \sum\lvert s_i \rvert ⩽ 1000
3 20 \sum\lvert s_i \rvert ⩽ 10^6
4 20  \sum\lvert s_i \rvert ⩽ 1000
5 10 \sum\lvert s_i \rvert ⩽ 10^6 无