「こんなきれいな星も、やっぱりここまで来てから、見れたのだと思うから。だから・・もっと遠くへ・・」

WC2013 流水帐

day -3

乘飞机到了成都,前往成都七中参加了WC2013前的短暂的“训练”。成都气候各种宜人,不愧天府之国…… 但是住的宾馆居然没有网……

day -2

上午在成都七中做了一套题目,感觉题目各种莫名其妙,下午上课也是讲题。 虽然几乎没学到什么有用的东西,但至少恢复了一些手感……

day -1

上午继续在成都七中做题,题目继续莫名其妙…… 但这两天适应性训练确实找回了不少想题的感觉,应该还是有效的。

day0

前往UESTC参加WC2013的报名。报名时候发了一个照相机形状的U盘,很好玩……(后来有人发现网上售价是25元囧)
表示WC最后一天时候我把讲义弄丢了,下面的回忆可能有顺序错误……

day1

上午wh教授讲了上个赛季的试题分析,然后讨论了CEOI的几道题…… 感觉CEOI的题目很有趣,也没有过于不可做的题目(或许至少选出的几题是这样的?

下午讲了喜闻乐见的平面图与点定位数据结构(梯形剖分)。我在THU集训时候就被平面图屠的很惨,很怕考平面图。 不过当时已经考了2题平面图,今天又讲了一次,觉得WC2013再出现平面图几率不大,压力小了一些。(考试后:你懂的) 梯形剖分什么的就纯属理性愉悦了,完全没听懂。

晚上营员交流,hym的2D物理引擎展示各种高能,现场各种欢乐…… cyf和gjq的科普中在GPGPU破解“某题库”(你懂的……)的用户数据库密码,各种欢乐…… fotile主席的线段树合并感觉很神犇,给COT系列诸神题跪烂了。 lyd和wqs讲的斐波那契堆…… 就彻底不明真相了。 不过总感觉实际速度会被配对堆秒杀……(后来jzp试了一下,似乎配对堆确实秒杀了fib堆)

day2

上午讲了线性规划与网络流,感觉这次讲座是今年WC中最给力的,用代数的方法直接推导出最小割模型真心神爆了。各种带上下界、负权环的流网络的做法也非常给力,解决了我很长时间的疑问。

下午讲浮点误差相关的知识,听得不明真相。

晚上营员交流,似乎除了lyp的py简介,其他都是理性愉悦来的…… 多项式恐惧症,后缀数据结构恐惧症。>_<

day3

上午是IPSC系列题目讲解,或者说是结论题选讲? 所有题目都是构造或者结论。 >_<

下午讲了啥我忘了…… 因为讲义在最后一天被我弄丢了>_<

day4

上午是gyz大神讲的IOI的3道题目和对时间分治的应用。 clj的那个例题太瞎了。。

下午lich讲了矩阵、行列式的一些应用和IOI的剩下3道题目。

day5

上午pku的hjf教授和去年一样,讲了一些科普性的东西…… 下午似乎是去杜甫草堂玩,我没去。

day6 (Contest Day)

先大概花了1h把所有题目想了一遍。(事实证明这个决定很错误…… WC这种难度的比赛其实直接上来就做部分分就可以了)

第一题大概意思是:给一个连通的平面图,边上有权值,反复询问:给任意两点(不在边上或顶点上),要求用长度大于0的曲线把它们连接起来,曲线也不能穿过边或顶点且不能穿过无穷域,使得曲线穿过的边中最大的权值最小。 问这个权值。

这题显然是裸题。平面图转对偶图,然后把MST求出来,然后用点定位数据结构求出每个点到底在哪个域内,然后询问MST上两点之间的路的最大权值,倍增维护MST即可。 但代码多恶心大家懂的。 不过数据很厚道,给了很多特殊的数据,比如类网格图、凸包图等。 我写了类网格图的程序,因为不用写坑爹的点定位数据结构所以比较好写(虽然还是写了300行)。期望得分50分。

写第一题花了我1h…… 这样现在只剩下3h了。 因为在THU集训我发挥的很糟糕,现在必须考得比较好才有机会,而且第一题的朴素和数据生成也很难弄,于是决定赌一把,怒不对拍第一题,直接做2和3.

第三题是提交答案。 大概意思是给若干线性同余方程组,求一个解满足最多的方程。
这题比较简单,有两个点是送分点,两个点可以高斯消元+中国剩余定理,一个点可以DP,一个点可以2^20枚举,一个点可以高精度+中国剩余定理(如果会py就很好写了),剩下三个点考场没看出特殊性。 因为我不会py,也显然没必要为了8分写高精度,所以只做了6个点,期望得分68分。

第二题是数据结构题,很恶心。 我因为提交答案写得太慢,花了2h,所以看第二题时候只剩1h了。 第二题有50分是送分的,还有20分用分块(莫队算法)可以解决。但因为时间不多了,而且我觉得即使没对拍,也至少应该把第一题代码看一遍,防止脑残错。 于是只写了第二题50分的朴素。 期望得分50分。

但结果并不理想: 第一题我数组开小,丢了10分,只有40. 第二题我链+无修改的朴素居然写错了!!!! 差点一口血喷出来。 于是第二题无修改+链的20分就丢掉了,只有30分。 第三题得到了71分,比预想的高,原因是那个高精+中国剩余定理的点我随便构造的解居然得了5分。 总共40+30+71=141分。

不过幸运的是,似乎几乎卡着线进了12人。

当时我看到141分认为没戏了,因为我写的分数应该所有人都会做,而且我还写挂了30分。 但似乎这个分数已经在前10名了…… 果然WC就是比谁挂的少。

clj怒217分屠场,扫描线+平衡树进行点定位怒A第一题神爆了。 lhm本来最后算出来比hym高0.02分,恰好第12名,但hym因为有营员交流和闭幕式情歌对唱(==||)的加分,把lhm挤出了12人…… (hym:《论物理引擎的重要性》《论情歌对唱的重要性》 ><)

12人名单: clj qmd wd xhr wzy gsh hym zwt wkn lg pty ljq

day7

因为飞机晚点,凌晨1:30终于回到了南京。 因为此时没有机场大巴,和wyt一起搭qmd的车子回到了市区。 回到家里睡觉时已经凌晨4点了囧……