爬山題解不想寫了

學數數

離散化然后找到以每一個值為最大值的連續子段有多少個,然后開個桶維護

那么怎么找以每一個值為最大值的連續子段個數

方法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]);}} } View Code

方法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$了

轉載于:https://www.cnblogs.com/znsbc-13/p/11394716.html

總結

以上是生活随笔為你收集整理的NOIP模拟测试29「爬山·学数数·七十和十七」的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。