cf138c-题解
题单介绍
[博客](https://www.luogu.com.cn/blog/87799/solution-cf138c)
[暂无更新]
# 题目
(读了翻译发现没看懂,最后看了英语原文+请教教练才看懂,所以给大家解释一下题目大意(不逐字对应,只解释大意))
## 题目大意
一条直线上有n棵树和m个蘑菇。第i棵树所在位置为a[i]有l[i]的概率往左倒,r[i]的概率往右倒,也可以不倒,倒地可以摧毁h[i]长度的地面(往左倒可以摧毁$a[i]-h[i]<=x<a[i]$的地面,往右倒可摧毁$a[i]<x<=a[i]+h$的地面,**a[i]不会被摧毁**)。如果蘑菇所在的地面被摧毁那么蘑菇也没了。 $\color{red}\text{注意不等式的符号有没有取到等号。}$
第i个蘑菇的位置位于b[i],权值为z[i],求摧毁后剩下的蘑菇的期望权值和。
## 输入
第1行1个整数n,m,分别表示树和蘑菇的个数。
接下来n行,每行4个整数,a[i],h[i],l[i],r[i],分别表示位置,摧毁的长度,往左和右倒的概率**百分比**(50表示50%即0.5) $\color{red}\text{注意概率是百分比!}$
## 输出
一个小(分)数,代表期望权值和。要求误差(即答案与输出差的绝对值)<=0.0001。
## 样例解释即说明
### \#1
第1棵树有50%的概率往左倒(即覆盖0<=x<2的区间),蘑菇在位置1,权值为1。所以期望权值和为1×0.5=0.5。
### \#2
第1棵树有50%的概率往右倒,第2棵有50%的概率往左倒,所以概率为1×0.5×0.5=0.25。
### 说明
测试点#12是一个有$10^{5}$棵树,1个蘑菇的大测试点。
注:所有变量和数组均与原题规定得一样,数据范围自行看原题。
# 暴力
枚举每棵树,计算每个点不被摧毁的概率。
对于每棵树,我们分别处理往左倒和往右倒,这样就拆成了2个区间分别处理。
概率计算方法为在所有树倒下时,不被摧毁的概率积。暴力把每个点都×l[i]或r[i],最后将sum加上所有蘑菇所在的点的概率×权值。
如果对计算方法有疑问,可以看样例解释。
时间复杂度为$O(sum{h[i]×2}),-10^{9}<=h[i]<=10^{9},n<=10^{5}$,所以最坏复杂度约$2×10^{14}$。
# 优化1
由于我们是区间修改,修改完之后全部求,所以可以利用前缀和的思想。(当然这里是求积)
设一个s数组,对于左端点,标记×l[i],(右端点+1)标记为÷l[i],最后跑一边前缀和(即```s[i]*=s[i-1]```)然后就可以求出每个点的概率,最后在枚举蘑菇求答案。
时间复杂度为O(max{h[i]}-min{h[i]}),最坏情况有$2\times 10^{9}$。
# 优化2(正解)
观察优化1的过程,我们发现当h差别很大时,中间有一堆元素的值时一样的,所以对这些一样的元素进行操作,完全是浪费时间和空间。我们怎么样避免操作重复的元素呢?
什么元素才会有一段重复?
在两个端点之间,不会有任何的标记,这两个端点之间的值肯定是一样的。
怎么办?
那我们可以将左端点右端点都放入一个数组中,排一遍序,然后端点中间的就可以不管它了。
时间复杂度$O(4n\times log_{2}(4n)+2n+n+m)$ (加号4边分别为排序,标记,前缀和的时间)
但是此时空间复杂度还是没有优化,所以就算不tle,空间也会让你mle或ce(不能开那么大的数组)。
我们优化了时间,就有中间的一大段空间空在那里,我们可以省去中间的空间,可以理解为把数组下标重新编号,使其跳过中间空着的空间,只管端点。
此时我们把数组重新编号了,蘑菇就不好找了,所以我们要把蘑菇也放入数组排序。
有点类似于离散化,不同的是不用把数组里的元素重新改,仅把s数组重新编号。
# 算法示例
讲了这么多,感觉自己讲得不好,大家可能没听懂,那就拿一个数据来演示优化2。
```
2 1
200 200 50 50
400 200 50 50
300 100
```
为方便,用a~b表示a<=x<=b
有4个区间:0~100,300~400,200~300,500~600
将所以数放入一个数组排序。排序完的结果:0,100,100,200,300,300,400,500,600
然后放入s数组并跑前缀和:
| |0|1|2|3|4|5|6|7|8|9|10| | | |
| -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: |
|数组里的数|0|100|100|200|300|300|400|500|600| | | | ||
|标记|×0.5||÷0.5|×0.5|×0.5||÷0.5|÷0.5×0.5||÷0.5|| | | |
## 细节
讲解一些我wa过的点为什么WA。
\#3:必须用(1-输入÷100)才是不被摧毁的概率。
\#5:特判除数为0的情况。
\#6:排序数值一样时的顺序问题,在代码里讲解。
\#9:第一个是蘑菇时没有计算。
\#12:
精度问题。double只能存小数300多位。所以如果有数据让你前面一直÷,就会爆精度。提供一个数据让你爆精度。(太大了,用c++程序生成,在iakioi.in中打开)
```cpp
#include<iostream>
using namespace std;
int main(){
freopen("iakioi.in","w",stdout);
int i;
cout<<"100000 1"<<endl;
for(i=0;i<100000;i++){
cout<<0<<" "<<i<<" "<<100<<" "<<0<<endl;
}
cout<<"0 1";
return 0;
}
```
所以要溢出时×一个数,让它恢复成接近1。当然要记录溢出了几次。因为在向上÷的时候可能会向上溢出,所以这时把溢出的次数-1(相当于反溢出一次)。设这个数是c,eps=$10^{-250}$最后答案就是$ans \times eps^c$
\#12:
但是tle了,所以要卡常,就把cin改为scanf就AC了。
# 代码
```cpp
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
long long a[1000005],h[1000005];
double l[1000005],r[1000005];
long long b[1000005],w[1000005];
struct xyq{ //注:id好像没用,懒得删了。
long long a,id,left; //left表示是哪一种1左端点3右端点2蘑菇。这么编号的原因是排序时数值一样按left的编号排序,先1再2后3,为什么要怎么做,建议自己打一下草稿模拟一下就知道了。我也解释不清。
double ykb; //ykb表示概率(left=1,3)或权值(left=2)
}_[1000005];
struct rule{
bool operator()(const xyq &s1,const xyq &s2){
return s1.a<s2.a||(s1.a==s2.a&&s1.left<s2.left);
}
};
double s[1000005];
#define eps 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 //大约有250位小数,double最多可以存300多位。
int main(){
long long n,m,i,N,tot=0,kkksc03=0;
double sum=0;
cin>>n>>m;
for(i=0;i<n;i++){
scanf("%lld %lld %lf %lf",a+i,h+i,l+i,r+i);
_[i<<2].a=a[i]-h[i];
_[i<<2].id=(i<<1);
_[i<<2].left=1;
_[i<<2].ykb=1.0-l[i]/100.0;
_[i<<2|1].a=a[i]-1;
_[i<<2|1].id=(i<<1);
_[i<<2|1].left=3;
_[i<<2|1].ykb=1.0-l[i]/100.0;
_[i<<2|2].a=a[i]+1;
_[i<<2|2].id=(i<<1|1);
_[i<<2|2].left=1;
_[i<<2|2].ykb=1.0-r[i]/100.0;
_[i<<2|3].a=a[i]+h[i];
_[i<<2|3].id=(i<<1|1);
_[i<<2|3].left=3;
_[i<<2|3].ykb=1.0-r[i]/100.0;
}
for(i=0;i<m;i++){
scanf("%lld %lld",b+i,w+i);
_[(n<<2)+i].a=b[i];
_[(n<<2)+i].id=i;
_[(n<<2)+i].left=2;
_[(n<<2)+i].ykb=w[i];
}
N=(n<<2)+m; //更新数组大小。这样不要没用一次都要计算。
sort(_,_+N,rule());
for(i=0;i<N;i++){
s[i]=1; //初始值是什么都不做。一定是1,因为×1才等于原来的数。
}
for(i=0;i<N;i++){
if(_[i].ykb==0){
_[i].ykb=0.00001; //误差在0.0001之内。这样避免除数为0。
}
if(_[i].left==1){
s[i]*=_[i].ykb;
}
if(_[i].left==3){
s[i+1]/=_[i].ykb;
}
}
for(i=1;i<N;i++){
s[i]*=s[i-1];
if(s[i]<eps){
s[i]*=(1.0/eps); //恢复成1左右。
kkksc03++;
}
if(s[i]>(1.0/eps)){
s[i]*=eps; //反恢复。
kkksc03--;
}
if(_[i].left==2){
sum+=_[i].ykb*s[i]*pow(eps,kkksc03);
}
}
printf("%.10f",sum+_[0].ykb*s[0]*(_[0].left==2)); //计算第1个蘑菇,因为我数组下标喜欢从0开始,第1个没有循环到。
return 0;
}
```