我被分配的subround是A和B，26号上午和半夜。于是就在26号上午做了。题目还是比较有挑战性的。第一题是给定两个向量，要求把各维重新排列使 得其点积最小。根据排序不等式可以逆序时是最小的。第二题是一个特殊的SAT问题，实际上是所谓的Horn Clause，可以用一个构造的方法解出：若所有的式子都包含大于两项，则可以把所有变量全置0；若有一项的情况，则可以确定出此变量的值，再把此值代入 其他式子进行化简，若发现矛盾则不能满足。第三题是一个比较诡异的题，没有好的想法，用 mathematica+人肉 把小数据过掉了（手抄错两个地方，WA两次- -），大数据不会做也没时间做了。

最后排名本来是160+，后来貌似计分规则改变，变成了105。这个规则变化还是有一定影响的，现在只看小数据的提交时间了。我这次做题的策略就是把三道题当成了六道题做，先不管3721把几题小数据都暴了， 再慢慢去想大数据的高效算法。在新规则下这样就有可能会有利一些，所以名次提高了。不过这样也有不好的地方，就是一旦大数据也并不那么难的话，写暴力的程 序几乎是在浪费时间。比如这次的第一题，我就先写了个next_permutation，做完一圈回来仔细一想才发现其实排个序就可以，暴力的算法也并不 一定就能写得快写得准，所以还是要酌情处理。

因为是每场subround选前840名，所以肯定是进了。本打算今天晚上继续练手呢，发现round 1b已经不允许我参加了……汗……本来说的好好的即使前一场过了后一场也可参加只是不算成绩的……无聊之下就写了这篇日志……

先放个图...


其实这次一开始颇多不顺，八点钟左右注册的时候还好好的，快开始比赛的时候突然打不开arena了……重启，重下载，命令行启动，全不行……从TOJ的FTP上拷了一个JDK1.4装上，才可以用了，不过这时候比赛已经进行了二十五分钟左右……

犹豫了一下还是开题了，因为按照平时的话如果写顺了五十分钟足够我完成前两题了，反正最后一题一般也是不会做，呵呵。发现第一题是水DP，第二题愣了一下没想到好办法，干脆floodfill硬上，两题写完，发现还剩了二十分钟多点，还发现我又Leader了……看了下第三题，发现不光预处理麻烦，处理完以后是超多点的Hamilton回路，连通块DP的话状态也太多……全然不可做……发现当时只有1个submit，就放弃掉去检查前两题了。（后来共有七八个submit吧，但也都挂掉了）

cha阶段看了好几个诡异的500pt代码，但都被很多人cha而没cha掉的，所以也就没敢动手。最后Sys Test两题都过了，Room Leader，Div Rank 35。就在yy不会真的能变红吧……然后等更新出来发现rating是2219……真神奇……当时进不去arena的时候就想直接不做了呢，看来有时候冒险一下还是很有必要的。

其实这次主要是rp好，正巧前两题都比较水，最后一题又不可做，所以少了二十几分钟几乎没有影响。如果前两题难些我就可能做不完两道，如果最后一题容易些人家都能过我也没时间做了。嗯……居然是在这样一种诡异的情况下变红了……

附一张完整走势图：

自从升到2100+以来的几次比赛都发挥一般，小降了几次，前些日子也因为毕业的事情太多，有几场就没有做。最近打算重新开始了，近段时间的比赛争取一场都不错过，呵呵。

说 这次的题目，250pt有点小难，不仔细想想的话很容易被阴到。我花了些时间把思路完全理清了才写的。（中间接了个电话，嘿嘿，不然应该能快些） 500pt和前几天刚见的一道题有些相似，注意到一定存在一种最优解使得某访问请求恰好在缓存的最首端或最尾端，这样就把本来10^9的范围缩小成了O (N)量级的可能性（N是请求数）。于是就是一个简单的O(n^3)DP了。1000pt一开始还以为把pick定理简单乘除搞一搞就能出来呢，拿第一个 Sample验证了一下我的猜想就开始拍了，等拍完了才发现过且仅过第一个Sample - - 再一看Div Summary，发现红到发紫的target们都在那里傻眼着呢，基本就放弃掉了。想了一下前两题，没发现有错误，就等着结束了。cha阶段我死盯着最后 一人的250pt看，已经发现他的错误了，不太敢cha，刚想再仔细检验一下，发现已经被别人cha走了 =,= 于是就又无所事事了。

最后本来只排房间第四，Sys Test完了以后我前面的人都挂题了，于是我就排到了第一，很orz的说。这次Room Leader主要因为这屋较弱，总的div排名是70多，小涨了40+，2148，算是新的最高记录了。



Edit: 原来的标题写错了，不是SRM407，是SRM410 -__-

基本来说是无悬念。三题都不难，不过我的条件反射实在是有问题。第一题，条件反射出来是DP，一顿拍；第二题，条件反射出来是DAG路径覆盖，又一顿拍……今天一讨论，两题人家都说是贪心……看来以后在写之前还是要多想想，不然总是费力不讨好。

另外第三题还惊险了一下，小数据AC以后，把大数据下了跑出来，输出应该是一堆浮点数，上交之前扫了一眼，发现里面有个NaN，直接就囧了。火速在源代码插 入各种assert，发现是在一处开根号的时候，因为精度误差没好好检验，传进去了负数……火速改进重跑，在八分钟时间还剩一分半的时候终于得到了正确的 结果……还好最后是也过了。有这次教训，后面的比赛中下大数据前可要谨慎了。

以上。

已经快一个月没有新文章了，今天终于有了时间和心情，所以随便写一点。以后还是要坚持多写。

这些天的一个大事就是毕业，各种散伙饭，我还都是双份，很感谢原英语系的同学还这么给我面子。一次也没喝挂，最接近挂的好像是ACM队毕业生和老于一起吃的那顿，其实也并不喝得很多，就三瓶左右的啤酒，不知道怎么坐车一颠就晕得厉害了，不过总的来说还好。另外我参加的饭局里面挂人最多的是软件3班的散伙饭，到最后清醒的男生没几个了，那天外面大雨，饭店前的路积水到膝盖，出租车怕熄火不敢进，我们这些稍微还算清醒的就看着躺了一地的人发愁，后来好歹还是把人都弄回去了，话说扛人可真是个体力活。

临回家前的那天晚上，宿舍哥儿几个吃最后一顿饭。在个饭店的单间，我正闷头喝酒，老王说，把门关好，然后呜呜就哭，结果让这厮搞得全场悲声一片。本以为长大以后就不知道什么叫眼泪了呢，没想到我居然晚节不保了，皑皑。

集训开始了一周，因为还有给OI那边讲课的事，这些天一直都比较忙乱，也没有很投入进去。或者也可能是我已经没有投入进去的斗志了，看着学弟学妹们斗志昂扬的，还有点小羡慕呢，果然是老了。我经常戏称自己现在做题就靠条件反射了，如果一道题不是在读懂的瞬间反应出算法的话，就懒得去多想，俨然废人一个。重新组了队伍，现在和两个05级队员luxu,mdz一队，叫做TJU_Neptune，话说其实我是有点想叫diablo3的，不过diablo/blizzard时代已经过去了吧，也罢。队友的实力是没有问题的，除了条件反射题，想算法的能力应该是比我强的，就是发现比赛时候这俩都有点不敢用机时，好像生怕占了我的时间似的，其实根本没那回事。前几天fzu的比赛，做了几个题，发现我代码能力还没怎么退化，1y率还挺不错。今年我是比较无欲无求了，所以也感觉格外轻松，话说欧洲杯上意大利的心情也是这样的么？据说我是传说中的大队长了，不过迟到次数/电影游戏时间等等目前为止我可能是最多的吧... >_<

宿舍也搬了，现在我是在38斋某宿舍，一台联想R61本本上写上面的话。感觉最近是很多神奇的事情突然涌了出来，有苦有乐有喜有忧，一下子真有点反应不过来，我得慢慢反应反应。

写到这里不知道再写什么了，从头读了一遍，毫无逻辑毫无结构。行了就这样吧 -_-

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

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

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

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

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

补记：最后结果80，第一题和第四题各得了一点分。决赛分数线据说是100多点。

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

第一试 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年后我们不再拒绝外国援助，事实上没有人会因为中国呼吁帮助而认为中国无能自救，相反，与世界合作，真实报告灾情，呼吁和接受帮助正改善了中国在世界的形象。

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

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

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

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

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

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