終于變黃了！
250pt
有兩根木棍，木棍A長度是[1,NA]的隨機(jī)整數(shù)，木棍B長度是[1,NB]的隨機(jī)整數(shù)（NA,NB<100,000）。兩根木棍底部對(duì)齊平行放置，距離為W。求木棍頂部間距的期望。
算法分析:
既然寬度確定了，我們枚舉木棍的高度差就可以了。
易疵點(diǎn)就是整形溢出。
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
有一個(gè)H*W的矩形（W,H <= 1,000,000）。每個(gè)格子i,j的值是i*W+j。 給一個(gè)數(shù)S(S<1,000,000,000,000)。求子矩陣的和為S的最小面積是多少？
算法分析：
首先估算出面積最大的數(shù)量級(jí)在10^6，于是考慮枚舉（又是枚舉）。。。。
枚舉量應(yīng)該是size + size/2 + size/3 + ... + size/size = size * log (size) 調(diào)和級(jí)數(shù)啊啊啊。。。。
枚舉出長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
西月弦 閱讀(283)
評(píng)論(0) 編輯 收藏 引用