2004ACM/ICPC交大网上预选赛总结
交大网上预选赛总结
在今天结束的2004ACM/ICPC上海交大赛区的网上预选赛上，我们两支队伍一共做出了8题中的七题，可是说是创造了历史记录。最终排名52位，排名并不是很高（因为前二十多名基本上被4所大学包掉了，没办法，太强了），但毕竟是在正式的比赛中做出7题，而且我们队互相之间的配合这次是最好的一次，尤其是今天我超水平发挥，一个人做了三道,这也都是团队合作的结果。
其实昨天我们都比较郁闷，因为在北大的网上预赛上没有什么成绩。所以我昨天晚上我很早就睡了，但是半夜里做了好多噩梦，多次醒来，很奇怪，我几乎从来没有一个夜里做两三个梦的。起来的时候也已经8点了，照例是先放音乐，然后洗漱，吃了早饭，JIMMY就已经来叫我了。于是我们按原计划先去超市买了中饭，我买了一升牛奶+噢力噢饼干，JIMMY买了汉堡+奶茶，去机房的路上又碰到了bear，于是三人一起走，路上还在讨论昨天北大上的一题。
我跟jimmy到机房的时候居然看到有几个不认识的人在那里，我们不管，找了机器坐下，测试一下发现可以上网，就开始装东西了，主要也就是DEVC++，金山词霸之类的东西，这时候R9也来了，还带来了官方的中饭，也就是公费买的饼干和红茶。还没等我们装完，比赛就已经开始了。
按照事先说好的，jimmy看E，F，我看C，D，R9看A，B，还有G，H再说。然后刚把PDF装好，bear就上来了，说他们队有一台机器不能连网了，他就只能上来了。我看的是C，D两题。英文都比较短。C说的是原始天为2000年1月1日，然后给你个天文数字，问你这天是几年几月几号，星期几，很简单的题目，可是我最怕的也就是这种没什么算法，只要判个闰年就可以了，要我遍的话很可能错的，所以不大高兴做这个。D也很简单，给出一个分段的递推公式，要求整个数列。由于要判断这个数是否已经在数列之中了（题目中是这样要求的）想想很可能超时，所以一时也没什么想法。这时候bear告诉我们他们队的Endymion已经开始着手做C了，他以前做过程序本来就有稍微改一下就可以了。于是我开始帮jimmy和R9讲C，D两题的题意。C已经有人做，D暂时没有思路，想想都会超时。这是R9开始做A，A说的是给一个最大为7*7的矩阵，每一行可以按一定的顺序旋转，要求旋转后使对于每一列来说，要每列的和的那个最大值为最小。我一开始想是动态规划，后来发现数据量不大，应该可以硬搜，所以R9就准备做做看。对于1到7的7种情况，每个情况写n个for...。我觉得比较可怕，不过既然他要试试，那也没什么关系。
jimmy的E一直都没怎么看懂，这题也是后来我们作出来的题中最难的一道，然后看F。几乎不用看题，看个测试数据就明白怎么回事情了。一看就知道是递归，于是我开始做F。jimmy继续看G和H。这时候大概已经过了半个多小时，Endymion说他C已经过掉了，于是我先把他的代码拿过来稍微改了一下（我一直就觉得改人家的代码比自己写要麻烦的多）。过了之后我开始做F，F说的是要输出一个梅花形状的X，最大为7，就是输出大约729*729个字符的东西，并不是什么难事情。我编了一个，自己测试的时候就觉得不对，于是开了.net调试，结果发现是打字打错了，然后再调试，就上去交了。第一次交是OUTPUT FORMAT ERROR。然后我改了一个小错误，再交依然是OFE，我郁闷了。装了个UE自己输出看结果，一直都没有搞出来，jimmy也一直在帮我看，最后他发现题目中要求不用输出不必要的空格。我郁闷，改了，交上去，想想这次总应该对了。
可是这时候交大的系统发生了问题，说B和H的测试数据有问题，需要rejudged，所以我交的F一直是recieved，没有判，十分地郁闷。于是看G和H题。在这之前，bear已经把D给过掉了，居然只要强行生成就可以了，于是jimmy 按照他的方法自己编了一个，稍微测试了一下也交了，R9的A也写好了，写了一百多行，我估计有2，3十个for的样子-_-%，也交了。这是我们最郁闷的时候，都是recieved，没有judge，就等着。不断刷新着state页面。然后自从我第一次递交改完的F之后大概20分钟之后，显示F过了，然后D也过了，A显示超时，果然还是超时！这时候我们已经过了三道：A，C，D，时间大概过了1个半钟头，我马上把F的代码给了另一支队伍。
另一队他们都在搞那个A，自从强行生成超时之后他们就一直在搞。我则看懂了G，G 说的是把2n个数按顺序围成一个圈，然后用直线将他们两两相连配对，一个只能和一个连，而且这些直线不能相互交叉。我一看题觉得很像离散数学中的二部图完美匹配，可是马上发现不对，因为直线不能相交。于是我画出了4个点，6个点的情况，马上就发现应该用动态规划来解决，而且很快列出了状态方程。就着手开始编，快编完的时候bear过来跟我说了他对这题的想法，我跟他说了我的，他也觉得应该是对的。我调试通过后就交了，WRONG ANSWER。我开始拼命想怎么回事情，怎么想怎么觉得方程是对的，这时bear提醒我测试一下最大的情况，我试了一下100，发现是负的，很明显，int超界了。然后改成了long long，试100，似乎没问题，然后又试了50，居然发现两者的位数是一样的，就明白了用long long依然超界。然后bear拿来了传奇人物CCMOUSE所编的大数类LargeInt，我删掉了它的除法和取余运算，然后用……结果发现他居然没有重载int到Largeint的等号，很是郁闷。于是我全删掉，把自己写过的一个大数类弄出来（我写的那个对是对的，只不过一来效率比较低，二来没有除法和取余运算，因为我编不来；P ），我自己重载过那个等号，写代码，调试，交，过了。我不禁叫了一声“yes!”。马上通知了另一个队。
这时大概已经过了2个半钟头了，我的肚子开始饿了。他们的A还没搞出来，已经交了大概10次了。放在我们面前的有B，E，H三题。B说的是给你最多50000个点的坐标，要求找出一个三角形面积最大……完全没有思路，E说的是集合，完全用数学语言表达，很多∑怎么怎么怎么嵌套满足条件，十分麻烦。H 说的是给出一个数字序列的逆序数（线性代数第一章第一节内容），要求这个序列的最小排列。看看ranklist这时交大他们已经都是6道以上了，好几个队已经7道了。明显H做的比较多，于是我开始想H。jimmy在我做G的时候就已经在做H了，他给我看了他列出来的一部分结果，他写了一个，大致想法是交换数字在序列中的位置，结果超时。于是我跟他一起看他写的东西。这时我的状态非常好，马上就看出了这个序列的一些规律（找规律这中东西是我从小学就开始喜欢玩的，嘿嘿）继续一边找，总结，在jimmy根本没听懂我的规律的情况下就开始着手编了，其实不是他听不懂，其实我只是有了感觉，却没有办法用语言来总结。我写完代码之后，自己的输出就不对，又开了个.net的project排错，结果发现是第一个循环时候的边界条件没想清楚。再调试，对了之后交上去，返回output format error,输出格式错。这时候我几乎高兴的和jimmy抱在一起，因为几乎已经对了，我们之后只是在最后多打了几个空格。改了之后交上去，就过了。我们已经5道了。
鉴于他们A还是没有出来，bear开始试着写写看A。我跟jimmy看剩下的两道，B和E。B完全没有想法，E完全没有看懂。就形势来看，还是E做出来的人比较多，于是jimmy开始看E。我很佩服他居然能领悟那些深奥的数学语言和更深奥的英语解释。最后他给我讲了这道题的意思，抽象出来之后，就是在坐标系上有一个柱形图，要求柱形图里最大的矩形的面积。我马上就发现这题跟ZJU上的一道题可以说是一模一样的，以前我曾经见过，可是当时我没做出来。于是我开始在ZJU上找这道题，再简单点说就是把ZJU上1200多道题目都看一遍……当时我肚子很饿，胃已经开始痛了，其实还是这个任务比较适合我，jimmy则开始想这题的算法。我大概看了近1000题左右，Endymion他们终于把A搞定了，于是bear也就不做了，我让bear把A题给交了，我去找Endymion跟他说E的意思，很可能ZJU上的这题他做过。
我跟他说了之后，他马上就说他做过的。然后花了点时间把代码找了出来。我让他过了之后就跟我们说一声。就回到了我们队的机房。jimmy的E其实也快完成了，他跟我讲了他的算法，后来事实证明他的算法完全是对的，跟Endymion基本上是一样的。不过endymion更快一点过了，于是我把他的代码拿过来交……居然run time error。怎么可能~~我跟他说了他没反应，我们只能自己看，结果又交了两次才过，原来是他交的时候多加了一个0，而给我们的代码上没有，又忘了说了。郁闷……
后来我才发现，我大概看了1000多道题目，其实只要再看两道，也就已经找到那道题了……
最后只剩下了B。这时候大概还剩下半个多小时，已经有大约10几个队8道了，7道的队里面我们是排在比较后面的，连我们的领队老师也参与到想算法的行列中来。最后我们对于B还是没有比较好的办法。期间还把H的代码给了南京大学的一个同行，于是他们也7道了……
这次最重要的是我们之间的配合默契。虽然我做了三题F，G，H。但除了F这道很简单谁都会做的题目之外，G要不是bear提醒我测试边缘数据，我可能怎么也不会想到超界，H更有一半以上是JIMMY的功劳，是他把很多数据都写了下来让我很容易地找到了规律。还有最经典的E，是jimmy看懂了题，我是跟jimmy一起把他抽象出来，是我联系到ZJU，是endymion写的代码。
总之所有一切都是大家齐心协力的结果。我们当然不是很强，可是我们也决不比强队差，我相信其实再时间多一点的话，8道也不是没有希望的。只要大家一起努力，什么都是可以实现的。
ACM也基本上就此告一段落，因为听领队的口气似乎交大赛区那边还是让我们上一届的学长去，毕竟这是他们最后一次机会了。至于我么，也不会死抱着最后一点点的希望不放。接下来要把重心放到考研和英语六级上去。有机会的话，还是可以去交大的……
__________________
要么不停地奋斗。。
要么不停地堕落。。
生活就是如此
2004-10-18 01:19 AM 发表 | 举报这个帖子 | 
| 
| 
