[ROI 2017] 存储器 (Day 2)

Luogu

IDLGP10653

Time2000ms

Memory512MB

DifficultyP5

2017O2优化ROI（俄罗斯）

给定一个字符串 $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$。 ## Input 第一行一个整数 $q$ 表示询问次数。接下来 $q$ 行每行两个字符串 $S_i,T_i$，含义如题所示。 ## Output 对于每次询问输出一行一个字符串 `Yes` 或 `No` 表示是否可以完成题目所给要求。 [samples] ## Note #### 【数据范围】注：本题只放部分数据，完整数据请左转 [LOJ P2770](https://loj.ac/p/2770) 评测。设 $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$ | 无 |

Samples

Input #1

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

Output #1

Yes
No
Yes

Input #2

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

Output #2

Yes
No
Yes

API Response (JSON)

{
  "problem": {
    "name": "[ROI 2017] 存储器 (Day 2)",
    "description": {
      "content": "给定一个字符串 $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$。 定义一次**变换**为： - 选择",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10653"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个字符串 $S$，设其长度为 $n$，每个字符要么是 `+` 要么是 `-`。\n\n定义一个**片段**为 $S$ 的一个子串 $S[l,r]$ 满足下面三个条件：\n\n- $l=1$ 或者 $S_{l-1} \\ne S_l$。\n- $r=n$ 或者 $S_{r+1} \\ne S_r$。\n- $S_l=S_{l+1}=\\dots=S_{r-1}=S_r$。\n\n定义一次**变换**为：\n\n- 选择...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments