#P17786. Flip and Reverse

Flip and Reverse

题目描述

给定一个只包含 00 和 11 的字符串 ss。你可以进行如下操作:

  1. 选择 ss 的一个非空连续子串,且该子串中 00 和 11 的数量相等;
  2. 翻转该子串中的所有字符,即将所有 00 变为 11,所有 11 变为 00;
  3. 反转该子串。

例如,考虑 s=00111011s = 00111011,可以进行如下操作:

  • 选择前六个字符作为操作的子串:00111011。注意该子串中 00 和 11 的数量相等,因此是合法的选择。选择子串 0、110 或整个字符串都不是合法选择。
  • 翻转该子串中的所有字符:11000111。
  • 反转该子串:10001111。

请你求出经过若干次(可以为零次)上述操作后,能够得到的字典序最小的字符串。

输入格式

第一行包含一个整数 TT(1≤T≤5⋅1051 \leq T \leq 5 \cdot 10^5),表示测试用例的数量。接下来的 TT 行,每行包含一个非空字符串,表示每个测试用例的输入字符串 ss。

所有字符串均由字符 00 和 11 组成,且所有字符串的总长度不超过 5⋅1055 \cdot 10^5。

输出格式

对于每个测试用例,输出一行,表示经过若干次操作后能够得到的字典序最小的字符串。

输入输出样例 #1

输入 #1

3
100101
1100011
10101010

输出 #1

010110
0110110
10101010

说明/提示

在第一个测试用例中,应对整个字符串进行一次操作。

在第二个测试用例中,需要进行两次操作:0111001,0110110。

在第三个测试用例中,无论进行多少次操作,字符串都不会发生变化。

由 ChatGPT 4.1 翻译