本文共 1518 字，大约阅读时间需要 5 分钟。

正题

题目链接:

题目大意

$n$个数的序列，每个数是$[1..x]$中的一个，有$q$个区间$[l..r]$，求所有区间最小值的最大值的期望。

解题思路

首先如果一个区间包含别的区间，那么这个区间显然不需要考虑，所以去掉后左端点和右端点同时递增，考虑最大值不超过$i$的方案$h_i$，定义$g_i$表示放$i$个点，每个区间至少包括一个点的方案。

然后$f_{i,j}$表示前$i$个位置，$i$有点，总共放了$j$个点的方案，考虑转移，$k->j$时要保证$k\sim i$这个区间内没有一个完整的区间，预处理好后有$$f_{i,j}=\sum f_{k,j-1}$$

我们发现$k$的取值是一段区间，前缀和优化即可。

$code$

#include
   
    #include
    
     #include
     
      #define ll long longusing namespace std;const ll N=2100,XJQ=666623333;struct node{
   	ll l,r;}a[N],b[N];ll n,x,q,f[N][N],s[N][N],fl[N],fr[N],h[N],g[N],tot,ans;bool cmp(node x,node y){
   return (x.l==y.l)?(x.r
      
       
        >=1;	}	return ans;}int main(){
   	scanf("%lld%lld%lld",&n,&x,&q);	for(ll i=1;i<=q;i++)		scanf("%lld%lld",&b[i].l,&b[i].r);	sort(b+1,b+1+q,cmp);	for(ll i=1;i<=q;i++){
   		if(i>1&&b[i].l==b[i-1].l)continue;		while(tot&&a[tot].r>=b[i].r)tot--;		a[++tot]=b[i];	}	memset(fl,0x3f,sizeof(fl));	memset(fr,0xcf,sizeof(fr));	for(ll i=1;i<=tot;i++)			for(ll j=a[i].l;j<=a[i].r;j++)			fl[j]=min(fl[j],i),fr[j]=max(fr[j],i);	ll l=0;fl[0]=fr[0]=0;	for(int i=1;i<=n;i++)		if(fr[i]<0)fl[i]=l+1,fr[i]=l;		else l=max(l,fr[i]);	l=0;f[0][0]=s[0][0]=1;	for(ll i=1;i<=n;i++){
   		while(l
        
         
          =1;i--) h[i]=(h[i]-h[i-1]+XJQ)%XJQ; for(ll i=1;i<=n;i++) ans=(ans+h[i]*i%XJQ*z%XJQ)%XJQ; printf("%lld",ans);}
         
        
       
      
     
    
   

转载地址：http://rfwaf.baihongyu.com/