B. Accuratelee [double pointer] [substr function]

A year and a half ago codeforces A problem done on , It was written with another number before , Today, I suddenly turned to hair
link https://codeforces.com/contest/1369/problem/B
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
input
5
10
0001111111
4
0101
8
11001101
10
1110000000
1
1
output
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: 1100110 1 → 110 0101 → 110 101 → 10 101 → 110 1 → 10 1 → 01.

The main idea of the topic ： Given 01 String , In a string , If 10 It can be compressed into 1 or 0, After the output is compressed , Select the string output with the smallest dictionary order among all the shortest strings .
Process simulation
10
0001111111

0001111111

Location 12345678910
The number 0001111111
Search from left to right , first 1 Position of appearance l=4,
Search from right to left , first 0 Position of appearance r=3,
Do not conform to the l<r, Therefore, the string is not compressed , Direct output 0001111111

4
0101

001

Location 1234
The number 0101
Search from left to right , first 1 Position of appearance l=2,
Search from right to left , first 0 Position of appearance r=3,
accord with l<r, So interval [2,3] String in 10 Compressible to 0, So after the string is compressed , Output 001

8
11001101

01

Location 12345678
The number 11001101

Search from left to right , first 1 Position of appearance l=1,
Search from right to left , first 0 Position of appearance r=7,
accord with l<r, So interval [1,7] String in 1100110 Compressible to 0, So after the string is compressed , Output 01

10
1110000000

0

Location 12345678910
The number 1110000000

Search from left to right , first 1 Position of appearance l=1,
Search from right to left , first 0 Position of appearance r=10,
accord with l<r, So interval [1,10] String in 1110000000 Compressible to 0, So after the string is compressed , Output 0

1
1

1

Location 1
The number 1

Search from left to right , first 1 Position of appearance l=1,
Search from right to left , first 0 Position of appearance r, Can't find ,
Do not conform to the l<r, Therefore, the string is not compressed , Direct output 1

The next code is original

c++ in substr Function application
#include
#include
using namespace std;
int main()
{
　　string s(“12345asdf”);
　　string a = s.substr(0,5);
// Get string s From the first 0 The start length of the bit is 5 String
　　cout << a << endl;
}
Output is as follows ：
12345

Be careful
0. purpose ： A structure string Methods

form ：s.substr(pos, n)
explain ： Return to one string,
contain s In the from pos At the beginning n A copy of characters
（pos The default value of is 0,n The default value of is s.size() - pos,
That is, without parameters, the whole... Will be copied by default s）

original AC Code

#include // substr function ( Who starts , length ) [ Closed interval ]

using namespace std;

int main()
{
    
	int t,n;
	string s;
	cin >> t;
	while (t–) {
    
		cin >> n;
		string s;
		cin >> s;
		
		int i = 0, j = n;
		while (i < n && s[i] == ‘0’)
			i++; // Note that this time i The pointer points to the first one on the left 1 The location of , And substr() Parameters are related to ,substr What's merged is 0 To i The last position of this section , This length is i Instead of i-1
		while (j > 0 && s[j - 1] == ‘1’)
			j–;
			
		if (i==j)
			cout<< s << endl;
		else // The first one on the left 1 Go to the first one on the right 0 The range of ( close ) Merge into numbers 0, The rest remains the same 
			cout << s.substr(0, i) + ‘0’ + s.substr(j) << endl;
	}
	return 0;
}