翼若垂天之云

坐了一夜火车，在昨天上午十点多赶到紫金港校区，浙江省程序设计竞赛十二点即开始，OIBH队依旧。
嗯，省赛就是不一样，免费发T-shirt，还有免费的午餐和晚餐。由于预习生的缘故，我们属于观摩/旅游队，不计入最终排名。
到了机房里，看到墙上挂着的十二个不同颜色的气球就开始激动，好像都没参加过这么多题目的比赛的说。分配任务，我看A、D、G、J，tzf看B、E、H、K，ww看C、F、I、L。于是比赛准时开始了。
我对自己的四道题目各略读了一下，判断出A是极水的，D不可做，G略麻烦，J矩阵乘。于是在他们两个还没看完自己的题的时候随便就AC了A题。然后他们俩告诉我E和F极水，我看了一下先敲F，没想到挂掉了，我的判断是行末有空格，把输入的方式由gets(s)改成scanf(”%s”,s)就好了。（据说事实上是因为数据是Windows格式的换行符，嗯，对于输入输出的处理要想考虑周全也没那么容易呢。）然后敲了E，AC了。
这时秒杀题已经没有了，在我coding的时候tzf和ww讨论确定了B就是一个裸的最小生成树，没有带模板（事实上，我们没有带简单的算法的代码，比如说，带了最小树形图，但没带最小生成树），我敲了std::sort加并查集的Kruskal，迅速AC之。
接下来，摆在我们面前的是各自手中的三道可做之题，ww的小蘑菇题G，tzf的DP题H，和我的矩阵乘法J。这时，我们队的薄弱环节就暴露出来了，只有我一个coder。如果有两人甚至全部都可以coding的话，我此时做出的决策会是将连续coding了半天的我换下来做点低强度的事情，让别人coding他自己的题。但是，没有这种选择。我的决策是：让ww在纸上写G的伪代码，我敲H，J先放下。结果由于考虑不周全的错误H交了三次才过，原因应该是我的coding状态开始下降。
出去喝饮料、上卫生间、凉水洗脸，回来以后状态好了一些，写一开始就想到思路的矩阵乘的J题，在文件的第一行写上注释“I Love Tan Zhiyi!!!”（别乱想！TZY是我很喜欢的线代老师。）交了两次才AC，是因为输入处理的时候有一种特殊情况，本来已经考虑到了，但因为样例里没有，所以打算先过了样例，然后再把处理特殊情况的代码加上，但是过了样例以后就很高兴地拿去提交，忘了还有一段该写的代码没写，所以没AC。哦……我真啰唆。
ww很快就把G的伪代码写完了，也出了很多组测试数据，交给我coding。tzf推出了L的公式，两人讨论一下复杂度以后觉得可以做，又讨论K无果。我拿着ww给我的伪代码和测试数据、tzf给我的公式，在不长的时间里AC了G和L（事实上coding时还是很磕磕绊绊，没有前几题时的手感），加入到对K的讨论和思索中。想啊想，想出了用繁琐的位运算降低常数的招数，search了一下别人AC这道题的用时，觉得应该就是这样了。不过，我此刻coding手感已经极差了，调试了很久，才发现犯了局部变量未初始化的超低级错误，幸好没有乱提交，还是一次AC的。
这时候，AC了九道题的我们能选择的题不多了。C是计算几何题，我完全不会；D看起来非常难，我们都一点思路也没有；I是长达五页的蘑菇题。结合各题的提交和AC次数来看，D首先被排除，曾经钻研过计算几何的ww想到了C的O(NlogN)算法，意志坚强的tzf看完了I，觉得只是严格按照超级繁琐的题目描述coding而已。C与I之间，我，唯一的coding男，选择了写C，因为我真的不愿意去写蘑菇题的！（分享winsty关于蘑菇题的金玉良言。）从赛后的情况来看，这个选择是正确的，因为I直到最后一刻仍然是有人提交无人AC的，做出十题的金牌队伍都是比我们多了C题而已。
直到现在，我相信ww提供的精妙异常的O(NlogN)的I题算法是完全正确的，交了整整十次都没有AC，或者因为我没有实现正确，或者由于精度问题，我们都不知道计算几何题中究竟应当怎样控制精度。当然，相对于上次校赛卡在二分答案题上的OIBH队，这次我们队卡在计算几何题上，已经心甘情愿许多了。
最后一小时封rank，加上没有给我们发奖（如果我们是正式选手，应该得银奖），所以我现在也不知道我们这个不计入总成绩的队伍的最终排名，大约是12或者13吧。OIBH队在成长，仍没有克服它的致命缺陷。接下来期待暑期集训吧！
最后是用Nokia 5700 XpressMusic拍的两张照片：

为什么我拿着一本圣经？嗯，因为我新手赛rank1的那次就放了一本圣经放在键盘旁边，然后感到圣灵充满无往不胜，所以我打算以后每次参赛都把圣经拿去，作为我的……吉祥物。

Tags: 5700XM, ACM-ICPC, OIBH队, 圣经, 省赛

Related posts

08年5月11日至12日
OIBH队第一次参赛记
08校赛照片
3月11日
Mar 30 2008

五一改短假了，但浙大有七天的“春假”，从上周一到周日，多么充实而颓废的七天啊！
拿到了新的手机，Nokia 5700 XpressMusic，非常喜欢。看重音乐功能、喜欢S60智能机、预算在两千以内，应该是满足这些条件的最佳选择了。用手机的标准来衡量，音质非常棒。照相功能比较弱，2M的镜头很烂，严重偏红，不过我对这方面的要求倒也不高。另外，“扭腰”的设计应该让所有第一次见到的人感到惊艳。完全不轻薄，这应该是目前S60智能机的共同缺点吧（SoariEz同学的超级水货E51不算的话……）。不过，最近读TAOUP，对操作系统的设计自然敏感一些，就觉得S60这目前最主流的手机操作系统令人不满的地方还是比较多。不知道BSD内核的iPhone怎么样？实在烧钱的说……我将来再买手机一定要选Unix类内核的操作系统，话说随着目前iPhone和将来Android的强势，未来Unix全面占据手机操作系统市场的可能性还是相当大的嘛，虽然目前而言Symbian仍是不二选择。
头三天，艳阳高照，陪妈妈姥姥和姥爷仔细地游览了灵隐寺、植物园、西湖几个景区。感想是……要门票的景色的确胜于免费的，飞来峰、三潭印月很赞。5700拍照就是方便快捷，随随便便就拍了好几百张……不过照的都是风景，加上摄影技术实在低能，就不发出来献丑了。遗憾是时间关系没去成白堤上传说中一百六十年历史的楼外楼……
接下来的几天时间，除了写写马上要交的作业以外，就是在音乐和书籍中度过了。哦……好吧还有大量的上网闲逛。消耗前一段时间下载的无数音乐，以及继续更多地疯狂下载。Strauss、王若琳、Avril、Linkin Park、Tschaikovsky（疯狂喜欢啊），加上李志、陈绮贞、苏打绿、牛奶@咖啡（新了解到的，还好吧）是这几天的主旋律。极赞Ein Straussfest、Start From Here、Live in Roxy Theater、Meteora以及Piano Concerto No.1 in B flat Minor, Op.23, I - Allegro non troppo。话说名字里面带琳字的女生我都喜欢，像陈慧琳啊关之琳啊蔡依琳啊范佳琳啊林琳啊，现在又多了一个王若琳。买了社会契约论、中国历代政治得失、沉思录等一些书，不过还没开始好好看，TAOUP的进度倒是不慢。
发一张前几天的书架照供亲爱的fans们瞻仰，这几天新买的书当时还没有放上去，从中您可以看出我的阅读是多么驳杂，以及5700XM的镜头，呃，或者我的拍照技术有多么烂。

最后，今天又新手上路的说。照例发ranklist：

Rank
Nickname
Solved
A
B
C
D
E
F
Penalty

1
Stone Cold
3
0
62(1)
0
0
176(5)
16(1)
334

2
DD
3
0
31(1)
0
0
166(6)
39(1)
336

3
冰之魄
3
0
172(9)
0
0
136(5)
38(1)
586

4
asmn
2
1
90(1)
0
0
0
24(1)
114

5
Aaron
2
0
78(2)
0
0
2
34(2)
152

6
winsty
2
0
120(2)
0
0
0
25(1)
165

7
ll861112
2
0
0
0
0
101(4)
22(1)
183

8
relive
2
0
0
0
0
125(6)
30(2)
275

9
gao
2
0
165(4)
0
0
0
97(2)
342

10
EZ
2
0
176(12)
0
0
0
76(4)
532

11
cscser
2
0
168(14)
0
0
0
114(4)
602

12
vivy
2
0
133(18)
0
0
9
44(8)
657

13
hazy
1
0
23
0
0
0
17(1)
17

14
classT
1
0
5
0
0
7
21(1)
21

15
moondy
1
0
0
0
0
9
21(1)
21

16
wanwei
1
0
5
0
0
0
36(1)
36

17
owen_water
1
0
2
0
0
0
43(1)
43

18
Navi
1
1
0
0
0
11
44(1)
44

19
jack
1
2
3
0
0
2
55(1)
55

20
XO
1
0
3
0
0
5
46(2)
66

21
loulou
1
0
14
0
0
0
29(3)
69

22
cai
1
0
19
0
0
1
43(5)
123

23
小强
1
0
140(3)
0
0
0
8
180

24
听雨轩士
1
0
3
0
0
0
142(8)
282

25
555
1
0
1
0
0
3
150(10)
330

26
我是小白, 大牛轻踩
0
0
7
4
0
0
2
0

27
milki
0
0
0
0
0
0
2
0

5555~~又是由于罚时过多rank1被抢了……重大遗憾是AC三道以后自以为无人能敌，就发起呆来，最后五分钟奇迹般想到D的思路以后大势已去……
打算下次比完以后就不再参加最后两场新手赛了，把积分留给别人，展示高风亮节以及积攒RP。连续两次因罚时的rank 1被抢了，11日是最后的一战，我要rank 1！

Tags: 5700XM, ACM-ICPC, Avril, Linkin Park, Strauss, Symbian, TAOUP, Tschaikovsky, Unix, 五一, 手机, 旅游, 春假, 校赛, 王若琳

Related posts

丁亥除夕
July 14th, 2008
HP Compaq NC6400(RV566PA) #AB2
ACM新手上路总结及感言
08年5月11日至12日