C++博客-oyjpArt ACM/ICPC算法程序设计空间

期待爱

oyjpart — Fri, 04 Jul 2008 10:56:00 GMT

《期待爱》
林俊杰，金莎

my life 一直在等待
空荡的口袋
想在里面放一份爱
why 总是被打败
真的好无奈
其实我实实在在
不管帅不帅
想要找回来(想要找回来)
自己的节拍(自己的节拍)
所以这一次
我要勇敢大声说出来
期待期待你发现我的爱
无所不在我自然而然的关怀
你的存在( 你的存在)
心灵感应的方向
我一眼就看出来
是因为爱
我猜你早已发现我的爱
绕几个弯靠越近越明白
不要走开( 不要走开)
幸福的开始就是
放手去爱
想要找回来( 想要找回来)
自己的节拍( 自己的节拍)
所以这一次
我要勇敢大声说出来
期待期待你发现我的爱
无所不在我自然而然的关怀
你的存在( 你的存在)
心灵感应的方向
我一眼就看出来
是因为爱
我猜你早已发现我的爱
绕几个弯靠越近越明白
不要走开( 不要走开)
幸福的开始就是
放手去爱
幸福的开始就是放手去爱

写这首歌不是想表达什么，只是确实挺好听的，何况我本来就喜欢林俊杰的声音。

oyjpart 2008-07-04 18:56 发表评论

《the negotiator》

oyjpart — Fri, 27 Jun 2008 19:45:00 GMT

很不错的电影了。个人觉得剧本的出彩和演员的表现都已经相当不错。
这部片子给人以震撼。有类似《达芬奇密码》的效果。

Kevin Spacey，这个在《七宗罪》中极为出彩的高智商罪犯的表演让我觉得很过瘾。
Samuel L. Jackson 一如既往的招风啊，哈哈

结尾稍显仓促。

值得一看。

影片中丹尼·罗马的沉着冷静是非常值得学习的，如果能学会的话。

原名：the negotiator
译名：王牌对王牌
导演：F·加里·格雷(F. Gary Gray)　
演员：塞缪尔·L·杰克逊(Samuel L. Jackson)

　　戴维·莫尔斯(David Morse)

　　罗恩·里夫金(Ron Rifkin)

　　凯文·史派西(Kevin Spacey)

　　约翰·斯潘塞(John Spencer)
发行：华纳兄弟电影公司(Warner Bros.)　
发行时间：1998-01-01　
类型：动作片

【内容简介】
谈判专家的存在就是要找到谈判的弱点并加以利用，但若谈判也是一位谈判专家，谈判将如何进行呢？这部惊险的动作悬疑片是根据美国圣路易斯警察局处理过的一个真实案件改编而成。敬业爱岗的芝加哥警察局的人质谈判专家丹尼·罗马（塞缪尔 L. 杰克逊饰），专门跟绑匪谈判挽救人质的性命。不久前他成功的从一个持枪的父亲手中解救出被劫持的小女孩，从而受到上司和媒体的一致赞扬。现在与老搭档又回到原来的工作岗位上并向他的新婚妻子凯琳（丽贾娜·泰勒）保证不再加班每天都回家吃晚饭。后来他的搭档因为涉嫌侵吞公款而被扣押在警察局当晚被人杀害。因为丹尼在案发后几秒钟就赶到现场，所以被后来的同事认为是最大的犯罪嫌疑人，局长艾尔·特拉威斯（约翰·斯潘塞）要他交出枪支和警徽。百口莫辩丹尼最终闯入芝加哥的内务部总部把两个工作人员和指挥官弗罗斯特（罗恩·里夫金饰）劫为人质，从而试图从调查员泰伦斯·尼巴姆（J·T· 沃尔什饰，他在影片完成不久后去世）口中问出事情的真相来。然后他叫来一个从另外一个辖区局赶到的外人：同为人质谈判专家的克利斯·萨宾（凯文·史派西饰）。萨宾来到后，两个人就谈判的控制权又发生了激烈的争夺，最终丹尼竭尽全力证明了他遭到了错误指控。

oyjpart 2008-06-28 03:45 发表评论

《In.Bruges》

oyjpart — Thu, 26 Jun 2008 06:45:00 GMT

杀手没有假期.In.Bruges.

Actually we really don't know what life is.
But we can, at least can see kinds of lives.

Life is meaningless indeed
But someday you realize that your life is approaching the end
God will tell you what life is.

◎译　　名　杀手没有假期
◎片　　名　In Bruges
◎年　　代　2008
◎国　　家　英国/比利时
◎类　　别　喜剧/犯罪/剧情
◎语　　言　英语
◎字　　幕　英文/法文/西班牙文
◎IMDB评分 8.1/10 (7,613 votes)
◎IMDB链接 http://www.imdb.com/title/tt0780536
◎文件格式　XviD + MP3
◎视频尺寸　640x272 (2.34:1)
◎文件大小　1CD 49 x 15MB
◎片　　长　107 mins
◎导　　演　Martin McDonagh
◎主　　演　拉尔夫·费因斯 Ralph Fiennes
　　　　　　柯林·法瑞尔 Colin Farrell .....Ray
　　　　　　布莱丹·格里森 Brendan Gleeson .....Ken
　　　　　　塞伦·希德 Ciarán Hinds .....Father McHenry
　　　　　　Clémence Poésy .....Chloe
　　　　　　斯科拉·鲁特 Thekla Reuten .....Marie
　　　　　　Robbie Kay .....Harry aged 7
　　　　　　Hannah Murray
　　　　　　杰瑞米·雷乃 Jérémie Rénier .....Erik
　　　　　　Theo Stevenson .....Tobias
　　　　　　Mark Donovan .....Overweight Man
　　　　　　Jordan Prentice .....Jimmy
　　　　　　艾力克·高敦 Eric Godon .....Yuri
　　　　　　Ann Elsley .....Overweight Woman
　　　　　　Pieter Loosveldt .....Bartender
　　　　　　Rudy Blomme .....Ticket seller
　　　　　　Susan Ateh .....Ken's wife
　　　　　　Emily Thorling .....Overweight Woman

◎简　　介　

　　两名职业杀手雷（柯林·法瑞尔）和肯（布莱丹·格里森），在伦敦刚摆平一桩棘手的任务后，被他们的老板亨利（拉尔夫·费因斯）指示，来到比利时布鲁日度假放松心情，不料却与当地人及游客发生纠纷，假期变成梦魇，他们才发现老板叫他们来度假可能别有用心。

oyjpart 2008-06-26 14:45 发表评论

《The Oxford Murders》

oyjpart — Fri, 20 Jun 2008 13:17:00 GMT

不错的电影，也许你应该自己去尝试着看看。

人是否能得知真理？

有哲学家认为：

人的理性思维是建立在逻辑的基础上的，逻辑学从来就不是到达真理的途径。

不过同样的漏洞在于，这句话的逻辑何在？

电影总归是电影，带引我们思考数理逻辑就已经不错了。

oyjpart 2008-06-20 21:17 发表评论

SRM406 PTS500 FoldThePaper

oyjpart — Wed, 18 Jun 2008 03:29:00 GMT

Problem Statement

You have a rectangular piece of paper that's divided into 1x1 cells, each of which has an integer value. The paper will be described by a vector paper. The ith element of paper will be a space delimited list of integers, where the jth integer of the ith element of paper represents the value of the jth cell of the ith row of the paper.

You want to perform a sequence of folds on the paper, where you may fold anywhere along an axis that is in between two rows or columns of the paper. After performing a fold, we wish to model the folded paper as a new, flat piece of paper. We will do this by considering two overlapping cells as a single cell, with a value that is the sum of the individual cells.

You wish to perform a sequence of folds such that the value of some single cell in the resulting piece of paper is as large as possible. Return this value.

Definition

Class:	FoldThePaper
Method:	getValue
Parameters:	vector
Returns:	int
Method signature:	int getValue(vector paper)
(be sure your method is public)

Constraints

paper will contain between 1 and 12 elements, inclusive.

Each element of paper will be a single-space delimited list of integers with no leading or trailing spaces.

Each element of paper will contain between 1 and 12 integers, inclusive.

Each element of paper will contain the same number of integers.

Each element of paper will contain between 1 and 50 characters, inclusive.

Each integer in paper will be between -100 and 100, inclusive.

Each integer in paper will have no leading zeros.

An integer in paper equal to zero will not have a preceding negative sign.

Examples

{
"1 1 1",
"1 1 1"
}

Returns: 6

We can collapse every cell onto the upper-left cell.

{
"1 -1",
"1 -1"
}

Returns: 2

We should perform only the fold between the two rows, and take the resulting left column.

{
"1 -1 -1 1",
"-1 -1 -1 -1",
"-1 -1 -1 -1",
"1 -1 -1 1"
}

Returns: 4

Folding between the middle rows then the middle columns allows us to combine the four corner cells.

{
"20 13 -2 100",
"-12 0 4 -3",
"4 1 -36 21"
}

Returns: 131

{
"0"
}

Returns: 0

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

题目大意是有一个12*12的矩阵，现在可以对这个矩阵横向或纵向折叠，出在重叠位置的数相加。
求折叠过程中任意位置产生的最大数。

很多大牛fail了，我一个DFS+剪枝也超时了，一共32人pass sys test，1000pts无人ac，此套题难度还是很大的。

基本思路是状态压缩DP，横向(1<<12)*纵向(1<<12)*加和。

但是这样会超时。关键是没有利用到折叠的信息。

预先生成某个位置的状态（由那些位置叠加而来），就可以减少检查量，就可以ac了。

如何生成这些状态呢？没错，又是一个DP. 呵呵。

oyjpart 2008-06-18 11:29 发表评论

无题

oyjpart — Mon, 16 Jun 2008 09:18:00 GMT

很好，很好，再一次天崩地裂了。

oyjpart 2008-06-16 17:18 发表评论

向Roba学习

oyjpart — Mon, 09 Jun 2008 01:11:00 GMT

最近看Roba的博客，觉得Roba博客写的很好。很积极，很开心，很简单，很狡猾。向Roba学习。

oyjpart 2008-06-09 09:11 发表评论

生活

oyjpart — Sat, 07 Jun 2008 15:03:00 GMT

生活

说实话，我本来不是很喜欢写自己的生活的。可是心里积蓄了太多的东西，猛烈撞击着
我的每一处神经，每一处血管都在喷涌。也许我必须要好好整整，否则我很怀疑我还能正常的活下去。唉。

一

先说说最近的生活吧。

一句话，生活总是无情的。说程序吧，这个是我在我的博客上说的最多的东西。5月31日以来，拿了一个Topcoder 0分，第一次拿0分，有点难受。也许每个人都能从自己的失败中找出很多借口来安慰自己，试图让自己的伤口不要太揪心。所以我也能找出很多借口，这个失误啊，那个又是题目怎么怎么了。但是之后得知百度之星23分而告别复赛时，那个心情真不知道该称呼什么。登录到百度看到的是一片“未通过”，血红血红的“未通过”，特吓人。满怀信心的打开网页，却要木然而愤怒地关掉。第二题1-19个Test全错，只对了第20个Test。第三题以为自己写的那个块状链表应该能过掉大部分数据，却只过了5个。第四题则只对了第一个Test。当然当时我写第四个程序的时候就只准备对1个Test。也许我还没适应OI的计分方式, 不会做就不愿意花几分钟的时间写个随机交上去，不会觉得随机居然能拿30分。很好，23分，很好。这一刻的心凉触动了我，映入我眼帘的是似曾相识的南京Regional。

南京赛，对，就是南京赛。这是我的第一场Regional。我们带着刚出生的ARTor队来到南京，渴望能给ARTor添加几分初生的荣誉。结果却抱着可怜的2道题灰溜溜地离开了南京，让ARTor还在摇篮里面就夭折了。非常敬仰非常崇拜Glory.h, 4道题，ICPC排名第四，结束了NUDT无金的历史。但是我自己知道，当ARTor小朋友的和Glory.h对视的那一刹那, ARTor清澈的眼睛里除了泪水,什么也没有。ARTor死了，再也不会出现，再也不会被提起。南京赛回来之后为了不让自己心彻底地冷掉，我是一遍遍告诉自己: 没事的，没事的，只是题目不适合我们。只是我们不会后缀数组不会TrieDP而已，只是我面对百万级的数据不敢去水J题而已。但是我忽视了很多，我敲的A题没有过。而场上的的确确有两个队伍过了A题，我忽视了，连Trie都不会的孩子，走到Regional赛场上注定要面对的不是失败是什么。

忽然有种特别真切的想法。时间静止了，我站在一条干瘪的水平X轴上，轴上贴着一个硕大的数字，0。抬头向上看，空空如也，隐隐约约远处有些云彩。然后太阳公公笑着对我说：孩子，加油向上爬啊，大家都在上面等着你呢。

这个时候也许会特别有劲，只想一个劲的沿着向Y轴爬上去。每前进一步，都特别高兴，笑容灿烂地绽放着。

是啊。那好。我现在就是零。我现在就是零。

二

好，现在我们回到现实，把镜头拉到5月31日。

这一天，是个很普通的日子，早上有一场选修课考试，下午去实验室做百度之星。可是在去选修考试的路上我和女朋友再一次吵起来了。心里特别难受。睁开双眼，看不到女友的眼神里面除了怨恨和愤怒之外还有任何色彩。女友的手紧紧地抓着我的衣袖，尖叫和愤怒的质问淹没了整个街道。那一刻，这个世界没有别人，只有我，我一个空荡荡的灵魂，在哭泣。

对。是的。我不是男人。我真他妈不是个男人。

我真的不明白，感情到底改如何维护。我非常困惑。血肉模糊就是感情吗？呵！

我的女友是个非常美丽善良的女孩子。我们的感情则是闹得惊天动地。

可是一个最无奈的事情是，我把她惯坏了。吵架成了家常便饭，人活着就是大喜大悲，心永远都是悬着的，不敢放下。

工作和恋爱是绝对冲突的。当你每个礼拜有例行的集训，当别人的假期成为你的工作时段的时候，冲突就凸显了。而也许这也仅仅是一个借口，真正的问题出在两人对待感情的态度上。这个世界上只有一件事，是不管你怎么努力都无法改变的。那就是感情。因为努力本身就是一个错误，努力去维护同样是一种逃避，因为你在违背自然。所以我很害怕，我很茫然，我很绝望。

别人可以做好，为什么我做不好啊。很显然，这总归是自己的问题。唉，是我自己性格的问题，可是，

唉。

三

《礼记•大学》有云：“古之欲明明德于天下者；先治其国；欲治其国者，先齐其家；欲齐其家者，先修其身；欲修其身者，先正其心；……心正而后身修，身修而后家齐，家齐而后国治，国治而后天下平。” 说的是明德之人需正心、修身、齐家、治国、平天下。治国、平天下，我没这个想法，但是修身，齐家这是人人的必修课。而我写这篇文章的目的，则是希望能正心。其后则是修身，齐家。

结果比较失望的就是我没觉得我得以正心了。我想也许我需要更多的是答案，我提的所有问题的答案。我将一个一个去寻找，去发现。我太不够成熟了，太小孩子气了，太自我封闭了。无论怎么说，我正在尝试，这就是好的，这就有希望。

oyjpart 2008-06-07 23:03 发表评论

点错题，看错题，做错题！可以去死了！！！！！！！！！

oyjpart — Thu, 05 Jun 2008 13:54:00 GMT

1.点错题：一点，发现自己点了500分的题，等了等，没反应（网速...)，还是想从250开始做，又点了点250，隔了一会出来了。以为是250的题，以为有简单的方法，想到一个枚举+排序的方法，怕超时。点了一下summary，发现别人都交了250(话说今天房间里面有一半是红人，很吓人），郁闷了。又想了下，写了个排序的上去。
2.看错题：交了发现居然还有220多分，原来是500分的题。汗。。。做250的吧。。估计交了也没多少分了。管他咯，做咯。结果怎么做怎么不对，样例死都调不过。到最后才发现题目都读错了。。一个数是上面的两个数之和，我看成上面的右边所有数的和了。。题目说的是upper right neiboring digits,就那个digit's'，汗，又读错了，亏我还说自己英语好。真tm丢脸。
3.唉就这样就算了，结果呢，第二题又被cha掉了。汗。我的心那个叫苍凉啊。
4.到practise room 一测俺的第二题，全是 "Received: caught signal SIGKILL"，那个叫不解啊。我在自己机器上G++运行的好好的，干嘛的就SIGKILL了呢。。唉。。

可以去死了！！！！！！

oyjpart 2008-06-05 21:54 发表评论

线性筛素数方法

oyjpart — Wed, 04 Jun 2008 08:39:00 GMT

看到高手的线性筛素数方法（Prime2函数)：

const int N = 25600000;
bool a[N];
int p[N];
int n;

void Prime1() {
   memset(a, 0, n * sizeof(a[0]));
   int num = 0, i, j;
   for(i = 2; i < n; ++i) if(!a[i]) {
       p[num++] = i;
       for(j = i+i; j < n; j +=i) {
           a[j] = 1;
       }
   }
}

void Prime2() {
   memset(a, 0, n*sizeof(a[0]));
   int num = 0, i, j;
   for(i = 2; i < n; ++i) {
       if(!(a[i])) p[num++] = i;
       for(j = 0; (j           a[i*p[j]] = 1;
           if(!(i%p[j])) break;
       }
   }
}

测试:

筛 [0, 100000) 范围内的素数
第一种素数筛法 0 毫秒
第二种素数筛法 0 毫秒

筛 [0, 200000) 范围内的素数
第一种素数筛法 15 毫秒
第二种素数筛法 0 毫秒

筛 [0, 400000) 范围内的素数
第一种素数筛法 16 毫秒
第二种素数筛法 15 毫秒

筛 [0, 800000) 范围内的素数
第一种素数筛法 47 毫秒
第二种素数筛法 16 毫秒

筛 [0, 1600000) 范围内的素数
第一种素数筛法 62 毫秒
第二种素数筛法 63 毫秒

筛 [0, 3200000) 范围内的素数
第一种素数筛法 297 毫秒
第二种素数筛法 109 毫秒

筛 [0, 6400000) 范围内的素数
第一种素数筛法 922 毫秒
第二种素数筛法 266 毫秒

筛 [0, 12800000) 范围内的素数
第一种素数筛法 2187 毫秒
第二种素数筛法 563 毫秒

筛 [0, 25600000) 范围内的素数
第一种素数筛法 4828 毫秒
第二种素数筛法 1187 毫秒

证明：任何一个合数只被标记一次。
      可以试着执行下这个程序的流程，就明白了

怎么样还行吧？
什么，觉得这个程序效率上没多大提升，没有什么用？
把a[]改成int类型，然后
void Prime2() {
    memset(a, 0, n*sizeof(a[0]));
    int num = 0, i, j;
    for(i = 2; i < n; ++i) {
        if(!(a[i])) p[num++] = i;
        for(j = 0; (j            a[i*p[j]] = p[j];
        }
    }
}
这样一来a[i]将记录i的最小质因子
那么[0, n)内的数的因式分解就可以... 嘿嘿
o(质因子个数)求任意数因式分解：
void factor(int x) {
    while(a[x] != 0) {
        printf("%d\n", a[x]);
        x /= a[x];
    }
    printf("%d\n", x);
}

然后用这个做了上次杭州比赛的GCD那题，虽然其实就是个容斥原理，可是我等白菜就是不会做。唉。
第一名8题，我们4题，这个差距大的有点想吐。
题目http://acm.hdu.edu.cn/showproblem.php?pid=1695

//Solution by alpc12:

#include <string.h>
#include <stdio.h>

const int N = 100010;

typedef __int64 LL;
#define I64Format "%I64d\n"
inline int count(int x) {int ret = 0;while(x != 0) {ret ++; x &= (x-1);}return ret;}

int a[N], p[18000];

void pre() {
    memset(a, 0, sizeof(a));
    int num = 0, i, j;
    for(i = 2; i < N; ++i) {
        if(!a[i])  p[num++] = i;
        for(j = 0; j < num && i * p[j] < N && (p[j]<=a[i] || a[i]==0); ++j) {
            a[p[j] * i] = p[j];
        }
    }
}

void go(int x, int y) {
    if(x == 0) { printf("0\n"); return; }
    int i, j;
    LL ans = 0;
    for(i = 1; i <= y; ++i) {
        if(!a[i]) {
            ans += (i<=x?(i-1):x);
        } else {
            int fac[20], nfac = 0, z = i;
            while(a[z] != 0) {
                fac[nfac++] = a[z];
                z /= a[z];
            }
            fac[nfac++] = z;
            int k = 1;
            for(j = 1; j < nfac; ++j) {
                if(fac[j] != fac[j-1])
                    fac[k++] = fac[j];
            }
            nfac = k;
            int now = 0;
            int xx = x;
            if(x >= i) xx=i-1;
            int mask;
            for(mask = 1; mask < (1<<nfac); ++mask) {
                int d = count(mask), mul = 1;
                for(j = 0; j < nfac; ++j) if((mask&(1<<j)) != 0) {
                    mul *= fac[j];
                }
                if(d&1) now += xx/mul;
                else now -= xx/mul;
            }
            ans += xx-now;
        }
    }
    printf(I64Format, 1+ans);
}

int main() {

//    freopen("t.in", "r", stdin);

    int ntc, a, b, c, d, k;
    scanf("%d", &ntc);
    pre();
    int tc = 0;
    while(ntc--) {
        printf("Case %d: ", ++tc);
        scanf(" %d %d %d %d %d", &a, &b, &c, &d, &k);
        if(k == 0) printf("0\n");
        else {
            a = b/k;
            b = d/k;
            if(a > b) go(b, a);
            else go(a, b);
        }
    }
    return 0;
}

oyjpart 2008-06-04 16:39 发表评论

基本参数搜索

oyjpart — Tue, 03 Jun 2008 07:45:00 GMT

上次百度之星第三题竟然不会做，很是惭愧啊，脑袋生锈了。

后来从HUST上面找了道类似的题目，AC了。

The perfect hamilton path

Time Limit: 5 Sec Memory Limit: 128 MB
Submissions: 72 Solved: 16

Description

There are N(2 <= N <= 13) cities and M bidirectional roads among the cities. There exist at most one road between any pair of the cities. Along every road, there are G pretty girls and B pretty boys(1 <= G,B <= 1000).
You want to visit every city exactly once, and you can start from any city you want to. The degree of satisfaction is the ratio of the number of the pretty girls to the number of the pretty boys. You want to know the highest degree of satisfation.

Input

There are multiply test cases.
First line: two integers N, M;
The following M lines: every line with four integers i, j, G, B, response that there is a road between i and j with G and B.

Output

The highest degree of the satisfation, rounded to the third place after the decimal point.

Sample Input

Sample Output

1.714

HINT

Source

dupeng

题目的意思是找到一个sigma(G)/sigma(B)最大的hamilton回路。
典型的参数搜索。二分或者迭代答案就可以了。

Solution：

#include <stdio.h>
#include <queue>
#include <cmath>
using namespace std;

const double EPS = 1e-4;
const int N = 15;
const int M = N * N;

#define Max(a, b) (a>b?a:b)

inline int dblcmp(double a, double b) {
    if(fabs(a-b) < EPS) return 0;
    return a < b ? -1 : 1;
}

struct Node
{
    int x, mask;
    double s;
    Node() {}
    Node(int mm, int xx, double ss) {
        x = xx;
        mask = mm;
        s = ss;
    }
};

int n, m;

double adj[N][N];
int X[M], Y[M], G[M], B[M];

double dp[1<<N][N];

double go(double ans) {
    int i, j;
    for(i = 0; i < n; ++i) {
        adj[i][i] = 0;
        for(j = i+1; j < n; ++j) {
            adj[i][j] = adj[j][i] = -10e300;
        }
    }
    for(i = 0; i < m; ++i) {
        adj[X[i]-1][Y[i]-1] = G[i]-ans * B[i];
        adj[Y[i]-1][X[i]-1] = adj[X[i]-1][Y[i]-1];
    }

    for(i = 0; i < (1<<n); ++i) {
        for(j = 0; j < n; ++j)
            dp[i][j] = -10e100;
    }
    queue<Node> Q;
    for(i = 0; i < n; ++i) {
        Q.push(Node(1<<i, i, 0.0));
        dp[1<<i][i] = 0;
    }
    while(Q.size()) {
        int f = Q.front().mask, x = Q.front().x;
        double s = Q.front().s;
        double& d = dp[f][x];
        Q.pop();
        if(s < d) continue;
        for(i = 0; i < n; ++i) if((f&(1<<i)) == 0) {
            if(dp[f|1<<i][i] < s + adj[x][i]) {
                dp[f|1<<i][i] = s + adj[x][i];
                Q.push(Node(f|1<<i, i, s + adj[x][i]));
            }
        }
    }

    double max = -10e100;
    for(i = 0; i < n; ++i) {
        max = Max(max, dp[(1<<n)-1][i]);
    }
    return max;
}

int main()
{
    // freopen("t.in", "r", stdin);

    int i;
    double ans;
    while(scanf("%d %d", &n, &m) != EOF) {
        double min = 2000, max = 0;
        for(i = 0; i < m; ++i) {
            scanf("%d %d %d %d", &X[i], &Y[i], &G[i], &B[i]);
            if(B[i] < min) min = B[i];
            if(G[i] > max) max = G[i];
        }
        double lo = 0, hi = max/min;
        int ok = 0;
        for(i = 0; ; ++i) {
            double mid = lo + (hi-lo)/2;
            if(dblcmp((ans=go(mid)), 0.0) > 0) {
                lo = mid;
            } else if(dblcmp(ans, 0.0) == 0) {
                printf("%.3lf\n", mid);
                ok = 1;
                break;
            } else {
                hi = mid;
            }
        }

        if(!ok) { int a = 0; a = 1/a; }
    }

    return 0;
}

oyjpart 2008-06-03 15:45 发表评论

这样的生活

oyjpart — Mon, 02 Jun 2008 14:23:00 GMT

5月31日早晨空气中沉浸着巨大的悲痛

可是我的面目却是麻木的

从此

头脑昏沉

每天钉在实验室傻傻看着电脑却什么也做不了

身边有alpc们，我的心有些安慰

虽然时间已经静止

可是世界仍然喧嚣我仍然没有发现自己到了地狱

可是我真的觉得自己不该来到这个世界上，原来自己一点都不真实

我的心是空的我不敢承受

考试，第一次我觉得考试那么难，我想原来挂科也可以和我离的这么近

而选修考试直接没有参加了我不在乎吗

是的也许程序才是真实的可是我却什么也敲不出来

原来程序也是要用心敲的

举杯回首

我的高中和我的大学哪个才是真正的我？

我讨厌现在的我讨厌高中的我

我想回到大一我想回到曾经的6班

我想拥有无尽的欢乐

我想觉得我还年轻我想觉得我这小子很不错

我想再体会一次那种渴望成长的感觉

我想再一次热爱生命热爱大自然

唉... 可是这都是虚幻的... 都是虚幻的!!!

oyjpart 2008-06-02 22:23 发表评论

湖大邀请赛

oyjpart — Tue, 27 May 2008 03:32:00 GMT

摘要: 废话少说，直接进入正题。比赛标题：湖南大学校赛暨湖南各大学邀请赛(包含几大中学) 比赛形式：个人赛比赛组队情况：alpc12(me) + alpc33(文文, 男) + alpc30(崔婧，女) 题目总数：12 AC：9&n... 阅读全文

oyjpart 2008-05-27 11:32 发表评论

[转]女人常说的32句谎话及详解...

oyjpart — Tue, 27 May 2008 01:29:00 GMT

第一句：我看上你可不是因为你的钱（或者是你的地位）！
仔细想一想，女人又不是白痴，什么都没有，只有爱情能当面包去吃饭啊？即使你现在没有，那么她的眼光也能看见你的以后，如果你很有能力，她肯定把你当作可升值性股票把你攥在手里。

第二句：你以为我想去啊，是xx非拉我去的。
谁拉谁去的啊？自己想去就去呗，我又不是不让你去。

第三句：你做饭做的真好吃。
哈哈哈哈！她这么说的时候千万别只顾着高兴，她的意思是：既然你做饭这么好吃，以后就你做好了……

第四句：给我讲讲你和你以前的她的故事，我不会生气的。
谁信谁完蛋！女人不吃醋谁相信啊？哪怕那是过去了500年的事情，等你说完了，她们就完全露出丑恶的嘴脸，要么哭啊闹啊，要么就让你干这干那，还美其名曰“劳动改造”！

第五句：她们都说xx牌子的衣服很适合我。
没什么好说的，掏钱包吧！

第六句：没关系，我感觉你还不胖。
如果她真这么说了，只是不想让你难堪，注意一下自己的身材吧。

第七句：老夫老妻了，我不要什么情人节礼物了。
天啊，如果这话你相信了，肯定和我一样，打扫一个月的卫生！女人么，说归说，如果你真不买，她狠死你！而且明年她铁定列张购物清单让你挨个买！！

第八句：其实，我感觉你应该有自己的‘红颜知己’。
切～～女人真有这么大方吗？她永远希望你离所有的女人远远的(除了她自己)。这样她才有安全感，如果你真有个女同学，女同事给你个电话，或者短信息什么的，她比谁都关心，耳朵还特好使！你晚上想和兄弟出去聚会的时候，她指不定就在你屁股后面跟着呢！

第九句：不要了么，房事对身体不好。
……自己品味吧！

第十句：没有钱我一样养着你！
天啊，我还没有辞职呢，为了以后的生活，去考it认证，需要点钱，我的工资和奖金一发下来就上缴，现在给点好么，“记清楚啊，现在可是我在养着你！”好好努力吧，兄弟们，男人是一家之主，挣钱就是你的责任！

第十一句：我们还是当朋友好了
其实你还有可以利用的价值

第十二句：我想我真的不适合你
我根本就不喜欢你！

第十三句：其实你人真的很好
可是我不想和你在一起

第十四句：你人真的很好
我是真的不想和你在一起

第十五句：你人真的真的很好……真的
猪头，离我远一点！

第十六句：我暂时不想交男朋友
闪边啦！你还不到我心中帅哥标准的一半

第十七句：我不想伤害我们之间的友谊
我们之间也只会有友谊

第十八句：我心中牵挂着一个人
那个人是我专门为你这种人虚构的

第十九句：我从来没想过这个问题
这是根本不可能的，还用想吗？

第二十句：我不适合当个情人
废话，没人会适合当你的情人的

第二十一句：你给我一段时间考虑
不给我时间，我怎么溜啊

第二十二句：你的条件真的很好
可是还没好到我想要的地步

第二十三句：可是这样的感觉好怪
这丑八怪，怪到这样还想吃天鹅肉？

第二十四句：你的温柔我会铭记在心的
拜托，情圣！光温柔是没用的，还要有钱！

第二十五句：其实我一直没勇气接受你
看到你差点吓死……哪还有勇气？

第二十六句：你真的很可爱
你真的很幼稚

第二十七句：你真的是超级可爱啦
猪头！不要象小孩那样缠着我！

第二十八句：遇到你，总会让我重温童年的快乐
就象阿姨遇到小弟弟那样

第二十九句：我们应该给彼此一点缓冲时间
给你时间快滚！再不走我要翻脸啦！

第三十句：别人都说你条件不错啊
可我从来没这样认为！

第三十一句：如果我们早点认识就好了
可以让你早点觉悟！

第三十二句：别急嘛，我们可以先做朋友
趁这个时候我要找到我的白马王子啊，呵呵

oyjpart 2008-05-27 09:29 发表评论

Tomcat JSP Web 开发中的乱码问题小结

oyjpart — Thu, 22 May 2008 03:26:00 GMT

Tomcat JSP Web 开发中的乱码问题小结
1. 静态页面的乱码问题
文件的编码和浏览器要显示的编码不一致。
1) 检查文件原始的编码, 可以用记事本打开, 然后选择另存为来看;
2) 给当前页面加入一个指令来建议浏览器用指定的编码来显示文件字符内容.

3) 如果系统是英文XP,没装东亚字符集支持, 也会显示乱码.
2. JSP 页面的乱码问题
1) page 指令有个 pageEncoding="GBK" 这个会指定当前页面保存的编码, 如果写成
ISO8859-1 就不能保存汉字;
2) page 指令的 contentType="text/html; charset=ISO8859-1" 也会像静态页面一样让
浏览器来优先选择一种编码.
如果JSP 乱码的话,一般就显示成?，而且不管你给浏览器选什么样的编码，它都不能正
确显示
3. 表单提交的乱码问题(Tomcat 特有)
1). POST 的乱码
MyEclipse 6 Java 开发中文教程
157 刘长炯著
a. 首先浏览器提交表单的编码是根据表单所在页面来决定的, 而不是根据提交后的
JSP 页面的编码来决定的. 把所有的页面的编码都设置成一样的,例如 GBK.
b. 处理方式就是在获取参数之前设置编码:
request.setCharacterEncoding("GBK");
c. 可以用过滤器的方式来解决, Tomcat 已经带了一个现成的:
apache-tomcat-5.5.23\webapps\jsp-examples\WEB-INF\classes\filters\SetCharacter
EncodingFilter.java
web.xml

Set Character Encoding

filters.SetCharacterEncodingFilter

encoding

GBK

Set Character Encoding

2) GET 方式的乱码
用 setCharacterEncoding() 不能解决. TOMCAT 的一个BUG, GET 方式传送的表单参
数总是用的 ISO8859-1 编码. 我们要把它转成 GBK 方式.
String username = request.getParameter("username");
System.out.println(username);
// 转码, 先取得原始的二进制字节数组
byte[] data = username.getBytes("ISO8859-1");
// 根据新的字符集再构造新的字符串
username = new String(data, "GBK");
小结:
所有的页面(除了最后的 GET 的乱码问题)都用统一的编码(GBK 或者UTF-8), 就不会出现
乱码问题

以上内容为【转】

下面是一个完整的过滤器例子：

package filters;

import java.io.IOException;
import javax.servlet.Filter;
import javax.servlet.FilterChain;
import javax.servlet.FilterConfig;
import javax.servlet.ServletException;
import javax.servlet.ServletRequest;
import javax.servlet.ServletResponse;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletRequestWrapper;

public class TomcatFormFilter implements Filter {
    /**
     * Request.java 对 HttpServletRequestWrapper 进行扩充, 不影响原来的功能并能提供所有的
     * HttpServletRequest 接口中的功能. 它可以统一的对 Tomcat 默认设置下的中文问题进行解决而只需要用新的 Request
     * 对象替换页面中的 request 对象即可.
     */
    class Request extends HttpServletRequestWrapper {
        public Request(HttpServletRequest request) {
            super(request);
        }

        /**
         * 转换由表单读取的数据的内码. 从 ISO 字符转到 GBK.
         */
        public String toChi(String input) {
            try {
                byte[] bytes = input.getBytes("ISO8859-1");
                return new String(bytes, "utf-8");
            } catch (Exception ex) {
            }
            return null;
        }

        /**
         * Return the HttpServletRequest holded by this object.
         */
        private HttpServletRequest getHttpServletRequest() {
            return (HttpServletRequest) super.getRequest();
        }

        /**
         * 读取参数 -- 修正了中文问题.
         */
        public String getParameter(String name) {
            return toChi(getHttpServletRequest().getParameter(name));
        }

        /**
         * 读取参数列表 - 修正了中文问题.
         */
        public String[] getParameterValues(String name) {
            String values[] = getHttpServletRequest().getParameterValues(name);
            if (values != null) {
                for (int i = 0; i < values.length; i++) {
                    values[i] = toChi(values[i]);
                }
            }
            return values;
        }
    }

    public void destroy() {
    }

    public void doFilter(ServletRequest request, ServletResponse response, FilterChain chain) throws IOException,
            ServletException {
        HttpServletRequest httpreq = (HttpServletRequest) request;
        if (httpreq.getMethod().equals("POST")) {
            request.setCharacterEncoding("utf-8");
        } else {
            request = new Request(httpreq);
        }
        response.setCharacterEncoding("utf-8");
        chain.doFilter(request, response);
    }

    public void init(FilterConfig filterConfig) throws ServletException {
    }
}

web.xml中加入如下配置信息

    <filter>
        <filter-name>TomcatFormFilterfilter-name>
        <filter-class>filters.TomcatFormFilterfilter-class>
    filter>
    <filter-mapping>
        <filter-name>TomcatFormFilterfilter-name>
        <url-pattern>/*url-pattern>
    filter-mapping>

上述都是使用统一的GBK编码，如果想用utf-8编码的话，稍作修改就可以了。
在解决了JSP乱码问题之后，还有一个问题，就是数据库乱码问题。
我使用的数据库是mysql
在hibernate的配置文件中加入
true
UTF-8
就算是一整套的中文解决方案了。

oyjpart 2008-05-22 11:26 发表评论