Codeforces Round #652 (Div. 2) B题_b. long long time limit per test2 seconds memory l

B. AccurateLee
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Lee was cleaning his house for the party when he found a messy string under the carpets. Now he’d like to make it clean accurately and in a stylish way…

The string s he found is a binary string of length n (i. e. string consists only of 0-s and 1-s).

In one move he can choose two consecutive characters si and si+1, and if si is 1 and si+1 is 0, he can erase exactly one of them (he can choose which one to erase but he can’t erase both characters simultaneously). The string shrinks after erasing.

Lee can make an arbitrary number of moves (possibly zero) and he’d like to make the string s as clean as possible. He thinks for two different strings x and y, the shorter string is cleaner, and if they are the same length, then the lexicographically smaller string is cleaner.

Now you should answer t test cases: for the i-th test case, print the cleanest possible string that Lee can get by doing some number of moves.

Small reminder: if we have two strings x and y of the same length then x is lexicographically smaller than y if there is a position i such that x1=y1, x2=y2,…, xi−1=yi−1 and xi<yi.

Input
The first line contains the integer t (1≤t≤104) — the number of test cases.

Next 2t lines contain test cases — one per two lines.

The first line of each test case contains the integer n (1≤n≤105) — the length of the string s.

The second line contains the binary string s. The string s is a string of length n which consists only of zeroes and ones.

It’s guaranteed that sum of n over test cases doesn’t exceed 105.

Output
Print t answers — one per test case.

The answer to the i-th test case is the cleanest string Lee can get after doing some number of moves (possibly zero).

Example
inputCopy
5
10
0001111111
4
0101
8
11001101
10
1110000000
1
1
outputCopy
0001111111
001
01
0
1
Note
In the first test case, Lee can’t perform any moves.

In the second test case, Lee should erase s2.

In the third test case, Lee can make moves, for example, in the following order: 11001101 → 1100101 → 110101 → 10101 → 1101 → 101 → 01.
题意：就是 10 可以变为1或者0 压缩串，如果压缩长度一样，要保证串的字典序尽量的小
思路：原文链接：https://blog.csdn.net/moasad/article/details/106937738。
那么再举几个例子就会发现，我们只要一个子结构的第一个字符为1，最后一个字符为0，那么中间的就都可以删掉。所以我们找到原字符串中的最小位置的1和最大位置的0，那么这俩个位置的所连成的片段，除了最后一个0不删，其他就都删除。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<iomanip>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
int main()
{
	int t; cin >> t;
	while (t--)
	{
		char s[100001]; int n;
		cin >> n >> s;
		int num0 = 0, num1 = 1000000;
		for (int i = 0; i <n; i++)
		{
			if (s[i] == '0')
			{
				num0 = max(num0, i);
			}
			else
			{
				num1 = min(i, num1);
			}
		}
		if (num1 >= num0)
			cout << s << endl;
		else
		{
			for (int i = 0; i < num1; i++)
				cout << s[i];
			for (int i = num0; i < strlen(s); i++)
				cout << s[i];
			cout << endl;
		}

	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42