荔园在线
荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: kaman (The last The best), 信区: ACMICPC
标 题: 上海赛总结
发信站: 荔园晨风BBS站 (Sun Nov 26 12:23:09 2006), 站内
2006年11月20日中午,深圳大学ACMICPC代表队Aspire全队成员:
Alec Liu、Kjshris Kong、Kaman Chow、替补XY Deng
和Miss Pang、李老师,开赴上海参加31届ACMICPC亚洲预赛。
到了酒店已经快下午5点,去上海新世纪逛了一下顺便吃饭,
回到酒店躺下就着(means 睡着)了,半夜醒来,想起前一天晚上
通宵还没整理完东西,于是开始又整理,那时候整理到二分图的
匹配和相关的应用。到了凌晨2点多总算读完带到上海的书之中关
于二分图的东西。倒下又着了……
第2天要到上海大学新校区抽签、热身赛、还有晚上组委会宴请
各参赛队:)。抽签之前开了个玩笑,说我们抽到的号码一定会有
个4,因为上年的比赛那个4字跟我们跑完成都杭州、赛场酒店饭馆……
这次抽签的结果是114……
下午热身的时候发现旁边就是thu威震江湖的zhuzeyuan、候教主和林mm的
香格里拉队,他们的左下就是这次夺冠的thu的楼教主的队。仰慕了一下
各大牛人,然后比赛就开始了。热身赛是3道题,1道听说是史前简单题,
好像Kjshris搞定,另1道是说一个这样的数集:
1、1和2属于这个集合
2、如果a和b都属于这个集合,那么ab+a+b也属于这个集合
3、除了上述的之外都不属于这个集合。
问题是给出一个数,判断是否属于这个集合。
Alec跟Kjshris讨论之后得出一个很神奇的性质,如果这个数+1的质因数只有2和3
那么这个数就属于这个集合,反之,不属于。跟着Alec秒了那个题。
还有一道就是我看的,描述比较复杂,以后再贴出来讨论讨论吧。
当时跟Alec讨论了半天都没有达成共识,隔壁的香格里拉队敲了半天也没有AC那题,
然后我们就开始提交各种各样的东西要调试一下裁判 :)。
热身完后似乎还有一个sun的讲座,还有T-shirt派送,鉴于上海又冷又下雨,我们
就放弃T-shirt,全体逃回酒店……
组委会的bg出乎意料的丰富。晚饭后我突然想起了Space上的东西忘了打印出来,
于是决定手抄必要的部分。其中有一个是“最小点对”的算法,我看了一下UVA 10245
(最小点对的一道题)Alec的时间比我要快,于是叫他找程序看,发现他写了N百行,
还什么红黑树什么的。只好找《算法导论》看,Alec还按《算法导论》所说的重敲了
一个出来,后来发现黑皮书上也有,根据黑皮书改进了一下实现提交,时间居然比
我之前敲的还要慢差不多一倍。研究了一下两个算法的稳定性等方面,做了一下
必要的记录,时间又到了凌晨2点,倒下又着了……
终于到了正式比赛。比赛在22号上午10点钟正式开始,按照平常一样Alec先分了一下
题目。我拿到的题第一道是A题,我才开始看题目,隔壁的thu已经开始敲了,看了之后
发现是上海赛区on site的择队问题,规则跟现实的规则基本一样,10分钟左右敲完,
提交的时候已经是全场第13个提交,不一会就返回Yes。这时候Alec跟我说了一下D题,
说要离散化处理,不过还没完全想清楚。看了下Ranklist发现有队已经过了C题,
Kjshris跟我说了一下题意,说怎样把一个图一分为二,而两个图的节点的权值和的差
最小。我看了一下题目上面的图觉得怎样像树形图,Kjshris说不确定是不是,于是
我重看了一遍题目,发现真的是树形图,简单一个dfs实现了,提交的时候是43分钟,
1Y,那时候排名升到第5名。Alec跟我简单的说了一下D题的实现,然后就上去敲。
我于是开始看G和E,发觉是一些bt的图题,准备等Alec搞完D后给他。我看到B有点
思路,于是开始想B,Kjshris看完题目之后想I。Alec敲完题之后,我提出他那种
实现的一些缺陷,出了些测试数据没有通过,只好改实现。讨论之后找到一个相对
好点的办法,Alec实现之后提交返回WA,检查程序发现只有一条线的时候没有处理,
处理了之后提交还是WA,两个人弄了不知多久,提交又多了几次WA,于是Alec random
1000组数据,穷举算出答案,然后跟自己的输出做比较。那时候发现不少队过了I,
我于是跟Kjshris一起想I。Alec测完1000组之后还是WA,我只好放下I帮他重看一遍
程序,提出了几个疑点都被他驳回,最后发现了一个算变化值的地方可能会有错误,
Alec改过来后半信半疑的提交,PC^2返回“Yes”,两人不禁震惊了几下……
时间那时候只剩下1个多小时,于是我们决定全力搞I题,I题是问杨辉三角形的第N行
有几个数不能被质数p整除。Alec跟Kjshris讨论了很久之后又找到一个很奇怪的
性质,不过还没最终推出来,而时间只剩下半小时,我只好开始乱敲I。到了结束前
10分钟左右,我终于过了sample和自己的几组测试数据,交几次居然都是runtime
error,慌乱之际对几个可能超范围的地方强制限制,再交了几次,可惜比赛跟返回
的结果都是“time limit exceeded”.
比赛的结果永远定格在3个气球,我们气愤的望着两支thu的7个气球,无限感慨~
颁奖最后拿了个银奖,对Aspire来说只象征安慰奖的成绩。
颁奖会出来还是大风大雨,在回酒店的路上想到了I题一个logN的办法(不是最好
的办法),只好拿头撞了几分钟车窗……
总结:
我还是那些老毛病,知识面不够广,数学太差,某些时候不够清醒。
不用数手指都知道,我只剩下一个机会了,
努力、加油。
Kaman Chow
2006-11-26
--
Science is what we understand well enough to explain to a computer.
Art is everything else we do.
———— Donald E. Knuth
※ 修改:·kaman 于 Nov 26 16:56:43 修改本文·[FROM: 192.168.14.224]
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.111.200]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店