标题：福州赛区总结 By Felix021@烤馍馍 出处：Felix021 时间：Tue, 23 Nov 2010 01:43:44 +0000 作者：felix021 地址：https://www.felix021.com/blog/read.php?1958 内容： 虽然说最后的结果没有比我预期的差，但是过程还是很囧的。鉴于这里是我自己的博客，废话就多写一点。 总之就是从10月的某个Hi消息开始的，jieyu突然告诉我，搞到了一个福州赛区的名额，和ldl同学一起，组个队伍，参加区域赛。缘由很简单，他想公费回家，顺便打个酱油。于是名叫烤馍馍（OpenKaomomo）的酱油队诞生。 真是很久没有做题了。做题的日子是很快乐的，至少可以把日子过得很简单的，其他七七八八的事情可以暂时放到一边，虽然有些不负责，但是突然觉得一切都变简单了；除了那些迫在眉睫的事情不得不分出时间来处理之外。 于是开始到机房和ldl一起做比赛，并且开始在WOJ上面刷题。大概做了四场比赛吧，WOJ的题目也刷七十多道（当然基本都是简单题），慢慢的找回了大二时的那种感觉（其实就是花大把的时间DEBUG那些BUGGY CODE）。不过之前不是搞得特别清楚的东西，在时间的积淀下，很多都豁然开朗，写起代码来也顺畅多了。 前往福州的旅程是比较曲折的。其实那一堆人里面我是最没有区域赛参赛经验了——因为这是我第一次（估计也是最后一次）参加Regional。所以在出发前两天（周三），我也还等着通知，在群里头问何时何地集合。然后发现原来大家也都在等。于是只好给董哥打电话，问。说是车票买的周五的，不是周四，要和实践办的叶主任一起去。于是给叶主任电话，约好，第二天到他办公室，谈清细节（到BBS上发集合帖），领了400块钱，下午拉上钟安原和FOUR两位同学一起到学院旁的自强去采购了320块钱的食品。真重。 周五下午3点机房集合了，把吃的东西分发，然后13个人（包括甜菜和CW）挤上一辆面包车开往武昌火车站，吃零食，看小说，看电影，睡觉（还是甜菜比较简单，从上车睡到下车），早上10点，抵达福州。真暖和。穿太多了。领着大家在公交车站等了半天308，到宾馆把房间开了，然后在天峰宾馆站等了半天91，然后在福大东门又等了好一会儿96，好不容易到福大，才跟志愿者MM碰上面。顺便说一句，志愿者MM也是福一中的，高中学妹啊。在福大食堂吃饭，jieyu和ldl随后赶到，一起吃饭去参加练习赛。进场的时候就已经迟了一点。 总算切入主题，练习赛。练习赛一共五题，ldl从后往前看，我从前往后看，jieyu看中间。A是简单的字符串处理，ldl速度上去敲，居然WA了。然后是我看的E题，素数筛法+因式分解，ldl上去敲，但是他筛法什么记不太清楚了，于是换我（正好前一阵写了好几题类似的），敲出来没有过样例，打印代码。帮ldl看A题，发现是题意没看清，100个word看成100个字符，AC。然后看自己的代码，发现有两个BUG，改了提交，AC。接着是B题，刚开始觉得最小生成树是错的，后来jieyu仔细考虑，发现如果用kruscal是可以保证正确性的。ldl敲。WA。WA。WA。看了一遍代码以后，发现是找边的循环退出条件位置不对，如果最小生成树只有1～2条边，就会出错，改之，AC。于是发现自己还是很适合搞DEBUG。这是好事还是坏事？考虑C题，SPlay有模板，不过题目的难点不在于SPlay，而在于树的输出，考虑了很久，最后放弃了。D题的图着色，写了暴力算法，不过没交。比赛结束，3题，排名78左右。练习赛的总结是，必须要给出一些极端测试数据，不能乱交。 结束后回去等车等得很痛苦，尤其是福大东门的91路……等了四五十分钟，最后还是让老妈和舅开车过来把大家接到南洋饭店吃了顿好的。晚上睡得不安稳，4点多被噩梦闹醒，然后噩梦不断，迷糊到早上7点出头，被闹钟吵醒。下楼吃了早餐（这个酒店的早餐不给力啊），然后坐车。志愿者说武大的队伍在10号车，上车坐了好一会儿说是错了，应该在14号车，结果走过去又说是13号车，上车后董哥电话问：你们上了3号车没……真是攒足了RP啊。 决赛奇葩地在9点30开始。10题，照例ldl从头，我从后，杰瑜中间。 最初是暴力的j题在100分钟AC的。首先是过不了样例，发现是忘了处理不合法的前导零。然后发现程序还有BUG，数组索引有错。然后提交，WA。jieyu检查发现是因为直接用除法，没有考虑整除。我则认为可能会溢出，改用long long进行乘法。于是AC。 第3个开的，F题是个AC自动机，就是数据量BT了一点。ldl敲完标程，过了样例，但是我出了个很弱的数据就跑错了。修改了以后提交，TLE。TLE。TLE。ldl一直比较紧张，到最后才45min的时候才静下心把问题找出来，AC。 第4个开的题目应该是B题吧。无向图最小割，被我读成了N个最大流，又是我的错-。- 总之就是TLE+TLE，在比赛最后7分钟的时候貌似还提交了一次，TLE，放弃。 H题，这题就是个大杯具，开的第2个题，AC的最后一个题。问题大概应该算在我头上吧，因为最初的时候没有把题意完全看清楚（固定的5分钟间隔），导致思考的时候出现各种偏差，提交了3次，都WA了。最后一小时我提出一个很繁琐的算法：记f[i][j]是表示在i分钟第一次选(0<=i<=4)，到第i+5*j分钟可以得到的最大值，for (i = 0; i < 5; i++) f[i][j] = max{ f[i][k]+g(i+5*j) | 0<=k