[思维]Theramore 2022杭电多校第8场 1001

Problem Description

\space \space  Those blood-soaked shores of Kalimdor is like a ghost haunting Jaina Proudmoore ever since the day she pushed her father into hell.

\space \space  Now, standing in front of the devastated ruins of Theramore, she knew how naive she had been to want peace.

\space \space  The Focusing Iris. It was the most brutal and cowardly killing method Jaina could imagine.

\space \space  The Horde wants war. They will do anything to destroy us. But if this is all they want, Jaina will be pleased to offer them a big one.

The warships of the Horde can be described as a string ss which contains only '0' and '1', denoting the small warship and the large warship. Jaina can perform some magic to the string. In one magic, she chooses an arbitrary interval with odd length and reverse it. Jaina can perform this magic as many times as she likes.

Jaina wants the small warships to be in the front, since they are easier to destroy. She asks for your help, and you need to tell her the lexicographically smallest string that she can obtain.

Note: in this problem, suppose two sequences ss and tt both have length nn, then ss is lexicographically smaller than tt if there exists a position i(1\leq i\leq n)i(1≤i≤n) such that s_j = t_jsj​=tj​ for all 1\leq j < i1≤j

Input

The input consists of multiple test cases.

The first line contains an integer T\ (1\leq T \leq 10)T (1≤T≤10) denoting the number of test cases.

Each test case consists of only one line containing a string s\ (|s| \leq 10^5)s (∣s∣≤105).

Output

Output one line containing the lexicographically smallest string that you can get.

Sample Input

2

101001

01101100000000101010

Sample Output

001011

00000000001010101111

Hint

In the first test case, Jaina performs magic to the interval [3,5][3,5] and the string is changed to 100011100011. Then Jaina performs magic to the interval [1,3][1,3] and the string is changed to 001011001011.

题意： 给出一个01串，可以选择其中奇数长度的一段进行反转，这个操作可以进行任意次，问最终能得到的字典序最小的01串是多少。

分析： 可以发现，这种操作总是会让区间内对应数字交换位置，如果再更深入一点，无论如何进行这种操作，奇数位置的数字只会和奇数位置数字交换，偶数位置的数字只会和偶数位置数字交换，而且对区间[l, r]进行反转后可以再对区间[l+1, r-1]进行反转，这就相当于只让第l个位置和第r个位置的数字交换了位置，通过这种交换就可以让偶数位置的0和奇数位置的0尽量往前放，当0用完了就填1，最后就得到了字典序最小的01串。

具体代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
 
char s[100005];
 
signed main()
{
	int T;
	cin >> T;
	while(T--){
		scanf("%s", s+1);
		int len = strlen(s+1);
		int n0 = 0, n1 = 0;
		for(int i = 1; i <= len; i++){
			if((i&1) && s[i] == '0')
				n1++;
			if(!(i&1) && s[i] == '0')
				n0++;
		}
		for(int i = 1; i <= len; i++){
			if(i&1){
				if(n1){
					n1--;
					putchar('0');
				}
				else putchar('1');
			}
			else{
				if(n0){
					n0--;
					putchar('0');
				}
				else putchar('1');
			}
		}
		puts("");
	} 
    return 0;
}