荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: 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软件 网络书店