题解

1 条题解

  • 3
    @ 2020-07-02 22:01:50

    \(\large\texttt{十年OI一场空,少个“-1”见祖宗!}\)
    这道题听\(b6e0\)\(\huge\texttt{大佬}\)说,有一种\(O(n)\)的神奇方法,可本蒟蒻不会……
    于是,我是用了较为暴力的\(O(n*log(n))\)方法。
    这种方法具体就是:先以每个\(0\)开头,以下一个\(0\)的前一位结尾,分成多组。然后在每一位做二分查找,按组数查找合适的结尾,在经过计算算出总长度,最后输出最长长度。
    于是乎,代码就变成了这样:

    #include <bits/stdc++.h>
    using namespace std;
    #define l s.size()
    int main(){
        string s;
        int n, maxx=0;
        cin >> s >> n;
        int a[l];
        if (s[0]=='0') a[0]=1; 
        else a[0]=0;
        for (int i=1; i<l; i++){
                if (s[i]=='0') a[i]=a[i-1]+1;
                else a[i]=a[i-1];
            }//先算出每一位所对应的组数 
        for (int i=0; i<l; i++){
            int x;
            if (s[i]=='0') x=a[i]+n-1;
            if (s[i]=='1') x=a[i]+n;//然后计算最长能延伸到第几组 
            int f;
            if (a[l-1]<x) f=l-i;
            else f=upper_bound(a+i, a+l, x)-a-i;//进行二分查找 
            maxx=max(maxx, f);//打擂台比最大值 
        }
        cout << maxx << endl;
        return 0;
    }
    

    \(\huge\texttt{幕后花絮}\)
    后来,我怂恿\(b6e0\)大佬在我的\(OJ\)提交后,偷窥了他的代码(((
    事实证明,他的代码也不是\(O(n)\)啊(((
    好像是\(O(\dfrac{n^2}{2})\)的呢……
    所以,我才是大佬……啊呸!我才是最优解!!!

    • @ 2020-07-02 22:11:16

      为什么大家都喜欢将我的名字用\(\LaTeX\)啊,名字一般不用\(\LaTeX\)的

    • @ 2020-07-03 07:02:39

      @\(b6e0\):因为您太强了,和我们不是一个等级的,所以要不一般,要有一种世上独一无二的名字才能配得上您的水平(((

    • @ 2020-08-20 19:36:17

      怂恿好像是贬义词。。。我的代码是\(O(n)\)的,双指针,\(i\)从\(1\)扫到\(n\),\(j\)也从\(1\)扫到\(n\),不是嵌套,所以均摊\(O(n)\)。

    • @ 2020-08-20 20:13:49

      @b6e0: 啊那我再看看可能是眼睛不太好

    • @ 2020-08-20 21:29:10

      @b6e0: 哎不对啊,您的这个就是嵌套(

    • @ 2020-10-22 06:34:19

      @b6e0: 哦您的确实不是嵌套(

  • 1

信息

ID
1002
难度
2
分类
(无)
标签
递交数
9
已通过
3
通过率
33%
被复制
2
上传者