#P17786. Flip and Reverse
Flip and Reverse
题目描述
给定一个只包含 和 的字符串 。你可以进行如下操作:
- 选择 的一个非空连续子串,且该子串中 和 的数量相等;
- 翻转该子串中的所有字符,即将所有 变为 ,所有 变为 ;
- 反转该子串。
例如,考虑 ,可以进行如下操作:
- 选择前六个字符作为操作的子串:00111011。注意该子串中 和 的数量相等,因此是合法的选择。选择子串 0、110 或整个字符串都不是合法选择。
- 翻转该子串中的所有字符:11000111。
- 反转该子串:10001111。
请你求出经过若干次(可以为零次)上述操作后,能够得到的字典序最小的字符串。
输入格式
第一行包含一个整数 (),表示测试用例的数量。接下来的 行,每行包含一个非空字符串,表示每个测试用例的输入字符串 。
所有字符串均由字符 和 组成,且所有字符串的总长度不超过 。
输出格式
对于每个测试用例,输出一行,表示经过若干次操作后能够得到的字典序最小的字符串。
输入输出样例 #1
输入 #1
3
100101
1100011
10101010
输出 #1
010110
0110110
10101010
说明/提示
在第一个测试用例中,应对整个字符串进行一次操作。
在第二个测试用例中,需要进行两次操作:0111001,0110110。
在第三个测试用例中,无论进行多少次操作,字符串都不会发生变化。
由 ChatGPT 4.1 翻译