2010年10月29日
摘要: 解題報告請看 hi.baidu.com/fatboy_cw,貌似這個blog就沒寫多少東西OpenWings就解散了,哀悼...
1/**//* 2 * Author: fatboy_cw 3 * Created Time: 2010/10/25&...
閱讀全文
posted @
2010-10-29 10:53 OpenWings 閱讀(457) |
評論 (5) |
編輯 收藏
2010年8月7日
摘要: 赤裸裸的最小點權覆蓋,不過G++居然不支持%lf...改交C++或者改%f過了...順便提醒OpenWings各位果斷發博啊...貌似最近我太墮落了...嗯.
codeCode highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighli...
閱讀全文
posted @
2010-08-07 22:54 OpenWings 閱讀(306) |
評論 (0) |
編輯 收藏
2010年8月2日
比賽時候無人ac賽后我過掉了。感覺還是一個很不錯的分數規劃,主要精髓在第一步的分數式轉換上。
題目是POJ3757。
開始看題感覺頭疼的地方是要求同時完成。這里有一個很精髓的轉換，把流量換為速度。假設最終時間為t,那么對于每個被選中的服務器,速度vi=fi/t=bp/(b+p),兩邊求和t=sigma(fi)/sigma(vi)=F/sigma(vi),然后最后要求總花費最小,每個被選中的服務器的花費為fi*ci=vi*ti*ci。兩個式子有可以推出對于選出的K個服務器,
sigma(vi*ti)=sigma(fi)=F,sigma(fi*ci)=sigma(vi*ti*ci),將ti=F/sigma(vi)帶入式子。總花費cost=F*sigma(vi*ci)/sigma(vi),這樣就轉換成了標準的分數規劃了~
code
1
#include <iostream>
2#include <cstdio>
3#include <algorithm>
4#include <cstring>
5#include <cmath>
6using namespace std;
7
8int N,K;
9double F,ans;
10
11struct Sever
{
12
double pi,bi,ci,xi,vi,value;
13
bool operator < (const Sever &A) const {
14 return value<A.value;
15
}
16
}sever[20005];
17
18bool bigger(double mid){
19 int i;
20 for(i=0;i<N;i++){
21 sever[i].value=F*sever[i].xi-mid*sever[i].vi;
22 }
23 sort(sever,sever+N);
24 double sum=0;
25 for(i=0;i<K;i++){
26 sum+=sever[i].value;
27 }
28 if(sum<0) return true;
29 return false;
30}
31
32int main(){
33 scanf("%d%d",&N,&K);
34 scanf("%lf",&F);
35 int i;
36 for(i=0;i<N;i++){
37 scanf("%lf%lf%lf",&sever[i].pi,&sever[i].bi,&sever[i].ci);
38 sever[i].vi=sever[i].bi*sever[i].pi/(sever[i].pi+sever[i].bi);
39 sever[i].xi=sever[i].vi*sever[i].ci;
40 }
41 double l=0.0,r=1e10+1,mid;
42 while(r-l>1e-5){
43 mid=(l+r)/2;
44 if(bigger(mid)){
45 r=mid;
46 }
47 else{
48 l=mid;
49 }
50 }
51 printf("%.4lf\n",mid);
52 return 0;
53}
54posted @
2010-08-02 11:14 OpenWings 閱讀(230) |
評論 (0) |
編輯 收藏
2010年8月1日
摘要: 把自己原來做過的幾道感覺不錯的圖論題貼過來。 [無向圖點雙][POJ2942]Knights of the Round Table題目大意:有N個騎士,給出有兩兩之間有仇恨的關系,要求安排一種環形座次使得總人數為奇數而且其實之間不會發生沖突。
題解:首...
閱讀全文
posted @
2010-08-01 19:55 OpenWings 閱讀(335) |
評論 (0) |
編輯 收藏
本來寫了一個文采飛揚的article來作為OpenWings的開門article的,不過最后感覺太有文采了于是還是del掉了...
從TigerWings到OpenWings,從當初我們期盼的"如虎添翼"到現在的展開雙翅的翱翔,我們所改變的絕不僅僅是隊名。從杭州邀請賽和金牌擦肩之后,我在想,盡管我們大家都沒有參加過正式比賽,但是我們不比任何人缺少激情與夢想,金牌對于我們來說,只是努力與否的問題。暑假集訓,對于我們每個人來說都是一個絕好的機會。這一個月的時間很可能不知不覺白白過去,但是如果抓住這一個月的時間付出自己所應該付出的努力,最后得到的可能是一個出乎所有人意料的驚喜。
ps:從現在看我的狀態比較飄忽,題目難度類型的不同對自己左右比較大。所以計劃開始做一些專題訓練,比如圖論專題數論專題之類的。另外目前隊里沒有人懂計算幾何啊啊啊啊,找個機會一起做一些計算幾何專題吧。最后說一下,大家有啥想法或者有啥解題報告統統的發上來吧,over。
posted @
2010-08-01 19:45 OpenWings 閱讀(193) |
評論 (0) |
編輯 收藏