Welcome to my new home~~  ^O^

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

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

简单来说，被完虐了。个人认为题目出得过难，能从这套题目中体现出真正实力的选手不会超过50个，于是剩下的人就是赛RP了。

第一题，手写识别。虽然字符是只有那么几个，但没有训练集，那么AI里常用的那些算法基本全废了（或者当场用手写板生成？）。最后只能写了一些简单的规则乱水，不知道能得分不。

第二题，求一个多面体对任意轴旋转和任意面镜面反射下的同构个数，给的是多面体顶点的三维坐标……完全没有想法……我打了一个正N面体的表交上去了……

第 三题，应该是最有可能有人AC的题，给一棵树，树上的节点为黑色或白色，每次可以把某点改变颜色，或者查询从点1到某点v的路径上离1点最近的黑色点…… OI里面类似的题目出过几次了，不过我不会做 >_<……so直接暴力之……过两天把SPOJ里面的Query on Tree系列都割了先……

第四题，又是几何……一个扇形的西瓜，上面有一些西瓜籽，要求切出最大块的西瓜使其包含不超过k个籽。这题写了很久，写了近300行，虽然仍然是一个乱搞的算法……过了Sample和我出的几个小数据，希望能得几分吧……

这次成绩出得还是挺及时的。去年被骂怕了吧，呵呵。

第一试 36
1. AC
2. 挂了4个点
3. 裸暴过5个点
4. 没做
第二试 53.75
1. AC
2. 没做
3. AC
4. 裸暴过5个点

考虑到两天都有点事，第一场做了不到一小时，第二场做了不到两小时，这个成绩还算正常，如果完整做下来可能还会再高一点吧。现在这个成绩能不能出线就不好说了……

有几点比较意外的:

1. 第一场第二题为什么挂了几个点...是中文处理的问题么?
2. 第二场第三题竟然AC...我当时写完以后随手出数据就把自己cha掉了，后来又修补了半天，快没时间了才匆忙交上去，一度以为我那个程序是过且仅过Sample了...
3. 暴力第一场第三题和第二场第四题，各过5个点，数据挺厚道，呵呵

主要是因为这篇文章给了我勇气……嗯……

简单来说，是关于这样一个叫做“海内网”的网站（和"校内网"十分想像，实话来说的话，都是抄的facebook），现在上面有一个买卖奴隶（当然，是虚拟的）的游戏，类似炒股票一样，挺好玩的。现在的问题的我的钱有点不够，而如果每邀请到一个好友加入，就可以给我增加1000元现金（当然，也是虚拟的- -）。如果你愿意的话，可以点击如下链接进入注册页面，这样就表明是因我的邀请而来：

http://www.hainei.com/account?a=urlreg&r=-Bq-2wW_hg8MV4BsEtsHPQ

此链接保证无毒无害，注册以后会自动成为我的好友。我相信能够坚持访问我这个无聊blog而看到这篇文章的同好，加作好友也并不是突兀的事情，so...欢迎并感谢你的加入 :D

再附一个简介：海内是一个真人网络，提供个人空间，迷你博客，相册，群组，电台以及电影评论等服务。

250pt和500pt都水，做完以后发现我居然最快，这时候剩50min，然后就开始傻盯着1000pt看，看到了比赛结束还是不会做-_-。想按照一 位一位dp来着，发现又不好写又不能证明最多用多少次，就这么囧了。最后我们屋有两个红人交了1000pt。cha阶段仍然无所事事，我基本可以肯定有一 个1000pt是错的，因为他就是用map存状态当成背包乱搞，但不敢保证能出对让他TLE的数据，也有人cha那个程序没cha掉，于是就没敢动手…… 最后sys test结束，两个1000pt都挂了……so我就room leader了……查看了一下，我上次做leader是两年多以前的事了……汗……rating涨了100左右，从走势图上已经可以看到上方的红色区域 了……yy啊……

四川地震以来的所见所感，我自己拙劣的文字已不能描述万一，只能转载一篇，提醒我们活着的各位，加油。
====================================================================================

http://mopa.blogbus.com/logs/20969007.html

已经不忍心再贴大地震中的照片，这几天我想所有的人都会被那些镜头浸湿着双眼。灾难就是这样，强迫着人真实，就算你不能面对但也只能面对，我想也正因如此，面对灾难才会让强人生出恻隐之心，让弱者更加彼此依靠，体恤凝聚。

非生即死的窗口期在下午关上了，根据所有地震的救援经验，灾民第一天被救的存活率是90%，第二天是50～60%，第三天则只有20～30%，而过了72小时的生死门，但凡能生还者都是奇迹。

于是我不忍心再贴大地震中的照片了，因为灾难的真实告诉我，奇迹决不会常常出现，从现在起我们只会面对越来越悲惨的写真，于是今天我的题图用的是BlogBus上的同车博友瞎讲三千四年前在现在的地震震中扶贫时拍下的一位女生在自家墙壁上的涂鸦，“谁来救我快点，我苦死了”，当时瞎讲三千把身边所有的钱都给了她家，但觉得也不能解这女生最真切的期望。

不知道那个女生现在可还好，她现在如果还在上学应该就在都江堰的某座中学，但这些天的照片已不允许我再联想她的现在，为什么“死”这个字无论天灾与否都与那里的孩子连在一起，都江堰，建城2265年，千年前的人们应该也有幻想愿景，但千年后依旧苦死，他们还会相信奇迹吗。

救灾专家说超越极限的生命要出现奇迹只能依靠精神力量，对已经获救的生还者，同样救人生命易，治人心灵难，哭泣的他们也许永远、永远无法从这样的灾难中缓过来，面对未来的生活，同样需要奇迹，需要能依靠的精神力量，否则，灾后紊乱、冲突都会将接踵而至。精神，此刻已经不是一个虚渺的概念，而已经是一种最实际 的求生物质，一种最迫切的和谐资源。

那么，什么是可以成为物质和能量的精神。它一定不是一厢情愿的沉醉。这次灾难让我第一次认同“同一个世 界同一个梦想”，因为现在全世界都在梦想——救人！灾难所表现出的国人共同关注营救灾民，把人的性命作为最大的人性，这是比用奥运营造的爱国情更真实的精神。如果说将来回顾2008年我绝不会把她叫做“奥运年”，而是“拯救年”、“共济年”，我们不得不承认，就在今年，中国的崛起将不看奥运就看救灾。

不是吗，奥运圣火传递终因旗帜问题最后决定放弃台湾，但大灾中，即将总辞职的台湾民进党政府作出的最后一个当政决定则是以政府名义启动两阶段共20亿新台币投入支助四川救援工作；“和谐之旅”被指人面兽心的豺狼达赖屡屡阻扰破坏，但大灾中，达赖喇嘛称赞中国救灾感人迅速。和谐不是环球跑出一个盛世来，古老中国再次印证了一回大难兴邦。

但，我们不能再将兴寄予难了，我们不能再一直置孩子于“苦死”之中，灾难后，我们必须深切反思如何树立以及什么是盛世兴邦的精神。

这 次地震比较32年前的唐山大地震，两同两不同，相同的一是地震等级相同，二是地震中中国人民一不怕苦二不怕死的气概相当，但两大不同却让世界为之称赞，一是震情如实通报，体现了政府对人民的信任，今天国务院抗震救灾指挥部最新确认，汶川地震已造成19509人死亡，遇难人数估计在5万人以上，在72小时耗尽后第一次在地震伤亡公报中列入了估计死亡人数，很客观很务实，而32年前唐山地震的伤亡人数直到三年后才得以见报，事实证明，信息的公开、舆论的放宽并没有引起不良后果，却更令人民理解和信任，二是32年后我们不再拒绝外国援助，事实上没有人会因为中国呼吁帮助而认为中国无能自救，相反，与世界合作，真实报告灾情，呼吁和接受帮助正改善了中国在世界的形象。

帕斯卡说，人不过是一根苇草，是自然界最脆弱的东西，大自然并不需要动员自己全部的力量，只需要一滴水，就能置人于死命。这就注定了人类不可以被分割，被孤立。只有以人类整体去面对，灾难才是可能克服的，恐惧才是可能走出的。中国是中华人民的共和国，也是地球人类的国度之一，中国人同样也先是地球人，大灾之中让我们更看到所谓精神并不能依靠特立独行的打造，那是靠不住的，世界还是有普世价值的存在。

在网上看到一首为地震死去的孩子们而作的诗，那不是用墨而是用泪写成的：

孩子快
抓紧妈妈的手
去天堂的路
太黑了
妈妈怕你
碰了头
快
抓紧妈妈的手
让妈妈陪你走
 
妈妈
怕
天堂的路
太黑
我看不见你的手
自从
倒塌的墙
把阳光夺走
我再也看不见
你柔情的眸
 
孩子
你走吧
前面的路
再也没有忧愁
没有读不完的课本
和爸爸的拳头
你要记住
我和爸爸的摸样
来生还要一起走
 
妈妈
别担忧
天堂的路有些挤
有很多同学朋友
我们说
不哭
哪一个人的妈妈都是我们的妈妈
哪一个孩子都是妈妈的孩子
没有我的日子
你把爱给活的孩子吧
 
妈妈
你别哭
泪光照亮不了
我们的路
让我们自己
慢慢的走
妈妈
我会记住你和爸爸的模样
记住我们的约定
来生一起走

苦难中的孩子，死亡也许成为解脱，成为上天堂的殿门，但天堂降落人间真的是不能实现的奇迹？假如我们对贫困地区的社会成果共享再多给予一些，而不是拿来粉饰自己的脸面，假如我们把庇护孩子的校舍用钢筋加固一些而不是抽去修缮追逐权力私欲的台阶，我们就不需要什么奇迹，天堂就是人间。

出现奇迹和 相信奇迹都很难，不然不会在“黄金救援时间”后看到了官方总体遇难评估数字；出现奇迹和相信奇迹都很难，所以与其寄望灾害准确预报，不如把所有学校检查一遍实际；与其奢谈人类的终极理想社会信念，不如融入到现代人类社会的共同价值观务实。所谓和谐之旅，大凡应是如此。

孩子，来生再做中国人，来生一起走，来生我们不再要奇迹，来生中国是天堂。为此，活着的中国人都要加油！

比较的累，大家都辛苦了，尤其是3个MM。半夜就开始出来赶路，火车上没有座，地铁上公交上也没啥坐的机会，赶到北大没来及歇会儿就开始比赛了。然而在这 种状态下大家成绩仍然不错，超过了我的预期，相当的赞，尤其lx他们队5题13名，更是要orz。话说我要像这样迷迷糊糊上场的话，未必能有这个成绩（我 在1318看题，发现脑袋根本没办法想东西，想了一会儿，就睡着了 - -）

回来的时候被耍了一把，急急忙忙赶到清华找回来的校车，被告知，4:45那班不开了 - - 又得公交地铁火车地原路折腾回来。还好买到了有座的动车，大家睡的那叫一个high啊……

感谢styc的咖啡和饭卡，还有志愿者MM们（确实好多PPMM啊……）

另外，在北大我们一帮人问路K次，被问路N次(N>>K)……

回来以后时差一直没调过来，早上醒得极早然后就睡不着了，一到下午尤其是傍晚就超级困。在这种状态下做一场比赛，明显不能期待什么好成绩。

发现又和Petr一屋，RP真不错……打开250pt发现乱暴就可以，仔细想了想怎么暴，就写了一个程序交上了。速度还算不错，房间第三还是第四吧。 500pt写扯了，一开始没看清题，以为O(n^3)就可以，仔细一看才发现有个先后顺序的条件，然后就发现只能O(n^4)了，时空复杂度都是。N是50，时间上问题不大，但印象中TC给的内存是很少的，不知道从哪里来的记忆，说是只有2M，然后我就不会做了……囧了半天，到群里一问，说是64M， 我囧囧囧……然后就赶快写完了，Sample给的很厚道的，最后一组trick数据一开始我没考虑到。这时候就只有二十多分钟了，看了看1000pt发现 居然有点思路，胡乱贴了一个高斯消元模版，再写一个可简单图化的判定，当时真是好像梦游一样，一点紧张感也没有，一点时间观念也没有，稀里糊涂就拍完了。 测过Sample，在结束前几分钟交上了。

然后X阶段1000pt果然还是被干掉了(不是被Petr,555)，现在还没仔细想是哪里的问题。然后前两题都过了，但因为500pt太慢，排在了160多名。于是就掉了3点rating。不过看上去依然很黄很圆满。

走势图

写得比较乱，也没怎么分段，凑合着看吧

我从后往前看，但是一开始感觉K有点长就跳过了，把J,I,H读了，感觉J勉强可做，但按我们队平时的习惯肯定不是一开始就敲的。读了半个小时，结果发现 没题可做-__-。这时候有一些球出来了，一开始的时候很分散，后来发现似乎F和K比较多，wt和hawk就去想F了，其实这个题感觉也并不很简单，如果不是有那么多队过我们是肯定不会先去想的。同时我赶忙把K读了，发现就是多加上八个状态的最短路，但处理起来麻烦的地方不少。这 时候右边的东京大学一声欢呼就把K球挂上了，然后我一兴奋就上去敲了个读input的预处理，发现下面还没想好，又下来了 -.- 他们两个对F推了一些结论，然后wt上来写了个dp，发现不能过自己出的小sample，后来又修正了一些地方，就过了。然后我写K，不知道 当时怎么想的，写SPFA用了一个平时很少写的写法，可能是认为那样会快一些吧。然后就出了小错无数，耽误了N多时间，后来终于过了sample提交却 WA了，打印了程序和无数份手工数据，怎么也找不出错来。我卡的时候cnhawk敲了A，WA掉了，wt手写了J的伪码，但似乎一直没有足够机时来 实现。直到三个多小时的时候，我实在找不到错了，向wt讲自己K题的算法时才突然发现是松驰操作更新以后，我的程序仍然可能从队列中取旧的距离值，我在以前用同样写法来实现SPFA的时候就在这里错过，居然错了第二次……然后着急改正的时候又没改完全，又多贡献了一个WA，这样，几乎全场都过了的简单题K（貌似卫冕冠军Warsaw U没过-_-），我在封版前才3y掉，可以说是本次比赛成绩不好的罪魁祸首了。然后wt写那个其实也很麻烦的计算几何J题，cnhawk继续改 A，已经发现的WA的地方，但是很难改。这时候可以做的还有B，我们没有想到用差分序列的方法，只是认为随机乱搞就有非常大的可能过掉（后来得知确实很多队是乱搞掉的），但时间已经太紧张了，我写了伪码之后估计要20-30min的时间，不过已经没有这么多时间留给我了。最后时刻 cnhawk的代码还在诡异的RE中，wt的J仍有一个sample不过，我和wt一起找错，终于发现是对题目的理解有点问题，地平线不能算做skyline的，然后就过了sample直接交了，结果居然WA掉。继续找错，终于在就要结束前发现一个严重的逻辑错误，改掉之后直接交（后来才知道，这时候是第296分 钟），然后突然来了一个人给我们挂了个汽球，当时我们很诧异，我还专门问了一下，回答说就是J题的球，我们就囧了，因为当时PC^2上的status仍然是没有评测的状态。cnhawk的A还是对不上号，就这么结束了。本来打算结束以后等着看J的结果是什么，结果刚结束所有的机器就被强制关掉 了-_-。从封board排名估计，2题和3题应该就是mention与否的分界，所以我们一直在提心吊胆地等最后结果。在颁奖会上有一个很酷的演示最后一小时的提交情况，从封board排名开始，如果ac了新的题，那个队就会一下子飞到上面去。到我们队的时候，发现确实是飞上去了，不知道是不是为了故意制造悬念才不给我们在PC^2里返回的-_-。

于是结果就是3道题，按那个排名来说就是并列47名，在全部100个队伍里是中游，在中国大陆14支队伍里也是中游，以第一次参赛来看也算说得过 去的成绩。就我个人来说对这个结果是不怎么满意的，如果我的K题不是做得那么垃圾，或者我们能把B放在A的前面，4题应该是一个比较正常的成绩。当然4题也没什么本质区别，与前面的强队还是有着巨大的实力差距。只能说继续努力了，希望明年TJU还能出现在WF赛场上，并且能有一个更好一点的成绩吧。

后天就要出发了，所有的准备工作也差不多了。当时在得知出线结果后悄悄定的几个目标，现在可以也说一下了，呵呵：

1. 在TOJ上AC1000+题目 (这个倒是做到了，不过纯属心理安慰作用...)
2. TC Algorithm变红 (还差150，555...)
3. SPOJ进第一版 (这个彻底荒废掉了...)

看来完成得不怎么样呢，汗……

其实我并不是很喜欢争强好胜的，可以说是各种机缘巧合让我走到了这一步。不管那些冠冕堂皇的理由，学校荣誉啊之类的东西，至少来说，为了那些远强于我却因RP而囧的人们，怎么也得看上去有个finalist的样子才行吧。

不管怎样，这会是最没有压力，最好玩的一场比赛了。Petr说，生活不能只有比赛，但生活会因比赛而更精彩，不是么？