此帖置顶，想与我交换链接直接在此留言即可

我的另一个关于技术方面的Blog: http://roba.yo2.cn

采用250 -> 1000 -> 500策略...

250pt写扯了，花了快20分钟。然后直接开1000pt，发现是个变态大模拟，最后写了200多行，没调试过所有Sample……又是结束后几分钟写过了，不过在练习室里交还是WA了，错了好几个地方，改了好几次才过了……最后这题只有两人过(Petr和ACRush...)，看了看人家的代码比我简洁多了，学习ing……

结果就是500直接没开，然后排名惨不忍睹，Rating直接掉了100，又变成黄人了……不过既然选择了这么做就要有这种觉悟了，我的底线是不掉出div1就行…… 等我用这种方式也能红色的那一天，哼哼……

这里所说的此类人，可能体弱多病、英年早逝，可能深居简出、默默无闻，但基于某种特质，统称其为“强者”。

强者不需要依靠，他也找不到可以依靠之人。勇敢的强者把孤独写在脸上，周围的人往往会被他的冷漠和不屑刺伤；狡猾的强者把孤独藏在心里，他也同样可以和狐朋狗友一起鬼混，只是内心深处的另一个他，始终孤独地、冷冷地望向星空。

这样的人，是带着上帝的使命来到人间的。他们的任务，就是以自己的智慧，推动这个小小星球上的小小生物，一步步接近神圣和不朽。

有时候严重的问题是，强者并不能确定自己就是the chosen one，所以他们也会忧惧、懦弱，然后便收敛了光芒，以他们非凡的智慧去经营庸人之事，做一个略显优秀的普通人。对于这样的，我们无法多作苛责。而对于那些勇于实现自己价值的，显然地，他不可能被同时代的人理解，人们对他的态度由敬畏到恐惧，由恐惧到憎恨，最终他在人们的排斥中郁郁而终，更有甚者是被其力图挽救的群氓所害。等到若干年之后，人们的智慧终于发展到足够的程度，才会突然惊觉，原来我们把上天的馈赠如此轻易地挥霍。一些人就开始嘲笑当时的人，却不知道现在你我的身边这样的珍宝又有多少呢？

……扯不下去了，发现我扯淡的功夫比尼采差远了……我没发疯，只是脑子抽风了一下，各位看官不必多虑……

http://www.bullog.cn/blogs/wanderlust/archives/165527.aspx

在某个严肃的饭桌上，有一个年轻人正襟危坐，他看上去若有所思，但又有些心不在焉。他偶尔仔细聆听席间的争论，偶尔又露出不耐烦的神情。这时候，坐 在年轻人左边一位脸色红润的大汉忽然搂住了他的肩膀，大汉满嘴酒气，热情奔放，浑身上下都洋溢着人格，他像一名苦难的阶级兄弟一样对年轻人背诵了一遍中国 近代史，然后他大声的说道：“孩子！不要忘记这些！这些日本人、美国人、法国人……外国人对我们所干的事情！一定不要忘记！不要忘记那些资产阶级剥削冷酷 的嘴脸，不要忘记革命者沸腾纯真的热血！记住这些，你就是我们的兄弟！”

说完这些，他揣着酒杯扑进了一片杯觥交错之中。正在年轻人发愣的时候，坐在他右边斯文而彬彬有礼的学者也把脑袋凑了过来。学者聪明而不动声色，他先 蔑视的瞟了一眼那位醉醺醺的大汉，转而用真诚的眼光凝视着年轻人。和大汉不同的是，学者先把中国的当代史背诵了一遍，随即他也有些激动的对年轻人说道： “孩子，这就是这个政权曾经干过的事情，你虽然没有经历这些，但你以后不能忘记这些。你忘记了，你忽视了，你就是无知、无耻，你就是民主的敌人。”

听完这些，年轻人的脑子隐隐有些发胀，两片屁股辗转反侧，不知道该放在哪一边。他本想保持沉默，但他发现左边那位貌似已经喝醉了的大汉在偷偷的瞄着 他，右边那位体面的学者也在暗自观察他。年轻人有些气馁，又有些茫然，他犹豫了半晌，终于站了起来，大声的说：“我能不能不记住这些，去追求客观的真、 善、美？”

“不能！”两个中年人异口同声的嚷嚷起来，“这是不可磨灭的仇恨！”“这是你死我活的斗争！”“以自私为美的资产阶级身上也有真善美？幼稚！”“这个邪恶的政权身上也有真善美？滑稽！”

年轻人憋红了脸，他说：“我没有经历过你们所说的那些，但我也清楚那些曾经犯下的罪恶，有些罪恶已经过去了，有些罪恶依然存在。经历过这些，并不意 味着深刻，没有经历过这些，也不代表无知。现在，我正年轻，我追求健康的人格，快乐的生活。我憎恨某些东西，但我并不想也变成那样。我不想永远活在过去之 中，我也不想背负这样的包袱。我从来不曾丢弃自己反对和质疑的精神，但也不愿因此而失去客观理性，和自己最淳朴的感情。我喜欢站在不同的角度去看待问题， 但永远不会站在某个立场上去看待问题。我认为，前者让我更开阔，后者让我更狭隘。

我从小疾病缠身，我也见到过很多苦难，我也为那些苦难的人做过一些微不足道的事情。我从来不曾忘记自己是个从偏僻小县城走出来的青年，我过去、现 在、将来都不会成为一个洋洋得意的精英。我有时候也愤怒，但更多的时候，我乐观而积极。我热爱这个国家，我相信美好的未来——不管这是否幼稚可笑，我愿意 为此而奋斗。对于你们，我满怀尊敬，同时我也希望你们能理解我的想法。我希望每天起床的时候，不是满怀着仇恨，而是满怀着希望和爱。

在《卡拉马佐夫兄弟》的结尾，阿辽沙说：最要紧的是，我们首先应该善良，其次要诚实，再其次是以后永远不要互相遗忘。我喜欢这段话，也想把这段话送给大家。我就说这么多，我希望大家能够携手共进，成为朋友。”

年轻人说完就坐了回去。饭桌上沉默半响，然后爆发出了各种叫声：“脑残！”“五毛！”“傻逼！”“装逼犯！”“说的真他妈恶心！”“GCD天天操你 屁眼，你还在这里追求什么客观，什么真善美，呸！”“难道你已忘记那些学生的鲜血了吗？”“日本人是怎么屠杀我们中国人的！”“什么鸡巴糊涂脑子！”“操 你支那狗的老娘！”

年轻人吃了一惊，这时候他才发现饭桌上有着很多跟他岁数相仿的年轻人，他们的眼神充满狂热，分别仰慕的看着大汉和学者，而厌恶的看着自己。年轻人有些不知所措，而大汉和学者则幸灾乐祸的看着他。

“快点滚吧！你不配呆在这里！”有一个更大的声音响了起来，席间众人纷纷附和。听到这句话，年轻人终于松了一口气，于是他站起来，匆匆说了一句再见，然后就一溜烟的跑掉了。

今天不在状态，睡得迷迷糊糊地就开题了，250pt是个贪心，不难，写得稍慢了一点。打开500发现不会做，伪多项式或状态压缩都不行，就囧了。（正确做 法似乎就是拆成两部分分别背包再合并，结束后听别人一说“双向”就反应过来了，比赛当时确实没想到）囧了以后就想干脆直接去做1000pt了，其实我一直 想等红了时候就开始每次都先开1000pt的，这次正好挑战一把……然后发现1000pt也不是不可做，就一状态压缩dp，可惜确实不在状态，思路对了， 小错无数，到结束以后七八分钟才调试出来，后来在练习室里交TLE了，是一个地方写得确实太暴力了，换成位运算就可过。所以最后就只有1题，100名多一 点，Rating降了30多，仍然红的，呵。

ps. 发现这样是一个挺好的方法，先不管三七二十一水掉250pt，也不去仔细检验了，按照通常情况这个时间不会超过15分钟，然后剩下的一小时专啃 1000pt。按以前的做法的话，把500pt做出以后基本上就不可能有足够时间来做1000pt了，虽然这样能勉强维持在红色上下，总感觉不爽呢……我 这人又比较懒，比赛结束以后就懒得再想题，最多也就是看看1000pt的解题报告就完事，这样下去也不会有多大长进，只是把水题写得越来越快而已。以后就 按照250->1000->500的顺序来开题了，或者更刺激一点的1000->500->250，看到时心情了，呵呵……等我 跌出红色再回来的时候，2500+的Rating或许就有希望了呢。

走势图不传了，在ycul上传图片有点小烦……

RoBa注：我在出这道题(TOJ 2941 Girl Friend) 的时候，并没有看过这篇文章……我那道题是作了太多简化的，很多地方都理想化了，最后可以得到一个简单的线性dp算法。当然，明显是很不实用的，就算真能准确计算出fitness和成功的概率，最致命的一点是在实际情况下不可能预知那个约会序列。相比之下这篇文章的讨论就更genernal和practical，虽然 还是作了一定简化的。最后结论就是，这个事情最好还是不要用数学来计算了……另外要说的是，MIT果然是MIT，YY的比我深刻多了……


原文地址 http://dahua.spaces.live.com/Blog/cns!28AF4251DF30CA42!1817.entry

有些朋友似乎想看看这里的算法作业。恩，很多都是针对算法领域的一些专门问题，不太适合在这说。不过，正好上周的作业里面有一道题目很经典，呵呵。

题材嘛，就是关于约会和选择恋人的策略——其实大家发现搞算法的那帮人想问题和普通人还真不太一样——这里说的是经典算法，不是Learning算法。

下面是译成中文的原题：

考虑一个选择终身伴侣的问题。假设你要从k个候选人里面选择一个人作为你的终身伴侣（嗯，MIT的学生通常在这个方面比较势利）。你可以选择先和某个人约 会一段时间，衡量一下你和这个人的适合程度，然后做出一个重要决定——你究竟要选择这个人永结同心，还是和他或者她彻底分手。作为一个负责人的人，你必须 遵循这样的规则，在和一个人没有彻底分手之前，你不能选择约会其他人。如果你选择和一个人彻底分手，你将再也没有机会重新选择他或者她。而且，请你明白， 在你约会一个人之前，你不可能了解关于他或者她的信息，或者对其做出判断。

你的目标是尽量选择最合适的人做伴侣。这里面的困境在于，如果你决定接纳当前这位作为终身伴侣，那么你将丧失选择更好的人选的机会；反之，如果你决定和他或者她分手，那么你将可能错失一个最好的人选。

在你做出最终决定之后，你会有机会见到全部的候选人，这样你就知道你选择的那个人究竟在这些人里面排名多少。如果你用了一个好的策略，你很可能最后会发现你的终身伴侣排名很靠前，如果你用了一个不好的策略，你有很大的机会发现其实你找了个排名很后的。

请完成如下问题

1. 请证明任何确定性的决策过程在最坏的情况下都是非常糟的。也就是说，无论候选人的人数是多少，无论你选择什么样的决策过程，都存在一种候选人序列，使得依据这种策略选择出来的人是里面最差的。
2. 请设计一种随机策略，使得无论有多少候选人，你都起码有25%的机会选到最好的那位作为终身伴侣。
3. 为了实现你对于伴侣的高期望，请设计一种随机策略使得你选择的候选人的实际排名尽可能靠前。这种策略至少应该保证，无论候选人的数量k有多大，你都可以以非常高的概率选到排在前 12 log(k) 名的人。（注：这道题其实问的东西要难一点，设计的要求更高，这里放宽了一点要求）
4. 请据此评论在MIT谈恋爱的后果。

解答写起来公式多一些，这里不多叙述了。这里简要分析一下而已。

1. 这种最差例子很容易找的。大概意思就是，无论你有什么样的策略和算法，我都可以找个人——这个家伙可能对你恨之入骨，呵呵。让他追踪你的决策过程，他模拟 运行你的算法，如果你的算法第一个不接受，他第二个找一个差一点的，第二个还不接受，他就往序列里面排进更差的作为第三个，直到算法接受了某一个后，他往 序列后面排进特别好的。然后你开始拿你的算法去这样构造出来的序列里面挑伴侣，保证挑到最差的。
2. 这个算法有点那个。你把你的候选人随机分成参考集和目标集，各占一半。你先把参考集的人逐个约会一遍，每约会一个分手一个——告诉对方他或者她是拿来训练 你的model的——唉，不知道那个人会不会第二天拿把刀来砍你。然后你在目标集玩真的。一直约会下去，直到找到一个人比参考集的全部人都好的，就把这个 人选为终身伴侣。如果，直到最后一个你还没碰上，你就选最后一个作为伴侣。因为你划分参考集和目标集是靠抛硬币划分的，那么你有四分之一的机会出现这样的 情况：第一名的出现在目标中，第二名出现在参考集中，这样按照你的规则，在这种情况，必然会选择最好那个。所以你选择最好的机会是四分之一。
3. 这个题目有点复杂，不多说了。需要用Chernoff不等式。
4. 嘿嘿。。。。。。

整个问题最后的结论是——不要苦心孤诣的去选最好的伴侣了，抛硬币又省心效果又好，哈哈。

如果发生下面事情之一，说明我终于找到正经事干了：

1. RSS订阅里的每个feed都有数个更新
2. 一进joke版（哪怕是求实的joke版）就可以哈哈大笑，而不是总在心里憋着一句兔呕得
3. 不懂得什么是俯卧撑，什么是打酱油，什么是毛建军，什么是叉腰肌……
4. 上一次海内，发现自己十辆车全在路上跑着
5. 邮箱里一坨未读邮件
6. 不再每天抢一个first，几天改一次qmd
7. 开了电脑，忘了开QQ开MSN开gtalk
8. 待续，想想我现在还有什么症状先……

http://quizfarm.com/test.php?q_id=17550N

其实很早以前就做过这个测试了，刚才看到两个人（Ta和Ta）又在折腾这个东西，所以又无聊去测了一次，结果与上次稍有不同：

前 三项还是原来的前三项，不过完全平均了，1/3数学，1/3工程，1/3哲学。但是三个也都不高，可见我以后就是个半吊子了。为了break tie，最后有一个附加的问题，让我在三种情况里面选一个最经常的，我选择了“思考此生的意义”(英文大意)而没选“冷静地解决问题”云云，于是就说我是 Philosophy了吧。囧。

其实从很早以来就有这么种感觉了，心事最重的时候，是说话（写blog）最少的时候，所以对于真正值得记录下来的事，往往当时并没有那个心情。也许这就是所谓的“却道天凉好个秋”吧。但不管怎么说，好歹写一点东西，等过些时间以后再看，揣摩一下当时的想法，也是很有意思的事情。刚才又在无聊翻BBS ACM版的老帖了，心里又有点唏嘘，所以有了上面这段话。

不知道现在还有多少人有写日记（纸质）的习惯，反正我估计是不可能坚持下来的。初中的时候曾经被语文老师强制写每周两篇的随笔，也许后来我的不错的作文成绩确实拜其所赐，但在当时来看，确实带给我的痛苦大于欢乐。再加上文章是要上交给老师看的，也不可能写些很私密的东西，和真正意义上的日记还是挺不一样的。后来也尝试过写日记，发现持续的时间不会超过两三天，很囧。

后来出现了blog这么个东西，一时之间貌似人人都有了，当然一两篇文章之后就歇菜的应该是大多数。没想到我居然能一直坚持几年过来。应该很大程度上是因为访问量和评论吧，如果是弄成像日记本一样完全秘密的，就没有坚持的动力了。写blog的时候，一方面不太想让人知道心里的想法，一方面又想要得到很多人的关注，看到有人留言就会很高兴，真是个奇怪的矛盾呢。

按照页面上的统计（不知准否），现在这个blog的累积访问量也有8万多了，近期大概平均每天的hit在100-200之间，也不清楚这个值是在平均水平之上或之下。几乎纯白的页面，方方正正的版式，平淡无趣的内容，偶尔几句的留言，挺符合我的风格，呵呵。曾经想过自己租个空间架个php站，后来又感觉没有很大必要了，一个普普通通的人的无聊东西，就是一个半公开的日记本而已，不值得花费这么大力气。

嗯……话说我为什么要写篇这个呢……