字符串minn
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 1024 M,其他语言2048 M
64bit IO Format: %lld

题目描述

\hspace{15pt}给定一个长度为 n,由字符 \texttt{`0'}\texttt{`1'} 组成的字符串 s = s_1 s_2 \cdots s_n。按照如下两个阶段进行操作:
【阶段一】
\hspace{15pt}从后向前依次针对每个位置 i\left(1\leq i\leq n\right) 执行以下两种操作之一:
\hspace{23pt}\bullet\,如果 s_i = \texttt{`0'} 且后缀串 s_i s_{i+1} \cdots s_n 中,\texttt{`0'} 的数量多于 \texttt{`1'},你可以将 s_i 重新赋值为 \texttt{`1'},或者不操作;
\hspace{23pt}\bullet\,否则,不对 s_i 进行操作。
【阶段二】
\hspace{15pt}记经过【阶段一】操作得到的新字符串 s'
\hspace{15pt}再从后向前依次针对每个位置 i\left(1\leq i\leq n\right) 执行以下两种操作之一:
\hspace{23pt}\bullet\,如果 s'_i = \texttt{`1'} 且后缀串 s'_i s'_{i+1} \cdots s'_n 中,\texttt{`1'} 的数量多于 \texttt{`0'},你可以将 s'_i 重新赋值为 \texttt{`0'},或者不操作;
\hspace{23pt}\bullet\,否则,不对 s'_i 进行操作。

\hspace{15pt}记经过【阶段二】操作得到的新字符串 s''。请输出能够得到的字典序最小的字符串 s''

【名词解释】
\hspace{15pt}字典序比较:从字符串的第一个字符开始逐个比较,直到找到第一个不同的位置,通过比较这个位置字符的字母表顺序,得到字符串的大小。

本题纯净版 Markdown 提供如下。
# A.字符串minn

## 题目描述

$\hspace{15pt}$给定一个长度为 $n$,由字符 $\texttt{`0'}$ 和 $\texttt{`1'}$ 组成的字符串 $s = s_1 s_2 \cdots s_n$。按照如下两个阶段进行操作:
【阶段一】
$\hspace{15pt}$从后向前依次针对每个位置 $i\left(1\leq i\leq n\right)$ 执行以下两种操作之一:  
$\hspace{23pt}\bullet\,$如果 $s_i = \texttt{`0'}$ 且后缀串 $s_i s_{i+1} \cdots s_n$ 中,$\texttt{`0'}$ 的数量多于 $\texttt{`1'}$,你可以将 $s_i$ 重新赋值为 $\texttt{`1'}$,或者不操作;  
$\hspace{23pt}\bullet\,$否则,不对 $s_i$ 进行操作。
【阶段二】
$\hspace{15pt}$记经过【阶段一】操作得到的新字符串 $s'$。
$\hspace{15pt}$再从后向前依次针对每个位置 $i\left(1\leq i\leq n\right)$ 执行以下两种操作之一:  
$\hspace{23pt}\bullet\,$如果 $s'_i = \texttt{`1'}$ 且后缀串 $s'_i s'_{i+1} \cdots s'_n$ 中,$\texttt{`1'}$ 的数量多于 $\texttt{`0'}$,你可以将 $s'_i$ 重新赋值为 $\texttt{`0'}$,或者不操作;  
$\hspace{23pt}\bullet\,$否则,不对 $s'_i$ 进行操作。

$\hspace{15pt}$记经过【阶段二】操作得到的新字符串 $s''$。请输出能够得到的<u>字典序</u>最小的字符串 $s''$。  

【名词解释】
$\hspace{15pt}$<u>字典序</u>比较:从字符串的第一个字符开始逐个比较,直到找到第一个不同的位置,通过比较这个位置字符的字母表顺序,得到字符串的大小。

## 输入描述

$\hspace{15pt}$第一行输入一个整数 $n\left(1 \leq n \leq 2\times 10^5\right)$,表示字符串的长度。
$\hspace{15pt}$第二行输入一个长度为 $n$,由字符 $\texttt{`0'}$ 和 $\texttt{`1'}$ 组成的字符串 $s$,表示初始字符串。

## 输出描述

$\hspace{15pt}$输出一个长度为 $n$ 的字符串,表示经过上述操作后能够得到的字典序最小的字符串。

## 样例

~~~text
3
110
~~~

~~~text
001
~~~

$\hspace{15pt}$对于这一组样例,其中一种最优的操作如下:
$\hspace{15pt}$【阶段一】  
$\hspace{23pt}\bullet\,$处理 $s_3$ 时,后缀串 $\texttt{"0"}$ 中 $\texttt{`0'}$ 数量多于 $\texttt{`1'}$,将 $s_3$ 置为 $\texttt{`1'}$,得到 $\texttt{"111"}$;  
$\hspace{23pt}\bullet\,$处理 $s_2$ 时不进行操作,字符串依旧为 $\texttt{"111"}$;  
$\hspace{23pt}\bullet\,$处理 $s_1$ 时不进行操作,字符串依旧为 $\texttt{"111"}$;  
$\hspace{15pt}$【阶段二】  
$\hspace{23pt}\bullet\,$处理 $s_3$ 时不进行操作,字符串依旧为 $\texttt{"111"}$;   
$\hspace{23pt}\bullet\,$处理 $s_2$ 时,后缀串 $\texttt{"11"}$ 中 $\texttt{`1'}$ 数量多于 $\texttt{`0'}$,将 $s_2$ 置为 $\texttt{`0'}$,得到 $\texttt{"101"}$;   
$\hspace{23pt}\bullet\,$处理 $s_1$ 时,后缀串 $\texttt{"101"}$ 中 $\texttt{`1'}$ 数量多于 $\texttt{`0'}$,将 $s_1$ 置为 $\texttt{`0'}$,最终结果为 $\texttt{"001"}$。  

~~~text
6
101001
~~~

~~~text
001101
~~~

输入描述:

\hspace{15pt}第一行输入一个整数 n\left(1 \leq n \leq 2\times 10^5\right),表示字符串的长度。
\hspace{15pt}第二行输入一个长度为 n,由字符 \texttt{`0'}\texttt{`1'} 组成的字符串 s,表示初始字符串。

输出描述:

\hspace{15pt}输出一个长度为 n 的字符串,表示经过上述操作后能够得到的字典序最小的字符串。
示例1

输入

复制
3
110

输出

复制
001

说明

\hspace{15pt}对于这一组样例,其中一种最优的操作如下:
\hspace{15pt}【阶段一】
\hspace{23pt}\bullet\,处理 s_3 时,后缀串 \texttt{\texttt{`0'} 数量多于 \texttt{`1'},将 s_3 置为 \texttt{`1'},得到 \texttt{
\hspace{23pt}\bullet\,处理 s_2 时不进行操作,字符串依旧为 \texttt{
\hspace{23pt}\bullet\,处理 s_1 时不进行操作,字符串依旧为 \texttt{
\hspace{15pt}【阶段二】
\hspace{23pt}\bullet\,处理 s_3 时不进行操作,字符串依旧为 \texttt{
\hspace{23pt}\bullet\,处理 s_2 时,后缀串 \texttt{\texttt{`1'} 数量多于 \texttt{`0'},将 s_2 置为 \texttt{`0'},得到 \texttt{
\hspace{23pt}\bullet\,处理 s_1 时,后缀串 \texttt{\texttt{`1'} 数量多于 \texttt{`0'},将 s_1 置为 \texttt{`0'},最终结果为 \texttt{
示例2

输入

复制
6
101001

输出

复制
001101