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 阅读(425) |
评论 (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 阅读(281) |
评论 (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 阅读(183) |
评论 (0) |
编辑 收藏
2010年8月1日
摘要: 把自己原来做过的几道感觉不错的图论题贴过来。 [无向图点双][POJ2942]Knights of the Round Table题目大意:有N个骑士,给出有两两之间有仇恨的关系,要求安排一种环形座次使得总人数为奇数而且其实之间不会发生冲突。
题解:首...
阅读全文
posted @
2010-08-01 19:55 OpenWings 阅读(290) |
评论 (0) |
编辑 收藏
本来写了一个文采飞扬的article来作为OpenWings的开门article的,不过最后感觉太有文采了于是还是del掉了...
从TigerWings到OpenWings,从当初我们期盼的"如虎添翼"到现在的展开双翅的翱翔,我们所改变的绝不仅仅是队名。从杭州邀请赛和金牌擦肩之后,我在想,尽管我们大家都没有参加过正式比赛,但是我们不比任何人缺少激情与梦想,金牌对于我们来说,只是努力与否的问题。暑假集训,对于我们每个人来说都是一个绝好的机会。这一个月的时间很可能不知不觉白白过去,但是如果抓住这一个月的时间付出自己所应该付出的努力,最后得到的可能是一个出乎所有人意料的惊喜。
ps:从现在看我的状态比较飘忽,题目难度类型的不同对自己左右比较大。所以计划开始做一些专题训练,比如图论专题数论专题之类的。另外目前队里没有人懂计算几何啊啊啊啊,找个机会一起做一些计算几何专题吧。最后说一下,大家有啥想法或者有啥解题报告统统的发上来吧,over。
posted @
2010-08-01 19:45 OpenWings 阅读(153) |
评论 (0) |
编辑 收藏