nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
转移自老blog

cf660C

链接

题意

        给你长度为n的01串,最多把k个0变成1,变完后连续的最长的全是1的串的长度是多少,并且输出最后得串;
        k<n<3e5

题解

        暴力:
            dp[i][j]代表前i个数把j个0变成1后,以位置i结尾的全为1的串长度最大是多少
            不妨设串为s[1:n]
            if s[i] = 0
                dp[i][j]   <----  dp[i-1][j-1]+1
            if s[i] = 1
                dp[i][j]   <----  dp[i-1][j]+1
        解法1:
            套路，统计前缀0的个数，然后枚举每一个位置作为变完后的全为1的串的结尾，于是起点就可以二分了，
            枚举终点i，则sum[i]-sum[j]<=k,sum具有单调性，于是二分
        解法2(优化):
            定义终点i对应的起点j为: 
                j=f(i)
            f单调
            可以用双指针扫描达到线性复杂度