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

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 4574 [Zjoi2016] 线段树


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,