标题:国软比赛总结 出处:Felix021 时间:Mon, 25 May 2009 01:58:30 +0000 作者:felix021 地址:https://www.felix021.com/blog/read.php?1609 内容: 很纠结地最后可以参加这个比赛了,但是这个比赛只能两个人参加,于是BFS只能拆散了。 Sandy和Boluor组队,然后我另外去找了Eire组成新队,队名70km :D 12点左右就到了机房,结果LCY说对外通知是12:30入场>_<|| 郁闷。 然后随便找一台机器测试了一会儿,到大约12点40的时候被安排坐到team30的位置(可是我们是team51=.=) 花了一点时间把vimrc先大致敲了一点进去,和eire讲了一点vim的基本操作,敲了一个model.cpp 1点多一点点开始比赛,8道题目,可是国软这次这么小气,两个人才一份题目,orz。 于是把题目拆开,Felix负责ABCD,Eire负责EFGH。 还好是中文,看完比较快,Eire说后面四道题目貌似没有直接可以写的 然后我看到B是一个简单的BFS,C是一个更简单的模拟水题 于是直接上去敲C,结果很快就WA了,检查了一下,发现一个小错误,Submit,又WA,超郁闷。 打印代码一边检查,然后Eire看H题,我和他讨论了一下,刚开始想到记忆化搜索 但是发现不对,没有高精肯定要溢出,高精效率又太低。 于是列出一个不太严谨的式子:如果把n拆成x份,那么最后的结果是x^(n/x)(忽略小数) 然后大致证明了3是最划算的(我居然忘了怎么求导T_T 还好Eire还记得。。。) 然后又大致觉得如果是4就应该拆成2 * 2 于是顺着这个不严格证明得出的思路写代码。 其间Felix改了一下C题,又WA,检查代码发现多了一个测试的printf T_T,注释,提交,AC@35min 一个简单的C题被我搞出3个WA。。。罪人啊。。。。 很快Eire根据那个"证明"结果写出了代码,提交,1AC@42。振奋。 然后Felix看B题的BFS应该很简单,虽然Eire有点担心,但是还是毅然决然地开题 写完以后测试发现不太对,打印代码一边晾去,由Eire开始写他想得已经差不多的G题 其间Eire又转去细想,而Felix在打印的代码上面发现了几处错误 改正以后样例基本OK了,然后是最后一个不对 自己看了一下样例,发现是样例错了,于是问judge。 结果被告知出题人kid正在地大回途中,waiting。。。 于是Eire继续G题,由于roman 2 arabic的函数写得很好,然后用一个struct+stable_sort,1AC@114min 这个时候开始网络变得非常垃圾,点一个Refresh就能把PC^2卡死,超郁闷。 还好等了不是太久kid回来了,原来是他把6写成5了,不好改题目,于是就把数据改了。 然后提交之,发现TLE了,超囧。 检查了一下,发现在BFS的循环里面有错,队尾指针在某个情况下不会改变(以前没遇到过),于是很囧地进入死循环TLE 修改了以后检查了一遍,又发现一些其他的错误,一并改之,提交,WA@130+min T_T 很郁闷很郁闷地继续检查,大概160min发现原来是存名字的map在每一个case之前没有clear,超囧。 又提交一次,还是WA!郁闷啊郁闷啊郁闷。 纠结了很久,大概30min以后问了maner是不是最后一个case后面不需要再加\n maner说,大概是。。。于是改之,提交,终于AC@196min... 剩下的四道题目和Eire讨论了一下: A题是一个枚举+二维DP的问题,Felix能想出这个框架,但是实在是不会写DP,无奈放弃 D题状似计算几何,但是细看其实不然。Felix也想出了应用容斥原理的算法基本框架,就是不会写T_T E题可见边——Eire很后悔地说没有带上图形学的书。。。 F题奇怪的比赛——完全没有思路,嗯。 此时70km@Rank2,仅次于momo+feli。 但是后面好几个队伍都出了3题甚至4题,估计很快就能超过我们,郁闷 更郁闷的是LCY同志宣布:由于比赛过程中网络状况比较差,比赛延长半个小时 于是我深情地拉着LCY的手说:我恨你T_T 由于最后一个半小时都没有题目可以做,于是Eire在5点多一些就先跑路了 Felix非常无聊地水了一下D题,毫无意外地TLE,于是也不再继续写了。。。。 —— 最后非常意外地70km还是留在Rank2的位置。究其原因,主要有这么几点: 首先,因为从地大回来的队伍不仅推迟一个小时才开始做题,而且都太累了——毕竟写了一天的代码啊,此乃侥幸。 其次,做题策略把握得比较好—— a) 看题,我们把所有的题目都快速扫过去,没有一看到简单的就急于做出来, 因此在整个比赛的过程中基本上是按照从简单到难的顺序做出来,这个还是比较划算的 b) 比赛的过程中时间安排得好。一旦觉得自己会陷入僵局的时候就打印代码换人写 事实上确实是,在纸上看代码很容易找到代码的错误,并且往往一次能找出不止个一并改好 c) 把自己的想法适当地和队友讨论,这样能让自己明确自己的思路,找到自己可能存在的问题, 同时如果自己存在问题,也可以借助队友的局外人身份找出(旁观者清啊!) 再次,河蟹的队伍气氛也很重要。整个比赛过程中非常开心,无论是卡题还是AC还是WA还是TLE(其实后两个结果都是Felix的贡献T_T),都可以笑得很happy,一点沉重的气氛都没有,我觉得这对队伍比赛时的状态有非常积极的作用,让我想起的去年暑假集训的Matrix76队,气氛一向都是非常河蟹。 此外,发现自己的基础还有很大一部分不扎实,主要体现在: 1. 简单的DP不会写..... 2. 容斥原理不会写..... 3. 算法流程没有完全想清楚就开始码字..... 4. 一个BFS能写出好几个错误,边写编改..... 5. 居然能挂在初始化上面,无语啊无语啊无语。。。 以上,OVER,特别感谢队友Eire同学,嗯。 Generated by Bo-blog 2.1.0