头像

limingyang




离线:14天前


新鲜事 原文

limingyang
5个月前
我要去AK IOI了/kk flag真不能乱立 原因见https://www.acwing.com/file_system/file/content/whole/index/content/1088047/


新鲜事 原文

limingyang
7个月前
I AK IOI 这不是JC 因为某同学的一场比赛就叫IOI 我AK了 QwQ



limingyang
7个月前

原题链接

又是一个建立在Vijos的域之上的名不见经传的小OJ(看管理员用户名好像能知道些什么?)
不过这道题不错
当然,标程的暴力很水,但我带来的二分解法会有些难度
本文同步发表于该题目的题解区
下面是正文,请耐心看完(有花絮):


$\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})$的呢……
所以,我才是大佬……啊呸!我才是最优解!!!



新鲜事 原文

limingyang
7个月前
外校考试加油! 考上了我就去AKIOI!(大雾