12 May 10 浙江理工大学邀请赛流水帐 by momodi@OpenLegend

Open是武大长期流传下来的人文精神，也是我们集训队一直的宝贵财富。因此我们在Legend的基础上取名OpenLegend，作为本次比赛的队名。

比赛前一天：

本来是想周六中午BG大家的，结果发现了浙江理工在下沙之后就知道中午来不及BG了，所以改到晚上。晚上的湘菜馆还是挺不错的，虽然我感觉不够辣。。吃饭的时候看大家的状态都不错，都挺Happy的。

周六下午热身赛的时候，Dumbear问了我一句：“我们的比赛策略是什么？”

听到这个问题之后，我顿时感觉大脑空白了几秒。

思索了良久这个问题的答案，回想起了以前在ChaeYeon队伍的时候制定的种种策略，比如赛前要制定表格，说好每个人的读题顺序，想好卡题了怎么办，碰到什么类型的题目让谁做，谁负责主要读题，谁负责帮队友debug等等等等。

在回想完这种种之后，不知道为什么感觉这些策略都不值得提出来，于是跟Dumbear说:“到时候看情况，该怎么样就怎么样吧。”

不过虽然没有继续讨论“策略”这个问题，我仍然在那里静静的思考了良久，或许真正的策略便跟武侠里面一样“重剑无锋，无招胜有招”。

周日上午九点，比赛正式开始了：

简单题H和A：

Dumbear和ISea开始读题。这时候我把每一个题目都扫描了一下。为什么要这么做呢？

这还需要从出题说起，自从去年开始大量出题之后，自我感觉上我对比赛的一些细节问题有了一些很新的认识。比如：一般来说这种强度的邀请赛都会有一个sb题来保证每一个队伍都至少AC一道题。而这种SB题是字符串处理的概率很大，因为字符串处理题好出-.-

在寻找了一圈样例里面有字符串的题目之后，我选中了H，运气挺好的，H确实是一个足够简单的题目。

我在上机的时候Dumbear还问了我H是什么类型的，本想解释一番的我想到Dumbear可能是怕这个题目不够简单，怕我太急了。所以我随口回复了“H是A+B类型的题目。”

AC了H之后Dumbear上来AC了A题。这时候差不多是9点30分，也就是说比赛经过了半个小时了。我猜想接下来的题目应该就没有A和H那么简单了，没想到的是剩下的题目难度也都不大。唯一的压轴难题确是我们几乎没有可能做出来的题。

计算几何D题：

我在写H题的时候就听Dumbear和ISea在讨论有一个简单的计算几何，DumbearAC了A之后我便上机开始敲这道几何题（D题）。计算几何写完之后有个小插曲，就是不知道为什么有一个泛型的函数编译通过不了。在询问了ISea和Dumbear之后，他俩也表示不知道。于是我果断停止在这里纠结，换了一种写法。编译通过并且过了样例之后，我又盯着代码看了一会，继续回想了一下是不是有特殊情况。这时候ISea问怎么样了，我答：“可以交了”。Dumbear附和了一句“交吧，感觉momo这题写的挺仔细，应该没问题。”听到这句话我小小的惊讶了一下，为什么Dumbear会知道我写的很仔细呢？

D题1Y。

状态压缩DP题 B和数据结构题F：

ISea很早就说了B是一个简单题，不过因为题目里面要牵扯到棒球的规则，所以ISea在跟我讲这个题目意思和做法的时候，我只是听了一个大概。不过我还是挺相信ISea的，所以我也就没有追求这个题目的细节，跟ISea表示了一下问题不大后，ISea也是直接去写了。

而后Dumbear跟我讲了讲F题题意以及RMQ的做法。我知道题意之后发现此题就是求一个数列中每一个数的左右两边边比他大的第一个数。这个问题的解法我很早就知道了，代码也很短，所以先把ISea从机器上拉了下来，换我上去AC了这道题。

而后ISea也1Y了状态压缩的B题。

乱搞题I：

接下来ISea和Dumbear讨论了一下I题后发现了其“简单题”的本质，不过这中间有一点点冲突：ISea有一个优美的方法，而Dumbear想直接去暴力模拟。最后Dumbear去用ISea的优美方法写的，可惜的是WA了两次也还没有AC。这时候Dumbear和ISea又再次重新读题，在确保了题意理解无误的情况下，Dumbear没办法换了他原来准备的暴力模拟的方法AC了I题。回想此题，最好的情况应该是Dumbear一开始就写最保险的暴力模拟方法。不过在出问题之后Dumbear能够顶住压力重写代码，还是很赞的。

图论+树形DP题E：

E题样例里面输出的是小数，也就是说E题是两种题目可能性最大：几何题或者概率题。这两种不同类型的题目对我来说完全就是两个极端，每次碰上样例输出小数的题目我都是爱恨交加。

我在读完题之后，悲剧的发现是概率题。

在I题的解决过程中，我仔细的研究了一下E题，发现与概率关系不大，在跑完最短路之后只要两边BFS就可以了。不过因为场上还没有提交这个题目，所以我们也并没有急于去写这个题目。后来在跟Dumbear讲解这个题目的题意和做法的同时，我更加确信这个题目的做法没错。所以做法也没有讲完，我就直接上机去写这个题目了。

写完之后WA了一遍，不过我马上意识到了错误的地方（图有可能不联通），因为这个地方在我刚开始写的时候考虑到了，中间因为I题被打断了一次，竟然所以把这个Trick给忘记了。改过之后E题2Y。

需要转弯的矩阵乘法题G：

在Dumbear写I题的时候，我和ISea一直在思索G题的做法，可惜一直没有找到正确的方向。后来经Dumbear提醒才恍然大悟，原来可以改成递推式用矩阵乘法解决。ISea去写了G。因为还有很长时间去写这个题目，所以我们有足够的信心G题肯定能AC。J题AC之后就是剩下最后一题J了。

压轴题J：

此题是浙江省赛的一个变形，这个题对我们来说是一个很大的悲剧，因为浙江省赛的时候是我们校赛决赛的练习赛，Dumbear和ISea是在参赛，我是在出题，所以没有一个人在当时对这个题有细细的研究。不过因为知道这个题目是一个难题，所以我们前期并没有浪费时间在这个题目上。最后还有一个多小时没事做的情况下，我们才开始细细的推导这道题。

当时有两个思路：

1. 先用强连通分量来判断是不是无解，求这个图的圈覆盖，而后试图把圈合并。

2. 先用强连通分量来判断是不是无解，然后搜索答案。

第一个思路我感觉是比较接近最终答案的，但是因为就连最初的假设“存在哈密顿路的充分必要条件是整个图在一个强连通分量里面”都不确定是不是正确的，所以这个思路并没有发展成熟。

第二个思路比较简单，所以在没有办法的情况下，我去用这个思路试图“水了水”。得到的结果也是理所当然的TLE。在用了各种搜索技巧提交了几十次之后，比赛结束了。

最后的结果是浙大的队伍做出了J题，AK了所有的题目。

我们因为罚时排在了9题第一总排名第二，虽然有些小小的遗憾，但是终究还是输在了实力上，就算没有J题，也是只能第二名。

结束语：

能够和Dumbear和ISea组队很开心，赛后找了一个网吧10个人打Dota内战，大家在尽兴之后开始了此次比赛的结束之旅。

在回去的路上得知了另外两只6题的队伍，一个银牌第一，一个银牌第三。不过是因为输在题数上，所以我想也没什么特别的遗憾。

Dumbear和ISea在赛场上显得很老练，对各种问题的处理也很成熟。我想他们两个再加上我们的传奇人物，一定能够在赛场上取得辉煌的成绩。

虽然今年我们集训队相比去年来说有种种不足和问题，但是我相信今年区域赛我们还是会有更大的突破的。

大家加油～激情比赛，为了目标而奋斗到底：）

Tags: 总结, 浙江理工大学邀请赛