NOIP模拟测试29「爬山·学数数·七十和十七」

爬山题解不想写了

学数数

离散化然后找到以每一个值为最大值的连续子段有多少个,然后开个桶维护

那么怎么找以每一个值为最大值的连续子段个数

方法1(我的极笨的方法)

考试时我的丑陋思路,

定义极左值为左面第一个大于当前值的值,极右值为右面第一个大于当前值的值

,找到最大值然后当前符合的子段个数就为$r-l+1+(r-now)*(now-l)$

解释一下$r-l+1$为以$now$为边界的子段,$(r-now)*(now-l)$为包含$now$的子段

那么问题又转化为了如何求边界

我们发现找极左值,极右值过程可以二分实现,

我们每次找到最大值,然后找到左右子段的最大值和$id$,这些子段的最大值边界就是当前$now$!!!!

维护最大值$id$可以线段树实现

给一下实现

简单好想个屁嘞

但是比较直观是真的

void pre(ll l,ll r,ll now,ll nowmax){

    if(l>r) return ;

    if(l==r) {

        sum[nowmax]++;

        return ;

    }

    sum[nowmax]+=r-l+1+(r-now)*(now-l);

    maxn=0,ida=0;

    if(l<=now-1)

    {

        seg_max(1,l,now-1);

        pre(l,now-1,ida,maxn);

    }

    maxn=0,ida=0;

    if(now+1<=r)

    {

        seg_max(1,now+1,r);

        pre(now+1,r,ida,maxn);

    }

}

总代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define A 2222222

ll n,q,mx,mn=0x7fffffffff,ida,maxn,idb;

ll a[A],sum[A],b[A];

char c[10];

struct tree{

    ll l,r,val,id;

}tr[A];

void pushup(ll p){

    if(tr[p<<1].val>tr[p<<1|1].val){

        tr[p].val=tr[p<<1].val;

        tr[p].id=tr[p<<1].id;

    }

    else {

        tr[p].val=tr[p<<1|1].val;

        tr[p].id=tr[p<<1|1].id;

    }

}

void built(ll p,ll l,ll r){

    tr[p].l=l,tr[p].r=r;

    if(l==r){

        tr[p].val=a[l];

        tr[p].id=l;

        return ;

    }

    ll mid=(l+r)>>1;

    built(p<<1,l,mid);

    built(p<<1|1,mid+1,r);

    pushup(p);

}

void seg_max(ll p,ll l,ll r){

//    printf("p=%lld l=%lld r=%lld l=%lld r=%lld\n",p,l,r,tr[p].l,tr[p].r);

    if(tr[p].l>=l&&tr[p].r<=r){

        if(tr[p].val>maxn){

            maxn=tr[p].val;

            ida=tr[p].id;

        }

        return ;

    }

    ll mid=(tr[p].l+tr[p].r)>>1;

    if(mid>=l)

        seg_max(p<<1,l,r);

    if(mid<r)

        seg_max(p<<1|1,l,r);

}

void pre(ll l,ll r,ll now,ll nowmax){

    if(l>r) return ;

    if(l==r) {

        sum[nowmax]++;

//        printf("l=%lld nowmax=%lld \n",l,nowmax);

        return ;

    }

//    printf("l=%lld r=%lld nowmax=%lld r-l=%lld\n",l,r,nowmax,r-l+1);

    sum[nowmax]+=r-l+1+(r-now)*(now-l);

    maxn=0,ida=0;

    if(l<=now-1)

    {

        seg_max(1,l,now-1);

        pre(l,now-1,ida,maxn);

    }

    maxn=0,ida=0;

    if(now+1<=r)

    {

        seg_max(1,now+1,r);

        pre(now+1,r,ida,maxn);

    }

}

int main(){

    scanf("%lld%lld",&n,&q);

    for(ll i=1;i<=n;i++){

        scanf("%lld",&a[i]);

        b[i]=a[i];

        if(a[i]>mx){

            ida=i;

            mx=a[i];

        }

        mn=min(mn,a[i]);

    }

    sort(b+1,b+n+1);

    ll m=unique(b+1,b+n+1)-b-1;

//    for(ll i=1;i<=m;i++){

//        printf("b=%lld\n",b[i]);

//    }

    for(ll i=1;i<=n;i++)

        a[i]=lower_bound(b+1,b+1+m,a[i])-b;

    built(1,1,n);

    pre(1,n,ida,a[ida]);

    for(ll i=1;i<=n;i++)

        sum[i]+=sum[i-1];

    for(ll i=1,que;i<=q;i++){

        scanf("%s",c+1);

        scanf("%lld",&que);

        ll nxt=(lower_bound(b+1,b+m+1,que)-b),

        pre=(upper_bound(b+1,b+m+1,que))-b-1;

//        printf("pre=%lld nxt=%lld\n",pre,nxt);

        if(c[1]=='<'){

            if(que>mx){

                printf("%lld\n",sum[n]);

                continue ;

            }

            if(que<mn){

                printf("0\n");

                continue ;

            }

            if(pre!=nxt)

                printf("%lld\n",sum[pre]);

            else printf("%lld\n",sum[pre-1]);

        }

        else if(c[1]=='='){

            if(que>mx||que<mn){

                printf("0\n");

                continue ;

            }

            if(pre==nxt)

                printf("%lld\n",sum[pre]-sum[pre-1]);

            else printf("0\n");

        }

        else if(c[1]=='>'){

            if(que>mx){

                printf("0\n");

                continue ;

            }

            if(que<mn){

                printf("%lld\n",sum[n]);

                continue ;

            }

            if(pre==nxt)

                printf("%lld\n",sum[n]-sum[pre]);

            else printf("%lld\n",sum[n]-sum[pre]);

        }

    }

}

方法2

单调栈,显然可以单调栈,看到这个就必须想单调栈啊!

维护一个单调下降的栈当发现当前值比队尾小接着插,发现当前值不小$pop$,当前值的$l$就是$pop$后单调栈的栈顶,已经$pop$掉的值的$r$就是当前值

代码咕了

七十和十七

设$g[i]$为将相对大小为$i$的数插到队头要花多少步复原

注意是相对大小

以下说的1,2...都是相对大小

我们将$1$移到队头要$1$步复原,$g[1]=1$

将$2$移到队头你相对大小为$1$的也要复原$g[2]=g[1]+1$

将$3$移到队头你大小$1,2$也要复原$g[3]=g[2]+g[1]+1$

...类推

$g[n]=\sum\limits {i=1}^{i<=n-1}(g[i])+1$

然后我们设$f$为移动总步数

$f[i]=f[i-1](为1的情况)+\sum\limits_{j=1}^{j<=i-1} f[i-1]+(i-1)!*g[j]$

,最后再同时除以$i!$,为了方便我们设$E[i]=\frac{f[i]}{i!}$

原式变为$E[i]=E[i-1]+\frac{2^{i-1}-1}{i}$

我们化简移项等操作$xjb$搞就$AC$了

巴特西

NOIP模拟测试29「爬山·学数数·七十和十七」

学数数

方法1(我的极笨的方法)

总代码

方法2

七十和十七

最新文章

热门文章