BZOJ 4574 [Zjoi2016] 线段树

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4574

题意：一个序列，q 次操作，等概率选一个区间覆盖成这个区间的最大值，求最后每个数的期望。

之前模拟赛做到了这个题... 写了正解惨遭卡常剩 80...

我们考虑到与其枚举所有状态去记录贡献，显然枚举每个位置，记录有多少个状态对它做出了贡献是更优的。所以对于每个位置 x，我们都可以找到一个它的唯一“最大贡献区间”[l,r] 满足 [l,r] 是包含 x 且 [l,r] 中所有元素都小于等于 x 的极大区间。无论进行多少次操作，x 只能覆盖区间 [l,r] 中的元素，那么我们可以枚举每个 x，对区间 [l,r] 统计答案。

考虑怎么记录这个答案，朴素的想法是 dp[i][j][k] 表示 i 次覆盖后，区间 [j,k] 等于 a[x] 的方案数。
不过这么做是不好办的，因为虽然 [l,r] 将整个序列分成了可以单独统计答案的三段，但是这样的话区间 [l,r] 内部的答案是不好统计的：因为把一个位置 y 覆盖成了 a[x]，既可能是一下子覆盖了一个区间 [x,y]，也可能是如覆盖 [x,x'],[x',x''],[x'',y] 这样一步一步走过去的。

所以我们换一个思路，dp[i][j][k] 表示第 i 次覆盖后，区间 [j,k] 均小于等于 a[x] 的方案数。这样做有什么好处呢？区间 [l,r] 内的覆盖都可以随便做了

于是我们考虑怎么转移：

已知覆盖 i 次的答案，现在考虑第 i+1 次：
若第 i+1 次的覆盖区间 [l',r'] 为区间 [1,l-1],[l,r],[r+1,n] 的任意一个子区间，显然合法，所以答案乘这三个区间的子区间数的和。
现在考虑跨越 l,r 的覆盖：
①：若完全覆盖区间 [l,r]，显然已经不合法，不需要考虑。
②：若覆盖区间端点 l，则我们可以枚举这个区间的右端点 right，显然 right∈[l,r-1] ，同时区间左端点可以在 [1,l-1] 中随意选择。
因为 a[l-1] 肯定是大于 a[x] 的，只要这个区间覆盖了 a[l-1]，那么这个区间一定会变得比 a[x] 大
③：若覆盖区间端点 r，同理，枚举区间左端点即可。

然后就可以统计答案了，统计的过程可以差分优化。
由于我们 dp 状态设计的是一个前缀和的形式，解除的答案实质上也是一个列前缀和的形式。

sol 是以前写的... 哪里错了随便骂我 T.T

#include <cmath>
#include <queue>
#include <cstdio>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 410
#define ll long long
#define mod 1000000007
#define ADD(a, b) ((a += b) >= mod ? a -= mod : a)
#define R register
using namespace std;
char xB[1<<15],*xS=xB,*xT=xB;
#define getchar() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)
inline int read() 
{ 
    int x=0,f=1;char ch=getchar(); 
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 
    return x*f; 
}
struct zgz
{
    int x,id;
}b[N];
bool cmp(const zgz &a,const zgz &b)
{return a.x<b.x;}
int n,m;
int a[N],c[N],bin[N],cnt,now;
ll sum[N][N],dp[2][N][N];
ll ans[N];
void cal(int l,int r,int pos)
{
    for(R int i=l;i<=r;++i)
    for(R int j=i;j<=r;++j)
    dp[0][i][j]=0;
    dp[0][l][r]=1;
    now=1;
    for(R int i=1;i<=m;++i)
    {
        for(R int j=l;j<=r;++j)
        for(R int k=j;k<=r;++k)
        dp[now][j][k]=(dp[now^1][j][k]*(bin[j-1]+bin[n-k]+bin[k-j+1]))%mod;
        
        for(R int j=l;j<=r;++j)
        {
            ll tmp=0;
            for(R int k=r;k>=j;--k)
            {
                dp[now][j][k]+=tmp;
                tmp+=dp[now^1][j][k]*(n-k);              
            }
        }
          
        for(R int k=r;k>=l;--k)
        {
            ll tmp=0;
            for(R int j=l;j<=k;++j)
            {
                (dp[now][j][k]+=tmp)%=mod;
                tmp+=dp[now^1][j][k]*(j-1);
            }
        }
        now^=1;
    }
    for(R int i=l;i<=r;++i)
    for(R int j=i;j<=r;++j)
    {
        ADD(sum[i][pos],dp[now^1][i][j]);
        ADD(sum[j+1][pos],mod-dp[now^1][i][j]);
    }
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)bin[i]=(i*(i+1)>>1)%mod;
    for(int i=1;i<=n;i++)
    c[i]=b[i].x=read(),b[i].id=i;
    sort(b+1,b+n+1,cmp);
    for(int i=1;i<=n;i++)
    a[b[i].id]=i;
    for(int i=1;i<=n;i++)
    {
        int l=i,r=i;
        while(l>1&&a[l-1]<=a[i])l--;
        while(r<n&&a[r+1]<=a[i])r++;
        cal(l,r,a[i]);
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    ADD(sum[i][j],sum[i-1][j]);
    for(int i=1;i<=n;i++)
    {
        ll tmp=0;
        for(int j=1;j<=n;j++)
        if(sum[i][j])
        {
            (ans[i]+=(sum[i][j]-tmp)*c[b[j].id])%=mod;
            tmp=sum[i][j];
        }
        (ans[i]+=mod)%=mod;
    }
    printf("%lld",ans[1]);
    for(int i=2;i<=n;i++)
    printf(" %lld",ans[i]);
}

100

101

102

103

104

105

106

107

108

#include <cmath>

#include <queue>

#include <cstdio>

#include <iomanip>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 410

#define ll long long

#define mod 1000000007

#define ADD(a, b) ((a += b) >= mod ? a -= mod : a)

#define R register

using namespace std;

char xB[1<<15],*xS=xB,*xT=xB;

#define getchar() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

struct zgz

{

int x,id;

}b[N];

bool cmp(const zgz &a,const zgz &b)

{return a.x<b.x;}

int n,m;

int a[N],c[N],bin[N],cnt,now;

ll sum[N][N],dp[2][N][N];

ll ans[N];

void cal(int l,int r,int pos)

{

for(R int i=l;i<=r;++i)

for(R int j=i;j<=r;++j)

dp[0][i][j]=0;

dp[0][l][r]=1;

now=1;

for(R int i=1;i<=m;++i)

{

for(R int j=l;j<=r;++j)

for(R int k=j;k<=r;++k)

dp[now][j][k]=(dp[now^1][j][k]*(bin[j-1]+bin[n-k]+bin[k-j+1]))%mod;

for(R int j=l;j<=r;++j)

{

ll tmp=0;

for(R int k=r;k>=j;--k)

{

dp[now][j][k]+=tmp;

tmp+=dp[now^1][j][k]*(n-k);

}

for(R int k=r;k>=l;--k)

{

ll tmp=0;

for(R int j=l;j<=k;++j)

{

(dp[now][j][k]+=tmp)%=mod;

tmp+=dp[now^1][j][k]*(j-1);

}

now^=1;

}

for(R int i=l;i<=r;++i)

for(R int j=i;j<=r;++j)

{

ADD(sum[i][pos],dp[now^1][i][j]);

ADD(sum[j+1][pos],mod-dp[now^1][i][j]);

}

int main()

{

n=read(),m=read();

for(int i=1;i<=n;i++)bin[i]=(i*(i+1)>>1)%mod;

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

c[i]=b[i].x=read(),b[i].id=i;

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

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

a[b[i].id]=i;

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

{

int l=i,r=i;

while(l>1&&a[l-1]<=a[i])l--;

while(r<n&&a[r+1]<=a[i])r++;

cal(l,r,a[i]);

}

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

for(int j=1;j<=n;j++)

ADD(sum[i][j],sum[i-1][j]);

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

{

ll tmp=0;

for(int j=1;j<=n;j++)

if(sum[i][j])

{

(ans[i]+=(sum[i][j]-tmp)*c[b[j].id])%=mod;

tmp=sum[i][j];

}

(ans[i]+=mod)%=mod;

}

printf("%lld",ans[1]);

for(int i=2;i<=n;i++)

printf(" %lld",ans[i]);

}

zgz233

zgz233

BZOJ 4574 [Zjoi2016] 线段树

l1ll5

Comments | NOTHING