荔园在线

荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀

[回到开始] [上一篇][下一篇]


发信人: huhaiming (一生只爱她), 信区: ACMICPC
标  题: [转寄] 比赛总结[转载]
发信站: 荔园晨风BBS站 (Tue Apr 27 11:00:07 2004), 转信

【 以下文字转载自 huhaiming 的信箱 】
【 原文由 jhun.bbs@argo.zsu.edu.cn 所发表 】
发信人: henryouly (CS01A:不会编程了>_<), 信区: ACMICPC
标  题: 比赛总结
发信站: 逸仙时空 Yat-sen Channel (Mon Apr 26 15:17:18 2004), 转信


这次比赛我犯了挺多错误的。比赛开始的时候,我从A看起,justforplay从最后看
起,Vcenit从中间看。我很快就看完A,以为A就是比赛前所说的人人可以过的简单题
,跟Vcenit说可以马上写,幸好刚刚才打了开头,Vcenit就拉住我说数据范围很大,
而且是2进制的,不是一般gcd,及时把我的错误纠正了(那个sample出得也真阴险)。
然后justforplay说他有高精例程,不过不保证正确性。马上分特了,于是还是决定
先找找其他容易的题目做,回头再看A,这是justforplay说G很简单,就是类似ACM排
名。我大概看了一下题目,也是在score那里有点糊涂,不知道judge脑袋里面卖什么
药,penalty到底有什么用。为了保险起见还是老实写qsort,按score降序penalty升
序来排。这是iamcs他们队升起了一个气球,说明这确实是简单题,才稍微安了点心
。虽然这样,按submit的时候手依然有点抖。submit过去后,看看submissions sta
t,发现是第三个提交,如此看来如果ac的话时间上还是很有优势的。果然很快就返
回yes了。

然后换Vcenit去打D,这是我看了一下气球,无间道已经过了J了,于是看看
J,发现只是梯形求和问题,特别去看一下是否要把x坐标排排序,很失望发现连顺
序都排好了。等Vcenit把D ac掉后,我马上上去打J,为了省事干脆开大数组一
次读进去后再处理,避免忘记每次交换(插一句,事后听说dynamic他们队就犯了这个
错误)。几分钟打完提交,AC。这时离比赛开始大概也就40分钟左右。打开排名网页
看,时间上本和iamcs咬得很近,他们比我们快18分钟。

justforplay一直想H用贪心,见到iamcs的绿色气球还以为他们过了H,这种速度很
可能是贪心贪过的。我做完J后仔细一看气球颜色,发现不对,是深绿的。。。于是
我看C,是凸包求面积,于是问谁有例程。Vcenit用很有信心的语气说他不用例程了
,写得很多,可以直接上去写。真是太拽了,肯定马上让他写,我和justforplay讨
论H的贪心是否正确,过了一阵justforplay说想错了,于是我们再转去B,一致认为
可以贪心,我之前在ural做过类似的题目,也是用贪心的(没有仔细想清楚,其实ur
al那题只是码头r=1的特例而已),于是等Vcenit做完C后准备做B。谁知道他写阿写
,调阿调,20多分钟过去了还没有过sample。我和justforplay真是郁闷,但是又不
敢影响他。总算他过了sample,赶紧帮他想了几组数据,一测,没有问题。然后就怂
恿他提交,总算AC掉了。这时看看iamcs他们,还是只有三个球,估计给哪题卡住了
,我们暂时领先(嘿嘿。。。)

然后justforplay写B,我和Vcenit讨论I。我知道I是特殊的堆排,也曾经想过能否
直接用qsort,但是看看数据大小还是吓住了,不敢写。我们也没有堆排的例程,跟
Vcenit大概说了一下I的意思(这里我犯了第二个错误,稍后再说),就由Vcenit规划
I,这时justforplay交B Wa了,打印出来。我先输入A的高精(毕竟我灌水多,打字
还是有点速度优势的)。因为justforplay的例程是10进制的,而且是4位压缩存储,
所以我打完例程后跟justforplay一起看程序修改成2进制。大概花了5分钟仔细改了
一遍,幸好改动地方不算很多,于是测试sample,过了。再随便出几个10进制不成立
的数据,也过了。提交,TLE。马上想到如果是因为效率不够就郁闷了。。。打印出
来看,让Vcenit做I。没有看出什么头绪来,越来越觉得是效率太差了。。。于是让
justforplay继续看A,我就去看还没有看过的E和F

F题很接近黑白棋,但是又不得不仔细看,很怕是把黑白棋改造过来设陷阱。读完
描述确认没有改造过,没有继续向下看Input(这是又一个失误。。。题目居然把10个
空格这个如此重要的条件放到Input那里了。。。),觉得根本不是给人过的,搜索量
太大了,就算是世界最顶级的黑白棋程序也只能预测到10多步而已(我AI论文就是写
黑白棋的搜索算法的。。。)于是就跳过了。看E,很像树型DP的变形,只是和justf
orplay在如何避免回路的地方产生了分歧,也没有确定出一个比较清晰的算法。Vc
enit写完I,提交返回WA,然后把程序打印出来,我去调试A。胡乱出了一些数据,
终于发现在某个数据除着除着就产生死循环。然后把循环节单独提出来,发现A除B余
数是A,B除A余数是B。这时Vcenit重看I题,觉得我的top的理解有问题。我把top理
解成了最高价格的了。(这个就是我前面所说的又一次错误了)。争了一下谁也说服不
了谁,发了clarification给评委,确认是most benifits,于是Vcenit改I,我和ju
stforplay继续在纸上手动模拟调试A。Vcenit写了一会儿说有个函数要重新写,于
是让出机给justforplay debug A,他在纸上写函数。justforplay很快就找到问题所
在,是我输入例程的时候把大于小于打错了(5555555555,我又一次害了队友)。再交
一次,终于AC了。这时实哥和dy已经分别是6题和7题了,kingfkong也5题,在我们前


Vcenit这时也写好了I了,提交,也AC了,总算夺回第三。这时刚好ranklist停止
刷新。。。

剩下一个小时了(事实上应该只有几十分钟,ranklist好象停晚了一点^_^),和Vc
enit讲了讲B的贪心,Vcenit说金牌之路有类似的,还证明了不能用贪心,要用流来
做(因为返回是WA,所以也就信了)。然后我大概看看金牌之路上的题目,确实模型很
像(可是求的东西不同阿。。。金上面的明显复杂多了,可当时也没时间去仔细想了
),于是我自告奋勇又充当打字员和翻译员的角色,把pascal翻译成c(max居然跑过
来看看我干嘛突然对着书狂打例程。。。)打完,又和Vcenit仔细研究怎么改输入输
出的接口。总算弄好程序了,一测数据,居然sample 1错了,sample 2和3对。。。
马上换Vcenit去调试。。。他也看过很久了,对书上的算法忘得差不多,最后到比赛
结束都没能调出来。。。(虽然说调出来也会超时。。。)

总得来说我们这次比赛发挥还算不错,从前一晚的试机到正式比赛,都没有遇到特
别郁闷的题目,A和I虽然卡了一下,最终还是可以成功做了出来。不过我犯了有史以
来最多错误,不是因为我做的题犯了弱智错误,而是多次误导了队友。如果I和A不是
因为我的影响,应该可以更早做出来。有足够时间去构思E。如果不是F我说不可做,
可能还可以多做一题。比赛开始的时候还可以和实哥他们队咬着上,到了后来幸好还
追了上来。如果下次还有机会的话,一定要再认真一点看题,不能太放松自己了,万
一辜负了队友平时辛勤训练的话,我就成了千古罪人了。。。

最后抗议一下,splutter居然来偷吃了我们队一只香蕉~_~一直到最后收拾的时候
才发现。。。希望两位队友补充

--
Things should be made as simple as possible, but not any simpler.

-Albert Einstein

※ 来源:.逸仙时空 Yat-sen Channel bbs.zsu.edu.cn.[FROM: 202.116.64.234]
※ 修改:.henryouly 于 Apr 26 18:25:12 修改本文.[FROM: scorpio.zsu.edu.cn]
--
※ 转寄:.逸仙时空 Yat-sen Channel bbs.zsu.edu.cn.[FROM: 211.162.69.142]
--
※ 转载:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 61.144.235.40]


[回到开始] [上一篇][下一篇]

荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店