LibreOJ

2770 「ROI 2017 Day 2」存储器

内存限制：512 MB 时间限制：2000 ms

题目描述

题目译自 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

样例 2

数据范围与提示

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

样例

样例输入 1

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

样例输出 1

Yes
No
Yes

样例输入 2

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

样例输出 2

Yes
No
Yes