算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
终于变黄了!

250pt

    有两根木棍,木棍A长度是[1,NA]的随机整数,木棍B长度是[1,NB]的随机整数(NA,NB<100,000)。两根木棍底部对齐平行放置,距离为W。求木棍顶部间距的期望。

算法分析:

    既然宽度确定了,我们枚举木棍的高度差就可以了。
    易疵点就是整形溢出。
 1 #include<iostream>
 2 #include<cmath>
 3 using namespace std; 
 4 class Pillars{
 5     public : double getExpectedLength(int w, int x, int y){
 6         int n = max(x,y);
 7         double ans = 0;
 8         ans += min(x,y) * sqrt((double)w*w);
 9         for(int i=1;i<n;i++){
10             double v = max(0, min(x-i,y)) +max(0, min(y-i,x));
11         //    cout<<i<<" "<<v<<endl;
12             ans += v*sqrt((double)i*i + w*w);
13         }
14         ans /= (double) x*y;
15         //cout<<ans<<endl;
16         return ans;
17     }
18 };

500pt

    有一个H*W的矩形(W,H <= 1,000,000)。每个格子i,j的值是i*W+j。 给一个数S(S<1,000,000,000,000)。求子矩阵的和为S的最小面积是多少?

算法分析:

    首先估算出面积最大的数量级在10^6,于是考虑枚举(又是枚举)。。。。
    枚举量应该是size + size/2 + size/3 + ... + size/size = size * log (size) 调和级数啊啊啊。。。。
    枚举出长h,宽w之后,利用公式反代出最左上角的值。
 1 #include<iostream>
 2 using namespace std;
 3 typedef long long ll;
 4 class RectangularSum{
 5     public : ll minimalArea(int H,int W,ll s){
 6         ll n = 1, ans = -1;
 7         for(;n*(n-1)/2<s;n++);
 8     //    cout<<n<<endl;
 9         for(ll w=1; w<=n; w++){
10             if(w > W) break;
11             for(ll h =1; h*w <=n; h++){
12                 if(h > H) break;
13                 ll t = W*w*(h-1)*h/2 + h*(w-1)*w/2;
14                 ll val = s-t;
15                 if(w==3 && h==3) cout<<val<<endl;
16                 if(val >=0 && val % (w*h)==0){
17                     ll x = val / (h*w);
18                     if( x/W + h <= H && x % W + w <= W){
19         //                cout<<x<<" "<<h<<" "<<w<<endl;
20                         if(ans == -1 || ans > w*h) ans = w*h;
21                     }
22                 }
23             }
24         }
25         return ans;
26     }
27 };
posted on 2012-06-26 13:36 西月弦 阅读(258) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理