G-Wind
Time Limit : 3000/2000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 123 Accepted Submission(s) : 13
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
N棵树和M个蘑菇排成一排. 每棵树有自己的坐标和高度, 每个蘑菇有自己的坐标和权值. 一阵大风刮来, 每棵树有Li%的概率往左边倒, 有Ri%的概率往右边倒, 有(1 – Li% - Ri%)的概率不倒. 如果一棵高度为H坐标为X的树往左边倒下, 那么坐标在区间[X – H, X)内的蘑菇就会被砸到, 如果往右边倒下, 那么坐标在区间(X, X + H]内的蘑菇就会被砸到. 求不被树砸到的所有的蘑菇的权值之和的期望值。
Input
第一行包含2个整数N, M.
接下来N行, 每行4个整数X, H, L, R. 表示这棵树的坐标, 高度和往左右倒的概率. 即这棵树有L%的概率往左倒, R%的概率往右倒.
接下来M行, 每行2个整数Y, W. 表示这个蘑菇的坐标和权值.
[数据范围]
对于20% 的数据, 1 <= N, M <= 1000;
对于100% 的数据, 1 <= N <= 10^5, 1 <= M <= 10^4, 树和蘑菇的坐标的绝对值不超过10^9, 树的高度在[1, 10^9]范围内, 每个蘑菇的权值在[1, 1000]范围内, 每棵树的L,R 满足 0 <= L, R, L + R <= 100.
接下来N行, 每行4个整数X, H, L, R. 表示这棵树的坐标, 高度和往左右倒的概率. 即这棵树有L%的概率往左倒, R%的概率往右倒.
接下来M行, 每行2个整数Y, W. 表示这个蘑菇的坐标和权值.
[数据范围]
对于20% 的数据, 1 <= N, M <= 1000;
对于100% 的数据, 1 <= N <= 10^5, 1 <= M <= 10^4, 树和蘑菇的坐标的绝对值不超过10^9, 树的高度在[1, 10^9]范围内, 每个蘑菇的权值在[1, 1000]范围内, 每棵树的L,R 满足 0 <= L, R, L + R <= 100.
Output
输出一个整数, 为最后答案. 保留4位小数.
Sample Input
1 1 2 2 50 50 1 1
Sample Output
0.5000
概率论忘记的差不多了，而且对于期望方差标准差我是完全不记得了..
期望，方差在这里。关于这些背景知识 将来有时间的话 我一定要好好恶补一下。
这题的期望就是 E=∑xi*pi,这个公式了。
开始写了个纯暴力，先枚举蘑菇，再枚举树。大概10s左右。
后面修改了一下，树的区间排序（发现排序完全没效果，以后要注意这种二维排序的局限性，排区间右端不能约束区间左端的变化，所以不能轻易break.），枚举树时用二分查，但是不能break。用时3.75s。
询问了下学妹，说纯暴力... 先树再蘑菇。想想也是，蘑菇是1维的，break起来很方便..
写了个..3.00s. 这就相当郁闷了。
再自己写了个二分查，优化到了time:0.265000。嗯...算是完成任务了.
PS:标程写得真烂！
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<time.h>
using namespace std;struct tree
{int x,h;double l,r;
}t[111111];struct segment
{int l,r;double p;
}seg[222222];struct node
{int x,v;
}no[11111];bool cmp( node a,node b )
{return a.x<b.x;
}int bisearch( int x,int n )
{int l=0,r=n,m;while( m=(l+r)/2,l<r ){if( no[m].x>x )r=m-1;elsel=m+1;}return m;
}int main()
{freopen( "Wind7.in","r",stdin );freopen( "date.out","w",stdout );int n,m;clock_t start,end;double time;start=clock();while( scanf("%d %d",&n,&m)!=EOF ){for( int i=0;i<n;i++ ){scanf( "%d %d %lf %lf",&t[i].x,&t[i].h,&t[i].l,&t[i].r );t[i].r/=100;t[i].l/=100;}for( int i=0;i<m;i++ )scanf( "%d %d",&no[i].x,&no[i].v );sort( no,no+m,cmp );double ans=0,p;/**for( int i=0;i<m;i++ ){p=1;int j=bisearch(no[i].x,2*n );for( ;j<n*2;j++ ){/**if( no[i].x>=t[j].x-t[j].h && no[i].x<=t[j].x )p*=1-t[j].l;else if( no[i].x>=t[j].x && no[i].x<=t[j].x+t[j].h )p*=1-t[j].r;/if( no[i].x>=seg[j].l && no[i].x<=seg[j].r )p*=1-seg[j].p;//if( no[i].x<seg[j].l )// break;}ans+=p*no[i].v;}*/double a[11111];for( int i=0;i<m;i++ )a[i]=1;for( int i=0;i<n;i++ ){int j=bisearch(t[i].x-t[i].h,m);for( ;j<m;j++ ){if( t[i].x-t[i].h<=no[j].x && no[j].x<t[i].x )a[j]*=1-t[i].l;if( t[i].x<no[j].x && no[j].x<=t[i].x+t[i].h )a[j]*=1-t[i].r;if( no[j].x>t[i].x+t[i].h )break;}}for( int i=0;i<m;i++ )ans+=a[i]*no[i].v;printf( "%.4lf\n",ans );}end=clock();time=(double)(end-start)/CLOCKS_PER_SEC;printf( "time:%lf\n",time );return 0;
}