_10.11

虽然是虚拟世界，但是心意却不是假的，想要和你在一起的想法一刻都没有改变，回到现实世界我第一想见到的人就是桐人，再一次喜欢你，和你真正的交往，真正的结婚 。

——亚斯娜《刀剑神域》

 1 #include<bits/stdc  .h> 2 #define mod 1000000007LL 3 #define int long long 4 #define LL long long 5 using namespace std; 6 LL fac[105],inv[105],f[105][10005],tmp[2][10005]; 7 LL n,m,c,Ans; 8 LL mgml(LL a,LL b,LL ans=1){ 9     for(;b;b>>=1,a=a*a%mod) if(b&1) ans=ans*a%mod;10     return ans;11 }12 LL C(int x,int y){13     if(x<y) return 0;14     return fac[x]*inv[y]%mod*inv[x-y]%mod;15 }16 signed main(){17     fac[0]=inv[0]=inv[1]=1;18     for(int i=1;i<=100;  i) fac[i]=fac[i-1]*i%mod;19     for(int i=2;i<=100;  i) inv[i]=inv[mod%i]*(mod-mod/i)%mod;20     for(int i=2;i<=100;  i) inv[i]=inv[i-1]*inv[i]%mod;21     scanf("%lld%lld%lld",&n,&m,&c);22     const LL t1=m/n,t2=m%n;23     for(int i=0;i<=n;  i) tmp[0][i]=mgml(C(n,i),t1),tmp[1][i]=mgml(C(n,i),t1 1);24     f[0][0]=1;25     for(int i=1;i<=n;  i)26         for(int j=0;j<=min(c,n*i);  j)27             for(int k=0;k<=min(n,j);  k)28                 f[i][j]=(f[i][j] f[i-1][j-k]*(i<=t2?tmp[1][k]:tmp[0][k])%mod)%mod;29     printf("%lld\n",f[n][c]);30     return 0;31 }

T1

 1 #include<bits/stdc  .h> 2 #define N 10000005 3 using namespace std; 4 inline int read(){ 5     register int x=0,f=1;char ch=getchar(); 6     while(!isdigit(ch)) f=ch=='-'?-1:1,ch=getchar(); 7     while(isdigit(ch)) x=(x<<1) (x<<3) ch-48,ch=getchar(); 8     return x*f; 9 }10 int n,top,Ans;11 int A[N],sta[N],nxt[N];12 int main(){13     n=read();14     for(int i=1;i<=n;  i) A[i]=read(),nxt[i]=i;15     for(int i=1;i<=n;  i){16         while(top&&A[sta[top]]<=A[i]) (A[nxt[sta[top]]]<=A[nxt[i]])?nxt[i]=min(nxt[i],nxt[sta[top]]):0,top--;17         sta[  top]=i;18     }19     for(int i=1;i<=n;  i) Ans=max(Ans,i-nxt[i] 1);20     return !printf("%d\n",Ans);21 }

T2

 1 #include<bits/stdc  .h> 2 #define N 100005 3 using namespace std; 4 inline int read(){ 5     register int x=0,f=1;char ch=getchar(); 6     while(!isdigit(ch)) f=ch=='-'?-1:1,ch=getchar(); 7     while(isdigit(ch)) x=(x<<1) (x<<3) ch-48,ch=getchar(); 8     return x*f; 9 }10 int n,m,blosiz,blonum,top,ans;11 int bel[N],ant[N],L[N],R[N],Ans[N];12 struct node{int l,r,id,ans;}sta[1200];13 struct Query{int l,r,id;}q[N];14 bool cmp(const Query &a,const Query &b){return bel[a.l]!=bel[b.l]?bel[a.l]<bel[b.l]:a.r<b.r;}15 void Record(int pos){16     sta[  top]=(node){L[pos],R[pos],pos,ans};17 }18 void Convolution(){19     while(top){20         L[sta[top].id]=sta[top].l;21         R[sta[top].id]=sta[top].r;22         ans=sta[top].ans;23         top--;24     }25 }26 int main(){27 //    freopen("text.in","r",stdin);28 //    freopen("a.out","w",stdout);29     n=read(),m=read(),blosiz=sqrt(n),blonum=ceil((double)n/blosiz);30     for(int i=1;i<=blonum;  i)31         for(int j=(i-1)*blosiz 1;j<=i*blosiz&&j<=n;  j)32             bel[j]=i;33     for(int i=1;i<=n;  i) ant[i]=read();34     for(int i=1;i<=m;  i) q[i].id=i,q[i].l=read(),q[i].r=read();35     sort(q 1,q m 1,cmp);int hea=1;36     for(int I=1;I<=blonum;  I){37         memset(L,0,sizeof L);38         memset(R,0,sizeof R);39         top=0; ans=1;40         int r=I*blosiz;41         while(hea<=m&&bel[q[hea].l]==I){42 //            printf("在第 %d 块 L:%d R:%d\n",I,q[hea].l,q[hea].r);43             if(bel[q[hea].r]==I){44                 for(int j=q[hea].l;j<=q[hea].r;  j){45                     int i=ant[j];46                     Record(i);47                     if(!L[i]) L[i]=i,R[i]=i;48                     int MINL=L[i-1]==0?i:L[i-1],MAXR=R[i 1]==0?i:R[i 1];49                     Record(MINL),R[MINL]=MAXR;50                     Record(MAXR),L[MAXR]=MINL;51                     ans=max(ans,MAXR-MINL 1);52                 }53                 Ans[q[hea].id]=ans;54                 Convolution();55                 hea  ;56                 continue;57             }58             while(q[hea].r>r){59                   r;int i=ant[r];60                 if(!L[i]) L[i]=i,R[i]=i;61                 int MINL=L[i-1]==0?i:L[i-1],MAXR=R[i 1]==0?i:R[i 1];62                 R[MINL]=MAXR;63                 L[MAXR]=MINL;64                 ans=max(ans,MAXR-MINL 1);65             }66             for(int j=I*blosiz;j>=q[hea].l;--j){67                 int i=ant[j];68                 Record(i);69                 if(!L[i]) L[i]=i,R[i]=i;70                 int MINL=L[i-1]==0?i:L[i-1],MAXR=R[i 1]==0?i:R[i 1];71                 Record(MINL),R[MINL]=MAXR;72                 Record(MAXR),L[MAXR]=MINL;73                 ans=max(ans,MAXR-MINL 1);74             }75             Ans[q[hea].id]=ans;76             Convolution();77               hea;78         }79     }80     for(int i=1;i<=m;  i) printf("%d\n",Ans[i]);81     return 0;82 }

T3

 

A. chess

容易发现当你确定前n行时，后面的m-n行就已经确定了。

那么我们只需要通过dp确定前n行的摆放情况，然后乘以次数即可。

具体的，就是将m拆成$m/n$ 与 $m\%n$

dp转移是$$dp[i][j]=\ dp[i-1][j-k]* \ tmp[0/1][k]$$

对于[1,m%n]的情况,$tmp[1][k]=C(n,m/n 1)$

否则就是$tmp[0][k]=C(n,m/n)$

 

B. array

一眼看错题。

其实题目的意思是：选择一个k，满足所有[k,i]之间的j，都有$a[k]<=a[j]<=a[i]$

那么首先提炼出来我们要找i作为最大值的区间的最小值的最小位置对吧。

如果暴力找的话用单调栈 ST表维护复杂度$O(n*log\ n)$过不去的。

然后就是很神奇的算法优化了。

我们考虑单调栈寻找区间最大值的过程。

for(int i=1;i<=n;  i){        while(top&&A[sta[top]]<=A[i]) top--;        sta[  top]=i;    }

有没有方法使得最小值能够继承呢？仔细思考。

我们发现：对于当前i能被挤出去的点的最大值区间，一定属于i的最大值区间。这不显然吗

那么我们既然要找的是i的最大值区间的最小值（忘了的看上边），是不是可以从很多个它挤出去的区间中合并出一个答案呢？

顺着这个思路，我们慢慢解决了这个问题。

具体的，就是将每个点记录一个数组$Nxt$表示$ \(上一个栈里的元素,i]\ $之间的最小值的最小下标。

每个点的Nxt初始设为它自己。

实际上每个点最后的Nxt就是它的答案的$k$。

那么当i节点挤出top节点时，我们判断一下top节点的Nxt的值是否比i节点的Nxt值小于等于，如果是，就更新i节点的Nxt。

并且由于我们是正向枚举的，就保证了Nxt如果能更新，值和下标就一定单调不增。

代码也就加了一句话，非常简单。

for(int i=1;i<=n;  i){        while(top&&A[sta[top]]<=A[i]) (A[nxt[sta[top]]]<=A[nxt[i]])?nxt[i]=min(nxt[i],nxt[sta[top]]):0,top--;        sta[  top]=i;    }

 

但是比较难想，我想了很久。

不要盲从于题解，如果认为题解不够优秀（比如我）不妨大胆破旧。

还是要把思路打开。

 

 

C. ants

一眼莫队线段树，丝毫没有意识到这是一道原题。

原到什么程度呢，就是说把那道题的代码放到这里，直接AC

话说那道原题我还写过莫队线段树的题解...

现在就因为当时水题掉RP了吧...

正解：回滚莫队。

考虑对于这种添加元素好添加，删除不好删除的情况，莫队的复杂度会生一个档次。

尤其是我们的修改操作还不是$O(1)$的情况下。

那么不妨换个思路进行思考。

为什么我们要用线段树呢？因为添加删除都好搞。

那么如果我们没有了删除，有没有更好的方式来摆脱这个log呢？ZKW如果没有了删除，我们发现其实用并茶几/桶都可以轻松维护连续区间的最大长度。

考虑怎么删除删除操作。

将枚举询问改为枚举块，那么左端点同一个块内的右端点满足单不降。

那么右端点就可以不删除只添加了。考虑左端点。

因为它们都在同一个块内，因此直接暴力每次将这个块的最后到L的所有都添加，然后再记录之前的状态直接回去就好了。

复杂度：每个询问左端点至多移动$O( \sqrt{n})$次，右端点单增不影响复杂度。

总复杂度:$$O(\ n* \sqrt{n})$$

以后用奇迹银桥水过的题一定要看看正解啊qaq...

 

来源：https://www.icode9.com/content-4-504201.html