四川网站开发哪家好,网站建设云尚网络,asp的网站,公司简介ppt模板免费下载传送门
题意#xff1a;给一个01串SSS#xff0c;求一个等长的01串TTT SSS和TTT所有对应位置的子串最长不下降子序列长度#xff08;以下简称LIS\text{LIS}LIS#xff09;相同TTT中0的数量尽量多 ∣S∣≤100000|S| \leq 100000∣S∣≤100000
对于一个01串SSS#xff0c;…传送门
题意给一个01串SSS求一个等长的01串TTT
SSS和TTT所有对应位置的子串最长不下降子序列长度以下简称LIS\text{LIS}LIS相同TTT中0的数量尽量多
∣S∣≤100000|S| \leq 100000∣S∣≤100000
对于一个01串SSS我们称它是固定的当且仅当不存在一个长度相同的01串TTT,它们所有对应位置的子串LIS\text{LIS}LIS相同即修改任意一个位置都会改变LIS\text{LIS}LIS并且规定空串是固定的。
两个固定的串拼起来仍然是固定的。如果修改了一个位置根据定义这个位置原来归属的串的LIS\text{LIS}LIS一定发生了变化。一个固定的串0和1个数相等LIS\text{LIS}LIS等于其长度的一半即全选0或全选1。前面和下一条递归证明边界为空串。后面由于一组01见下一条的1一定在0的前面最多只有1的贡献。一个固定的串前面添“1”后面添“0”后仍然固定。和上一条递归证明修改中间同理修改两边一定会增加1。
我们在原串中删除所有极大的固定子串由于没有“10”所以剩下的一定是“00000……11111”
由定义固定子串是不能修改的
【解法一】
我们发现这玩意就是括号匹配
用个栈维护一下得到剩下的字符
然后把后面的一坨1都改成0。显然不能改更多的。
这样对于任意一个子串把它的极大固定子串挖出来由于后缀的“1”可能改成了“0”把影响的段改成“全选0”后LIS\text{LIS}LIS不会变化可以保证合法。
【解法二】
结论某个1可以改为0当且仅当修改后整个串的LIS\text{LIS}LIS不变。
其实本质是相同的。如果某个位置的1在某个固定子串中显然修改会改变这个子串的LIS\text{LIS}LIS并且会改变原串的LIS\text{LIS}LIS。否则对LIS\text{LIS}LIS不会产生影响。
倒着DP一下即可。
#include iostream
#include cstdio
#include cstring
#include cctype
#define MAXN 100005
using namespace std;
char s[MAXN];
int pre0[MAXN],suf1[MAXN],dp[MAXN];
int main()
{scanf(%s,s1);int nstrlen(s1);for (int i1;in;i) pre0[i]pre0[i-1](s[i]0);for (int in;i1;i--) suf1[i]suf1[i1](s[i]1);for (int in;i1;i--) dp[i](s[i]1? max(suf1[i],dp[i1]):dp[i1]1);int now0;for (int i1;in;i)if (s[i]0||now1dp[i1]dp[1]) putchar(0),now;else putchar(1);return 0;
}
