Topcoder SRM 547 Div1 250 - c++编程基础

TOP

Topcoder SRM 547 Div1 250

2015-07-20 17:13:39 来源: 作者: 【大中小】浏览:2次

Problem

On a horizontal line, there are two vertical pillars. The distance between their bottoms is w . The height of the first pillar is an integer, chosen uniformly at random in the range 1 through x , inclusive. The height of the second pillar is an integer, chosen uniformly at random in the range 1 through y , inclusive. The tops of both pillars will be connected by a straight piece of rope.

You are given the ints w , x , and y . Compute and return the expected length of the rope.

Limits

TimeLimit(ms):2000

MemoryLimit(MB):64

w∈[1,1000]

x,y∈[1,105]

Solution

枚举绳子的长度 L ，统计期望。

EXP=∑iLi×Nitotal ，其中 Ni 表示不同绳子长度出现的次数， total 表示总次数， total=x×y

发现 L=w2+dh2￣￣￣￣￣￣￣￣￣√ ，其中 dh=abs(h1?h2) ，表示两个杆子高度的差值。因此，枚举 dh 即可。

下面需要处理 Ni 。对于不同的 h1 ，与 h2 的差值 dh 是一段或两段连续的区间，因此只需要在这段区间上的 Ni+=1 即可。用两个标记数组，先标记最后统计的方法，可以在 O(max(x,y)) 的时间内算出 Ni

Complexity

TimeComplexity:O(max(x,y))

MemoryComplexity:O(max(x,y))

My Code

//Hello. I'm Peter.
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #include
                
                  #include
                 
                   #include
                   using namespace std; typedef long long ll; typedef long double ld; #define peter cout<<"i am peter"<
                   
                     b; i--) #define repin(i, a, b) for (int i = a; i <= b; i++) #define depin(i, a, b) for (int i = a; i >= b; i--) #define pi 3.1415926535898 #define eps 1e-6 #define MOD 1000000007 #define MAXN #define N 100100 #define M ll add[N],sub[N],res[N]; class Pillars{ public: double sq(double x){ return x*x; } double getExpectedLength(int w, int x, int y){ repin(i,0,max(x,y)){ add[i]=sub[i]=res[i]=0; } int from=0,to=0; repin(h1,1,x){ from=max(1,h1-y); to=h1-1; if(from<=to){ add[from]+=1; sub[to]+=1; } if(y>=h1) res[0]+=1; if(y>h1){ from=1; to=y-h1; add[from]+=1; sub[to]+=1; } } ll now=0; repin(i,1,max(x,y)-1){ now+=add[i]; res[i]=now; now-=sub[i]; } double ans=0.0; repin(i,0,max(x,y)-1){ double t=sqrt(sq(w)+sq(i)); ans+=res[i]*t; } ll sum=(ll)x*(ll)y; ans/=sum; return ans; } };


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：C++ MySql实现个人电话本	下一篇：C++拾遗--函数重载

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: