终于变黄了！
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
西月弦 阅读(272)
评论(0) 编辑 收藏 引用