荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: huhaiming (一生只爱她), 信区: CIE
标 题: GDCPC随想
发信站: 荔园晨风BBS站 (Wed Apr 23 22:53:44 2003), 站内信件
随便谈点这一个月来参加ACM竞赛（其实说不上是ACM，准确来说，应该是GDCPC）
的一些感想吧。最大的收获应该是终于踏足这片神秘的“禁区”了吧，以前只是有
所耳闻而已，具体是个什么东东一无所知。最后的成绩如何倒并不重要，用“阿
Q
精神”安慰自己就相当于是人类登月的第一步吧，呵呵。以前深大对这个比赛一直
都不重视，即使有人想参加也是只闻其声，不见其影。官方对此不闻不问。这样的
状况在今年得到了很大的改善，学院为这项活动拨了专款，有专门的老师负责，校
内的选拔比赛也还办了起来，内部集训用的五楼的CASE实验室，有若干台电脑（可
惜每台都中毒颇深，逼得要我们的明教练买了套正版的金山毒霸），最后去参加比
赛时各方面也感觉比较舒心。最终的成绩并不算突出，有很多原因，我觉得最主要
的是积累的浅薄和经验的欠缺。现在队内的这十个人，都是刚接触这个比赛。总而
言之，我们是迈出了这第一步，即使我们这帮人得不到个什么结果，也希望能留给
后面的师弟师妹一些宝贵的经验，做一块坚实的铺路石。
※ 经过篇※
※ 校内选拔
校内的宣传在上学期末就已经大张旗鼓地贴开了，可惜都是差不多期末考完试的那
几天。我是刚好在学校主页的邮件系统上看到的。虽然贴出了一些做题的网址，可
惜。。。寒假没有怎么放在心上。一直到这学期开学了，再一次的在bbs发出了通
知。当时是请了中大的郭嵩山教授（他可是中大的领队，人称郭老）过来专门给我
们一个讲座，我去听了之后，觉得蛮好玩的，决定了，参加！那天是星期四下午开
的讲座吧，我记得很清楚。于是星期五我还专门去了一趟书城，搜回了两本书：一
本是王晓东的《算法设计与分析》，另一本是我挺感兴趣的国外经典教材《组合数
学》。那天是二月二十八号。
之后马上看了一个星期的书，觉得并没有太大的长进，真是惭愧?。然后就是准备
3月8号（印象太深了，这天就是妇女节）的比赛了。那天我抽到的是6号签，刚好
STOP就坐在旁边^_^。题目是简单的三道题，三个小时。可惜那时的水平太烂，我
调了两个多小时才把第一题给做出来，太痛苦了。那题就是输出一个N（1<=N<=5）
位数，要求这个数的前i位组成的数都要求是素数（1<= i <=N）。我竟然做了两个
多钟头，汗。。。
还好，之后小健告诉我说只有我和Tiny是完全做对的，这都有点安慰。。。说回初
赛，做完第一题后，我看了后面的题目，第二题是模拟竖式除法求出分数的循环节
的，
当时没什么想法（这题伟明做的思路对了，真强，可惜应该是时间不够），第三题
就有
点愧对小健了，竟然是最短路径！！！！！数据结构里面的!!!!!小健在我做出第
一题
后还专门跟我说，叫我一定要拱出这题，结果却对不起他老人家了?。比赛就这么
完了，
可能是太多人不熟悉的原因吧，做出来的效果大家都很不好，于是就有了：复赛。
安排在3月11号的晚上（周六）6：00-9：00。那打击实在是太大了，第一题是识别
浮点常量，由于思路比较不清晰，很多都比较混乱，我做了足足两个半小时，才调
了
出来，最后却差两个数据没过，真是心情贼不好（后来才知道是读题不认真看清楚
，
真是活该了）。复赛的时候，noid和gxdx都做出了两题，真是NB！
第二题是版本排序的，那晚回来之后想着把第二题做出来，第二天拿去给老师测测
数据，跟同房和小宝聊了一会，在熄灯之后看了部电影，大概2点多就开始写第二
题
的程序。本想用基数排序的，可惜又无从下手，搞得用了一个奇复杂的数学方法
解决了（大概是级数方面的原理吧）。这一搞就是五点多六点。看着日出，就渡过
了我这学期的第一个通宵。。。还好，早上拿去给明仲老师测试的时候，都过了所
有
的数据。可惜成绩还是死定了在那里——一题都没做出来（ACM就是这样，一个数
据
没通过，这题都是废的了）。还好跟小健混了这两年，最后公布进入校队的名单的
时候，还是把我和Tiny拉了进来，要不也没有今天。
※ 组队训练
就这样，我们这九个人（名单方面我都弄在program版的精华区－>ACM专区）就这
么开干了。逢每周三，周五，周日下午两点到晚上九点。我们都准时在CASE实验室
报到。不断地做题，做其他赛区的题目。最容易的题目莫过于美国题了，不会剃光
头。可惜，成绩也不好，老是只是做一题。一开始我和gxdx和老炯一组，noid和
gun和stop早早就类似内定地捆在一起磨合了。。。noid师兄的编程能力奇强，每
次做题都很快，小强（gun）在搜索，递归，回溯方面的游戏题目很有一手，而
stop的英语能力是有目共睹的，强强联合，让我们真是羡慕死了，训练的时候，一
般稳定地都做出了3题，甚至有做出五题的颠峰状态。而本人在搜索方面，递归，
游戏这类题目是很弱的，基本上就是不会做，只能做一些数学题。唯一比较安慰地
，一般的数学题，我都能保证做出一题以上，呵呵。于是，在训练过程中，我所处
在的队伍一般都是成绩最差的那个队伍。当时比赛的名额还是准备着2支队伍的，
我老想着，看来都是没希望咯。。。。。。
训练过程中真的是很辛苦，不过大家相处得很好，可以说是苦中作乐吧，一般都会
偷偷懒这样子，这偷懒中做得“最过分”的，莫过于是老炯了，哈哈。竟然私下有
罢工的言论，而我也随声附和着。后来队伍也有一些变化，先是我和老炯，
babybird凑合在一组，然后就是最强队的雏形—noid，gun，babybird，可惜不是
很稳定，后来还是恢复了原来的老样子。其间，有00级闻名的“高手”客串了一次
训练，可惜由于当天的题目不太适合“高手”的手风，他没继续客串下去，然后当
时的形势紧张吖，由于师弟的实力还不是很够，缺了一个人，在游说cojomy加入失
败之后，我们最后把小宝拖了进来。在我的花言巧语诱惑之下，小宝终于就范了，
kaka。当天小宝加入训练的成绩真是惊天地泣鬼神，全场，只有小宝做出了一道题
，把我们比得无地自容。就凭这个成绩，小宝就中途杀了进来。第二天就确定了分
组名单：我，小宝和Tiny分在了一组；老炯，babybird和gxdx分在了一组；noid，
gun和stop分在了一组。而师弟就是我们重要的——后备队员^_^ 。在后面的训练
中，基本上就是做一些基本的题目，准备比赛了。
其间不得不提的就是中大的一个师弟dynamic了。他是中大校队的，参加了今年的
WORLD FINAL，在3月底的比赛中，取得了世界第八的名次，强！！！我们请到了他
和我们一起讨论了一个下午，可以说让我们清楚地看到了中大和我们的实力差距。
他的知识功底很扎实，基本上每种题目用什么方法做很清晰，这是我们遥遥不及的
。同时，我们在他身上也学到了不少好用的东西，譬如流文件改用freopen啦，
_int64的用法，这些都对我们的训练起着关键的作用。真是感谢他。
※ 正式比赛
经过16次外界传闻的“地狱式训练”,一直到4月16号星期三最后一次训练，终于是
准备踏上了征途。老实说，我是没什么把握的，当时自己的斤两很清楚。自己这组
，会做的题目类型很有限，不外是：模拟题，数学题和一些简单处理的题目。我们
都是抱着尽力就好的心态准备过去珠海的。星期五那天早上，我们准备坐船过去珠
海的，在等小健的时候，竟然碰到了姜书记，在得知我们要去珠海比赛的时候，她
给我们派了校车，专门送我们过去珠海，真是感谢领导的支持^_^（特别是现在的
非典意外，杜绝了路途中的不安全）。过到中大的珠海校区，那边环境真的很不错
，可惜住的地方离比赛太远，走路要二十来分钟。当天周五晚上就是试机，感觉就
是机器比较慢，其他倒没什么，试机的题目都很容易，小宝很快就推出了公式。不
过当时的环境也太乱了，经常是没反应，试机之后已经是十点了，再到老师那里开
个短会碰一下头，大家互相鼓励了一下，回到宿舍就是十一点多，洗刷完毕就睡觉
了。第二天，就正式比赛了，比赛从10点20分开始，一直到下午3点20分。比赛一
开始，只发了一份题目，后来才送来了第二份题目，可惜那时候我们已经开始分发
题目各自看了起来。就不管那份题目，一直都扔在一边。一开始就选了B题
tercher’s game，E题Job Assignment，G题winner，H题sorting algorithm，J题
dependencies among jobs看起来这些题目都是只有一页，对于我们队这些英语
cheap仔比较容易D，先不说做题，读题都成问题的话，看来做题都是无望了（所以
对于C题有五页的篇幅，我们队是连看都不看的^_^）。先是我在看B题，我很快的
就知道是解同余方程组的题目，可是我心里没底，我决定我先不做这题，而是把题
目扔给了小宝，让他接手这题，然后我再筛选其他的题目看。我终于找到了最容易
的H题，是排序的问题，要求对没排序的N个数排好序，并且输出每M个数的第一个
（M的数值会给出）。我马上上机，很快就把程序写完了，排序是用stdlib里面提
供的快排函数，问题是每M个输出的，对于最后一组不足M个的情况下，究竟要不要
输出第一个。在我反复看了N次题目，细细地看清楚英文的意思，决定是不输出。
于是，提交，一次通过。我们组拿到了第一题，起码不会剃光头，压力顿时小了很
多^_^。可是，这时已经是11:32分了，看着第一个气球在机器旁边升起，感觉真好
（每做出一题，都会得到一个代表改题的不同颜色的气球）。我和小宝，Tiny相互
拥抱了一下，马上继续投入战斗中。这时候，我们看到场内升起了几个黄色的气球
，是D题有人做出来了，马上拿题目来看，原来是奇数幻方的题目，要求输出N（
N
是奇数）阶幻方最右下角的数字。
这题简单，我在组合数学里面看过的，方法是有的了，可是N可以到达100万，一开
始用模拟的方法不断地生成，短短三十来行程序就写出来了，sample也过了，但是
考虑到N很大的情况，我试了一下999999，一运行，哇。。。等了足足一分钟还没
有出来，显然的，如果胆敢提交的话，肯定会超时！这时候，小宝对第二题有具体
的想法了，他上，于是，我和小宝换，我把程序打印出来研究，小宝开始写第二题
的程序。对于第二题，我知道是运算规模太大了，我在考虑着一个问题：究竟是推
公式，还是继续模拟，我有方法能把时间复杂度降下来，降成O（n）。可是公式比
较安全，但是另一方面，在N＝999999的时候，极有可能要用高精度（即运算过程
和结果都可能会超出int的范围），那时候我对公式的适用性有所怀疑。就在这么
的彷徨中，我边彷徨，边和小宝讨论他做的B题。最后小宝写完B题，sample过了，
一提交，竟然又是超时！faint，这时候，我尝试上机修改D题，可惜由于思路不集
中，写不出个所以然来。我差点就想着推公式的了。这时候，Tiny看完了一遍题目
，确定A题很容易的，而且当时场上A题代表的红色气球也很多了，这时候，我决定
，我和Tiny讨论完思路后，Tiny上，写A题的程序，在Tiny开始写程序后，我跟小
宝和Tiny说，我需要半个小时研究D题，我一定能做出来，在半个小时里面，无论
发生什么事情，都不要打扰我！在得到大家的支持后，我就一个人在啃D题了，二
十分钟后，我把复杂度降了下来，也在纸上写出了程序。这时候Tiny把A题写完了
，提交，竟然是Wrong Answer，faint！我上，把Tiny写的程序打印出来给他查错
，我继续写D题。很快地，我把D题改好了，提交，竟然还是Wrong Answer，我测试
了一下，果然答案有问题，高精度使用方面有问题。而在这时候，Tiny说不容易把
程序查出错误，在这样的环境下，我马上决定，我先把D题放下，由我重写A题的程
序（因为我知道A题的思路），在我写了1/3正处在无比痛苦的时候，Tiny把错误找
了出来，竟然输出的时候打错了变量名！我狂faint！！！虽然当时肯定是安慰了
一下，说没事，改了，提交，这时候Tiny说好像哪里还有问题，我和小宝听到就真
的有点faint了，我也准备继续重写我没写完的A题，好在这时候，judge的信息回
来了，这题过了！！yeah。于是我们组拿到了第二个气球，红色的A题。这时候已
经是1点39分了。之后我马上停止A题的程序，调D题。Debug跟踪，发现是_int64的
输入输出有问题，不是用％lld的，试了％ld，％d都不行，这时候头就真的大了。
最后是，怎么想不起来_int64类型的输入输出格式，只好换了方法，用int输入到
一个临时变量，再强制转换成_int64，输出的时候，强制转换成double输出，用
%.0lf输出，把小数点后面的全都搞掂不输出。在这种偷天换日的提交下，我们组
拿到了代表D题的黄色气球。到2点35分，我们拿到了三个气球。这期间，小宝换了
J题来做，是关于拓扑排序的，可是我们都不熟悉，小宝用了其他方法写了出来，
这时候的时间并不多，只好这样了，而最后，小宝也把J题好不容易写完，却是3点
了，一测试，sample过了，提交，天啊，竟然返回wrong answer，小宝慢慢地继续
查错，可惜最后到比赛结束，小宝改了一些，可是比赛就在没有任何提示下，结束
了，连改出来的程序再提交一次的机会都没有，唉。。。于是，我们只是做出了三
题。比赛出来后，看到了其他的两队都做出了两题，只有我们组做出了三题，觉得
有点险~~~~~
纵观本次的题目，基本上题目的难度不小，而且要比较小心，好在运气不错,
没
有碰上太头疼的搜索题，游戏图，这让gun的实力没有得到充分的发挥，真是可惜
而在比赛完了之后，陆续知道了一些情况，广州大学剃了光头，华工最好的成
绩
也是做出3题，跟我们一样，汕头大学在比赛结束前还是一题都没对，不过听说在
比赛的最后一个小时，他们还是对了三题，不过比时间，肯定是我们比他们快。到
了晚上公布成绩，中大dynamic的那队做出了7题，强，拿世界第八的实力跟我们就
是不一样，华工拿了第二名，我们拿了第三名，都是同样做出3题，只是时间上，
华工比我们快，真是觉得有点惋惜，如果最后那个J题小宝调出来的话，就排在第
二名了，不过这也是体现实力的地方，毕竟我们还是第一次参加这样的比赛，经验
不足。于是，GDCPC第一届的比赛就这样结束了，而我们也结束了一个多月的训练
。虽然成绩没让自己满意，但也算可以给关心我们的老师和同学们一个不错的交待
了，^_^。
※总结篇※
结合比赛来谈谈我们欠缺的一些方面吧，总体还是觉得我们能做的题目类型很有限
，数据结构方面的内容很多都忘了，也很不熟练（如果熟练的话，小宝就不用对
J
题那么痛苦了），其他方面，譬如动态规划，递归搜索，近似搜索这些方面还是不
太行，譬如G题明知道是动态规划的，就是不会做，干着急。另一方面，我看组合
数学也不扎实，E题是关于完全偶图的一阶匹配的，而我却不知道这样的做法，结
果也是不会做。而B题由于训练这方面很少接触，其实B题我相信已经做出来的了，
小宝的程序超时的原因也是因为没有用到高精度而造成超时。但是在这方面，实在
没有想到也没办法。希望以后的师弟师妹会注意到这些。
闲话多扯了点：）。第二个说说临场发挥和经验问题。这次比赛noid的一组一开始
做了A题，应该算最简单的题之一，很快把程序写好了提交被打了回去，因为没想
到一些容易疏忽的地方，提交了九次才通过。应该算是非常郁闷了！其实是开数组
方面可能越界了，经验是有所欠缺吧。
接下来关于如何提高的问题，用围棋来类比一下。都是竞技类活动，多少有些类似
吧。就个人的体验来说，提高棋力主要靠这几个方面：（以下非本人所写）
1.看高手写的理论书籍，例如定式、死活、官子、打入等等方面的。这个过程
也是
有层次的，从简单的看到难的，没有上限。
2.实战，这个是最重要的！光看棋书，只是获得了概念性的东西，要靠实战来
检验，巩固和发展。脱离了实战的任何东西都是garbage！在实战中感到困惑和不
解的
东西，再会到理论中去寻找答案，学到新的东西后，再运用到实践中去，回环反复
。实战
要尽量和各种风格的对手都下下，越是你的苦手越能学到更多的东西。现在网络对
弈也
比较火爆了，对于一般人来说找寻各种各样的对手也很方便了。可以下的对手多了
，又
一个问题出现了，就是对局质量。如果是为了提高棋力的目的，就不能为了下棋而
下棋
。下完一盘棋，要认认真真的复盘，反反复复的研究棋局的进程，自己哪里下得好
，哪
里出了问题，都要仔细总结。犯了的错争取不再犯第二次。现在的围棋软件都不错
，对
这些功能都支持得很好。我自己就是个很好的反面例子，上大学之后迷上了网络围
棋，
为了痛快，只下直接上来就20秒读秒的快棋，噼里啪啦就下完一盘，完了扔在一边
不管
继续下。只是一种情绪的宣泄，只满足于连切菜鸟若干盘的快感，结果水平越下越
差（
当然我也不想做什么高手，只是玩玩而已）。可以说对实战的反思和研讨是会带来
极大
的提升空间的，否则等于做无用功，甚至退步。
3.很正规的实战也就是比赛。这是非常重要的，也是很珍贵和难得的机会。通
过比赛你能更清楚的看到自己被忽视的弱点。
4.虚心的向高手学习。职业高手在重大比赛的棋谱要常打，要投入比自己实战
棋谱更多的精力去研究，看看有什么值得借鉴的新思路，在对比中衬托出自己的不
足。
如果更多的精力去研究，看看有什么值得借鉴的新思路，在对比中衬托出自己的不
足。
如果有机会可以和职业高手面对面的讨教一局，获得的收获就更大了。
再说就是在19路棋盘之外的一些东西了。天赋当然很重要，但热情、兴趣和追
求可能更有决定性作用。另外个人的修养，习惯和规划也会对棋盘之内产生潜移默
化的
影响。我都没有直说在我们的竞赛训练中应该如何。大家都是聪明人，会举一反三
的。
十月份还有世界的亚洲分区赛，希望有更多的师弟师妹在这方面发展，为
深大争
得荣誉。平时的实战比较少，可以考虑每个月在浙大网站上面的月赛都参加一下，
还是比较有用的，遇到问题的话，多几个人讨论，是一件很好的事情。
就我个人性格来说，不想把比赛结果看得过重，更喜欢把它当作一个愉快的游戏。
但另一方面出去比赛就代表着深大的荣誉，不能当作儿戏。这也就要求平时训练的
时候就要严谨，认真。
以上就是我的一些杂乱的感想吧，写得漫无边际，还很拖沓冗长，大家不要笑
话就是了:)以后，就看师弟师妹们的了！！！！！
--
菩提本无树，明镜亦非台
本来无一物，何处惹尘埃
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.0.200]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店