Just A Blog

    首先我们来假设这样一件事：现在是暑假最后一天的晚上8点，由于某些原因你一点作业都还没做。这里你可以认为你像上条当麻一样去拯救世界了，总之就是完全没有碰过暑假作业。幸运的是你刚好有能够回到过去的时间机器，那么你会怎么做？

Read more

    Th04总算是结束了。这次的参加人数只有22人，和我想象的差不多。

    题目：
    第一题，最大最小博弈。本来是打算写一道ICG的，后来觉得会不会太难了，就换成了现在这个题。很简单的博弈，只需要记忆化搜索即可。

    第二题，异或方程组。改编题，原题是USACO09NOV的的金组题《灯》。当年做这道题时还不会异或方程组，所以只得了11/17。不过最开始给出题目时，数据范围稍微给大了一点，对于某些特殊情况会TLE，这里感谢一下rowdark同学给出这个特殊情况。所以数据范围改小到40，这里向参加比赛的同学道个歉。

    第三题，二分答案网络流。怎么说了，这题会出现二分答案完全是为了针对本省的省选。因为本省的省选已经连续若干年出现了二分答案的题目，而且今年很有可能出现网络流的题目。将这题写出来，也算是给本省的学生一个特殊照顾吧。

Read more

    其实这东西是发表在NOI导刊上的，但是NOI导刊的编辑太蛋疼了，居然直接复制。导致若干个重要的计算公式丢失，所以在NOI导刊上看到的题解很囧。这里我把原来的Pdf发出来，有需要的童鞋请自行下载：

    COCI 2010 Sol(609KB)

    由于各种原因，没参加R2和R3。(主要是比赛时间太晚了，= =)

    首先解释一下为啥到了今天我才完成这篇文章。11月20日考完NOIp之后我回了家，然后颓废了半个月。这半个月过的比较懒散，所以也没怎么写东西。

    11月开始到20日，整整20天都是在为NOIp作准备。按照以往的传统，高二的学生也为此停了整整两周的课，期间南开惟一一个用C++的选手也到了八中集训。怎么说呢，很累、很充实、很快乐的两周，第四次享受这种全天学习OI的欢乐。期间到三中进行了两次模拟赛，第一次因为很久没有正二八百做过比赛了，被高二的学生菜了；第二次虽然拿了第一，但是最后一题已经是第3次写，却还是只得了10分。
    19日中午，MJJ和YSL两个高三的从大学城放回本部，准备最后一次NOIp，能不能够拿到保送资格就看这一次。下午去一中试机，我被安排了带领初三和高一的学生，后来被主任称为领队。离开时专门去围观了今年我和Wagner都比较看好的LJL。回到学校后也没什么必要的事，大家放松一晚，第二天就是战斗日。

Read more

    今天是NOIp2010结束的第三天，正式的成绩还没有下来。就我个人而言，就算是放到江浙一带，应该也是没有压力的省一。但此时心里依然很紧张，因为有几个我所关心的OIer还卡在一等线上，需要等正式成绩出来才能知道结果。

    NOIp2010，算是有史以来最简单的一次了，好几个省的一等线都在300左右。当然，他们是强省。而作为弱省的我们，只有150~160的分数线。听说浙江分数线在320，这可真是坑爹。不过也有说宁夏最高130分、甘肃140分的。不过不管怎么样，能够拿到第一，在省内也算是比较强的了。咱不和江浙那群BT比。

Read more

最后的一个月
    7月初，离NOI只有一个月。
    这段时间一三八的学生主要在我们学校训练。我跟Wagner说我们这里要老师有老师，要网速有网速，要妹子有妹子，于是Wagner就果断拖着Sujiao过来了。ZZL学校因为只有他一个人进队，所以也和我们一起。猥琐小正太因为无聊，也几乎待在微机室。那段时间里Sujiao去参加了北大的夏令营，但是没有能够拿到免面试的资格。7月20日左右，Wagner提前去了上海集训，最后从那里直接飞到烟台。
    中间有7天，吴老师出差，八中没有老师。于是我们去了巴蜀集训，也算是第一次见到了巴蜀的队员。算上夏令营，重庆队一共11人，巴蜀占了6人。其中RJ和CXY确实很强，尤其是RJ，传说中刷过了1000+题的DP优化牛人。在巴蜀的几天除了每天做一套NOI题，还抽出了一天让每个选手讲课。说起来还真是不幸，在某天杯具地考了倒数第2后，我抽到了1号，也就是第一个上去讲课。想了很久以后，决定讲二分图最大权匹配，选择题目时刻意地改编了一下，引入了东方人物中的灵梦、紫和魔理沙。这也成为了后来决定举办东方幻想乡系列模拟赛的一个原因。
    后来的训练也就是每天练题想题讨论题，期间也有过不少的事：比如ZZL的6+1学习方法，即学习六天必须要休息一天，所以他某天没出现，让我们惊讶了一下；CEOI的比赛，本来是染色网络流的第一题，被MJJ用DLX活生生地拿了45分；某天练习题时，惊讶的发现Wagner、MJJ和我，三个人使用三种不同的平衡树，Wagner只用SBT，MJJ只写Treap，而我是除了Splay，另外两种都不会。平时我们累了，就躺在机房临时铺上的凉席上睡会儿，因为凉席是单人尺寸的，被霸占了之后，其他人就只能睡在电脑桌上了。于是某天打算去休息会儿时，发现MJJ和ZZL都躺在桌子上，睡得正香；同样是睡觉的问题，某天猥琐小正太和MJJ因为做题疲倦了，就跑去看奥特曼。好吧，你们看奥特曼我就不说什么的，还疯狂地吐槽+狂笑，我睡个觉被闹醒了很多次。这都算了吧，可是你们别事后疯狂地向我推荐奥特曼行不行!!!
    总之就这样，忙碌和欢乐的一个月很快过去了。

Read more

    NOIp的三场模拟赛总算是全部办完了，剩下的就是之后三场NOIp难度以上的比赛了。
    由于NOIp考纲限制太多，所以每一道题都花了很长时间来设计算法。尤其是这次的第3、4次，想了好几天才写出来。
    Stage.3要比前两场难一些，这是为了卡满分。因为前两次满分都有不少，Wagner觉得这样不好，需要卡一下，就果断决定用一道语文题、一道搜索题来卡满分。结果还是多不错的，上300分的都只有2个。那么就先来说说这次比赛的4道题目：

    首先是第一题，这题其实是改编题，原题是第一届海峡两岸青少年程序设计大赛(CSAPC)大陆地区邀请赛的飞船控制站。不过原题是个环，为了简化题目，我使用的是链。标程的算法虽然号称是O(NlogN)，其实是O(N)的，所以才会有50W的数据规模。这是本次比赛最简单的一题。

Read more

    这是一道水题，但是需要刷很久。

RP游戏

This problem is easy. You just need to output an integer N (0<=N<50). If your RP is very high, you will get an AC.

这个问题很简单。你只需要输出一个整数N(0≤N<50)。如果你的RP非常高，你将会AC。

Read more

备战省选
    NOIp结束后，正好学校开家长会。我爸也正巧到主城区有些事，于是他就自己去参加了。这应该是我到重庆这4年，我爸参加的第二次家长会。其实在开学很久后，我爸都还不是很清楚我在哪个班(= =)。家长会结束后，班头柴Sir特地把我爸留了下来，打算让我爸劝我放弃OI。重庆市33名，省队只有5个名额，对我而言是很艰巨的任务，无论是谁看了都会觉得希望不大。但是我爸只说了两句话：“孩子喜欢信息，我也就让他参加，如果现在让他放弃，他一定心里放不下。不如让他参加，能过当然很好，若是没通过，也就完全死心了。”很普通的两句话，但却成为了我之后的动力。没有了原来的浮躁，因为喜欢OI，所以会去学OI。最后的一局，无论成败，只要我尽力了，结果怎样都无所谓了。
    过了没多久，正式的一等奖分数线划定，7人中有4人拿到了一等奖。其中一个在拿到一等以后没多久就放弃了省选，回去补文化课。
    11月，在网上得知了开哥保送THU的消息。重庆市数学联赛的第一名，直接去了THU的基础数学系。后来开哥告诉我，他原本打算去经济系的，结果THU没要他。于是开哥成为了八中高2010级第一个清北生。
    寒假，原定于开学第二周周六的省选突然提前到第一周周六。半个月的停课时间，缩短至四天。由于正常行课需要使用第一微机室，这四天我们只好在旁边的老微机室学习。四天的时间被安排的满满的，没有新知识，按照顺序将以往学过的内容一点点地复习，熟练。最后一天的中午，经过几天连续脑力的劳动，实在坚持不下去，我趴在桌子上睡着了。等到醒过来的时候，阳光恰好照到我的位置，电脑仍然播放着轻扬的旋律。之后我们前往一中，看考场。

Read more

Ranklist
    五月，连续的三件大事件
    由于某些原因，zlaner休了假，我们的信息竞赛老师换成了吴老师。
    我和小涵成为了2010级信息班的班长。
    学校的OJ正式开放，从此开始刷题的竞赛。在暑假开始前，我成功的到达了Rank1。
    高一期末考试年级49名。综合以前的成绩，知道自己能够进到最好的实验班，就开始放下心弄OI和MO。整个7月，除了开始一周在南开学习MO，其他的时间全部待在了学校。白天8个小时的MO，晚上3个小时的OI。虽然很幸苦，但是也很充实。OI班的人都被分在一层楼，所以晚上总是十分热闹。比较郁闷的是Ranklist上被ccy超过了。
    7月结束后，回家休息了10天。8月10日又开始了第二轮竞赛学习，全天11小时OI。准高三的学长也加入了进来，其中也包括了已经拿到全国铜牌的一位。这段时间是我整个OI学习中比较快乐的时间(另一段就是备战NOI2010前的一个月)，每天学习新的算法，每天切过新的题目，每天打打闹闹。某天晚上，凌晨1点时，WBS还在我们寝室边洗衣服边大声唱着歌(他们寝室没有这个条件)。等到他洗完想要回去时，对面已经关门。没有办法，WBS只好和我挤一个床，因为我们两个都比较瘦。这段时间凯神果断地超过了ccy，排到了rank1，而我滑落到了raank10左右。
    等到集训结束时，算法也学的差不多。25日后，大家就开始赶拖欠了1个多月的暑假作业。

Read more