- 给定一个 01 串 $s$，要求你找到一个与 $s$ 长度相等的 01 串 $t$ 并满足以下条件：
- 对于任意的 $l,r(1\leq l\leq r\leq n)$，$s[l:r]$ 和 $t[l:r]$ 的最长不下降子序列长度相同；
- $t$ 中 $0$ 的数量尽可能多。
- 有多解输出任意一种。$|S|\leq 10^5$。
sol
- 这个题非常有意思。容易想到按照一个顺序依次确定每个位置的值。
-
但是前面的位置确定了，当前位置的值不仅和之前的最长不下降子序列长度有关，还和 $1$ 的个数有关。
-
发现
10是不能被其它等长的串所替换的，它的最长不下降子序列长度为 $1$，而其它等长的串都为 $2$。 -
有一个思路（猜测），就是把串中的
10不断删除，直到不存在。但这样真的行吗？ -
删除某个
10后对所有 $l,r$ 最长不下降子序列长度的影响：- $l,r$ 完全包含被删除的
10，那么原先无论最长不下降子序列是怎么选的，都一定会选择10中的恰好一个数，现在它的长度必定减少 1； - $l,r$ 和 被删除的
10无交，那么最长不下降子序列长度不影响； - $l,r$ 和 被删除的
10有交但不包含，即 $l$ 或 $r$ 在10之间，如果是 $l$ 则原子序列一定会选择最左边的 $0$，如果是 $r$ 则原子序列一定会选择最右边的 $1$，删去后长度必定减少 1。
- $l,r$ 完全包含被删除的
- 删去后的问题，如果 $s'$ 和 $t'$ 满足条件，那么加回这个
10后仍然满足条件。 -
所以可以一直删去
10，直到没有10。考虑现在的串一定为00...011...1，可以把所有数字都变成 $0$，所有 $l,r$ 最长不下降子序列长度不变。 -
具体实现可以从左到右扫描，维护一个栈记录之前还没被删去的 $1$ 的位置，如果当前为 $0$ 且栈不为空则可以和前面的一起删去，否则加入栈。最后栈中的 $1$ 即没有被删去的 $1$，都变为 $0$ 即可。
```cpp
include
using namespace std;
string s; int top,t[110000];
int main(){
cin>>s; int n=s.length();
for (int i=0;i<n;i++)
if (s[i]=='1') t[++top]=i;
else if (top) top--;
while (top) s[t[top--]]='0';
cout<<s<<endl;
return 0;
}
```