The only difference between easy and hard versions is the length of the string. You can hack this problem only if you solve both problems.
Kirk has a binary string ss (a string which consists of zeroes and ones) of length nn and he is asking you to find a binary string tt of the same length which satisfies the following conditions:
- For any ll and rr (1≤l≤r≤n1≤l≤r≤n) the length of the longest non-decreasing subsequence of the substring slsl+1…srslsl+1…sr is equal to the length of the longest non-decreasing subsequence of the substring tltl+1…trtltl+1…tr;
- The number of zeroes in tt is the maximum possible.
A non-decreasing subsequence of a string pp is a sequence of indices i1,i2,…,iki1,i2,…,ik such that i1<i2<…<iki1<i2<…<ik and pi1≤pi2≤…≤pikpi1≤pi2≤…≤pik. The length of the subsequence is kk.
If there are multiple substrings which satisfy the conditions, output any.
InputThe first line contains a binary string of length not more than 20002000.
OutputOutput a binary string which satisfied the above conditions. If there are many such strings, output any of them.
题意
给出一个 串 S ,求一个串 T , 要求LIS等长,所有区间的 LIS 相等,0 的个数尽可能多
解:
从后往前贪心, 保证后面的解都是合法的
假如当前是0 作为起点 对后面的Lis 无影响
假如当前是 1 假如不是以他为起点 那么 就变为0 就一定更改lis
假如当前是 1 假如是以他为起点 那么 就变为0 就一定不会更改lis
所以 但是当 $tot1>=tot0$ 时 可以没有影响 可以改
// #include<bits/stdc++.h> using namespace std; string s; int main() { cin>>s; int tot1=0,tot2=0; for(int i=s.size()-1;i>=0;i--) { if(s[i]=='1') if(tot1>=tot2) s[i]='0';else tot1++; else { tot2++; } } cout<<s; }