1 条题解
-
3 (limingyang) LV 8 @ 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})\)的呢……
所以,我才是大佬……啊呸!我才是最优解!!!
- 1
信息
- ID
- 1002
- 难度
- 2
- 分类
- (无)
- 标签
- 递交数
- 9
- 已通过
- 3
- 通过率
- 33%
- 被复制
- 2
- 上传者