一段灿烂的记忆,一个冬日的故事

  最近在推Narcissus,于是决定就拿这个做标题,感觉很符合我当时的想法。

  

GDKOI2018

Day 0

  早早的回到了学校。但也不知道要做什么,就在校门外的M记回想着我过往的OI历程。在快吃午饭时敲了下Dinic和SAM的模板。

  下午是坐车去广二的,整理好房间后基本上就在颓颓颓了。

  

Day 1

  早上起得晚了,差点迟到。

  开考先看题目,T1题面很长,没看懂;T2字符串题,似乎比较可做。T3统计中点,计算几何?T4计数题,感觉很不可做。

  重新浏览了一下T1,看懂题目后,似乎就是一个显然的二分+最短路?

  然后去思考T2,容易得到一个$O(NM)$的暴力做法。但想题时始终认为必须要找出所有的关键字的位置,就被卡住了。

  大概卡了有30min,没有得到什么优秀做法,就先去敲了T1。

  敲完T1还有2h30min左右,经过简单的博弈,决定T2暴力然后去想T3

  在脑海内模拟了一下T3,似乎是个二维FFT的过程?这种黑科技怎么可能作为考点。

  去看一遍数据范围,发现$x,y$很小,好像可以一维枚举+一维FFT来避免二维FFT。时间复杂度是$x^3 \, log \, x$的,时限上有点紧。

  纠结了15min,没想到什么好的做法(中途想出bitset做法, 然而只有70分),于是还是码了这个会被卡的FFT做法,中途因为蝴蝶变换写错了,卡了30min。

  码完T3,大概还有30min的样子,拿来对拍T3就结束了。

  

  出来后,大多数人是两题,tututu和KsCla是三题。

  和tututu,KsCla讨论了一下T3,他们都是把二维转一维后FFT,时间复杂度$n \, log \, 100x$。感觉有理有据。

  

  下午评讲,T1倒着来可以少个二分;T2是在AC自动机上跑暴力的思想;T3是tututu,KsCla做法,把二维转一维再FFT,中途某位出题人上去说,枚举+FFT做法(即我的做法)跑了4s。。。T4没听。

  

  期望得分100+40+100+0=240

  实际得分30+30+10+0=70

  T3莫名全RE了,码了FFT都能RE?原本想去复评,但心情不好,就没去了。

  

Day 2

  上午讲座是数论和dsu on tree。数论内容全部都懂,因此全程打炉石。后面听了下dsu on tree。

  下午的DP题十分有趣。

  

Day 3

  想着要在Day2翻盘,因此早早地起床了。

  开考看题,T1匹配问题,感觉不可做;T2是个有上下界的最短路径问题,感觉不太可做;T3环计数问题,感觉可做;T4染色问题,感觉可做(雾)?

  我可能看的是假题面?

  

  最后还是决定按顺序切题。

  先回去想了下T1,大概20min左右,发现似乎分4块推推公式就完了?

  然后拿了一整张草稿纸推公式,大概1h30min左右码(tui)完。

  接着去看T2,似乎选了的边设为下界,其余设为上界,然后跑最短路就行了?感觉有理有据。(Naive!)

  在2h30min左右,码完了T2。

  看T3,我会L=2的DP。记录下是否与第一位相同就好啦。(然而当初没想到,L>2也可以这样子记录)

  看T4,好像不是可做题啊。。。最后水了10pt的暴力DP。

  

  下午就要去长沙了,所以就没听到评讲。中途被KsCla hack了T2的贪心做法。

  

  期望得分100+?+20+10=130+

  实际得分40+0+20+10=70

  

  T1的思路似乎错了,不是很清楚。

  晚上看到了成绩总表,毫无悬念的Cu,翻盘失败。

  

PKUWC2018

  由于不喜欢THU对体育的态度,因此来了PKU。

  

Day 0

  报到日。

  不给试机,因此看了下系统就走了。

  

Day 1

  开幕式,内容挺有趣的,讲计算机前身、今世和未来。

  

  接着就考数学,感觉选择题还是比较简单的,高中数学就能切掉。

  简答题也是蛮好玩的,T1应该对二进制讨论一下就能证明;T2分成多个矩形然后跑DP;T3算是个签到题吧,用三角形性质+平方的性质容易得到上下界;T4感觉是不可做题。

  由于时间不够,选择题蒙了几题,简答题也只做了T2和T3

  

  下午机试,有点紧张。

  开考看题,T1好像是启发式;T2似乎DP题;T3斗地主,大搜索题。

  返回T1,推了一下式子,感觉用Splay+启发式合并维护子树就好了?

  然后赶紧码码码,大概花了1h,打出一个6kb的代码。

  中途一直在Debug,花去了2h,但提交的分数一直为0。

  

  当时心态应该是有点爆炸的,跑去看榜的时候,发现T1有20+人AC,200分也有3个左右。

  那时博弈得到的决策是,切掉T1然后码T2暴力得大众分。

  但结果并不顺利,我的6kb代码到最后也没有得分。

  最后30min时交了T1暴力。

  

  得分40+0+0=40

  

  出来后得知Coming和KsCla也没调出T1。

  晚上我们的心情都不是很好,毕竟知道正解却切不掉是一件很难受的事,更何况现在还是IOI赛制。

  

Day 2

  第二场机试。

  

  开考看题,T1应该就是状压DP;T2排列概率计数,似乎是可做题;T3感觉不可做,但是暴力高斯消元有20pt。

  决定先想T1。

  容易得到一个$N \cdot 4^N$做法,压压状态大概就变成了$3^N$做法,这个有50pt。

  感觉中间有很多状态其实是没用的,试着Map+反向DP,结果T到30。

  

  当时思考能否通过枚举最大独立集DP。这样就是$k \cdot 2^n$了,$k$为最大独立集数,感觉有理有据。

  但是我很快hack掉了这种想法:有$x$个联通块,每个联通块为$\frac{n}{x}$节点数的完全图,显然该图最大独立集数为$(\frac{n}{x})^x$。利用导数求最值,发现这个数字大概在$10^3$级别的,这样是会TLE的。

  

  考虑到这种极限情况后,我试图进一步改进DP:发现每个联通块的最大独立集数最大不超过$n$,能够每个联通块进行dp,最后合并。这样时间复杂度为$\sum k_i2^{k_i},\sum k_i=n$,这个和氏的上界为$n \cdot 2^n$的。

  是一个十分合理的想法。估算一下,代码量应该要3~4kb左右。然后我去查了一下T1的代码量,没有一个>2kb的,当初我觉得我可能是想错了。

  因此只好继续思考其他方法。但是那时候头脑已经很混乱了,什么都思考不进去。等我意识到的时候,只剩下40min。这个时间,我连最开始的想法都没时间实现了。因此只好码暴力走人了。

  

  最后得分50+30+0=80

  

  出来后我表示我被T1卡死了,结果Coming爆出一句T1是个大水题。

  听了下他的做法,不是很懂,但貌似压一个$2^n$就好了。

  KsCla则表示他就是枚举独立集A掉的,这个数据居然没有卡这种做法,太水了吧。

  

  下午跑去等面试名单。面试线是200,我们什么都没有。

  离开长郡后,就去玩了下游戏机室。但心情始终不是很好,玩了一会儿就离开了。

  

Day 3

  早上听评讲。

  D1T1做法没问题,不过用上线段树合并可以少个$log$;D1T2听起来是个很简单的DP,不过考场上没去想。

  D2T1有很多选手是枚举最大独立集A掉了,数据没卡,感觉很亏;D2T2是一个很有趣的题,最后使用上了FNT;D2T3不太记得了。感觉Day2的题目很棒,区分度做得很好。

  

  但回想起自己的考试安排,却好像是初次参加考试一样。明明5h3T对于GD选手而言(GD 4h4T),应该是有很大优势的,结果却打成这个样子。

  在当初被某道题卡住的时候,就应该选择去换题,而不是在这里硬肝。自己的考试经验不足,这是最大的问题。

  

  评讲完后大合照,原本都打算溜了,结果被告知全部营员返回。

  回到原地点后,发现似乎是正式营员都有约。

  后来拿到约后发现是个废约,省队 降20+NOI ABC前100/D前50 一本+NOI D前100 降60。

  PKU这么做,应该是为了尽量地招揽人才吧。

  

WC2018

Day 1

  报到日。

  建在了一个未开发的区域,学校特别大。而且校外的很长一条路上都能看到NOI的宣传。

  

Day 2-5

  Day2: LZZ和matthew99

  Day3: jiry和zzx

  Day4: wys和immortalCO,apiadu

  Day5: yjq和xumingkuan

  Day3和Day5的晚上都有营员交流。原本对LCA的卷积定理内容很感兴趣,但到后面还是一脸懵逼了。

  

  这次上课感觉挺欢乐的,还玩出了一些梗(电音之wys)233。

  而内容感觉也很棒,质量很高。

  

  这么多节课中,我最感兴趣的应该是immortalCO的动态DP和apiadu的超现实数。

  特别是apiadu的超现实数,那节课让我受益匪浅。

  

  Day5晚上敲了下FFT和Treap的板子,都是1A,不知道有没有用。

  

Day 6

  开考先看了下题,感觉每题都能拿到不少的暴力分?

  大致想了一下,没有什么更优的思路,于是决定先码T1暴力。

  

  先水了T1的$n^2$暴力,没花多少时间。

  然后去想T2暴力,一开始以为是$n!$相关的做法,后来我发现貌似状压一下就有50pt。

  这个没有犹豫,我觉得50pt已经够了。于是直接码了起来,测大数据时发现WA了。

  我以为是自己的欧拉回路想错了,然后在纸上推了一下,的确是有点小漏洞。

  补了这个小漏洞后发现还是WA?喵喵喵?

  这时候看下时间,发觉已经过去2h30min了。

  

  冷静一下,决定去码T1直径的16pt。

  大概10min码完,然后花了20min对拍上

  一切顺利,决定再回去搞T2,这次我直接把欧拉回路改成用网络流判定,这下没问题了吧?

  结果还是WA了,最后我选择放弃T2。

  此时,大概剩下1h。

  

  跑去看了下交互题,感觉type=1/2/3都能做。

  先码了个type=1的$n^2$暴力,然后再拿了type=2的$n \, logn$的点。

  最后思考了一下type=3的做法。一开始,我考虑随机取点去扩展左右端点,但这样分析,虽然期望次数不错,但最坏还是$2n$的。

  考虑到数据可能会卡,再加之实现起来并不容易,最后决定去掉随机,选择暴力扩展。这样是严格$2n$的。

  码完这些后,大概就结束整场比赛了。

  

  出来后听说T2改了题面,不过由于广播问题,非集训队选手都没听到。不过集训队选手没受到影响,算是不幸中的万幸吧。

  吃饭时,KsCla告诉我,随机取点的做法实测是$n+logn$水平的,这种做法的确十分优秀。不过考虑到当时时间问题,选择$2n$的决策应该没问题。

  

  下午评测,ufozgg为了填锅,用了两种数据去测。

  最后成绩28+40+50=118

  KsCla的T3随机取点多拿了20pt。

  T1的取直径做法忘记开大空间,然后对拍的时候又是按照$3000$来拍的,就没发现问题。没拿大数据去试,的确是考试时的失误。

  

Day 6-Night

  晚上去文艺汇演。

  有几首退役歌,感触还是挺深的。

  

  中途插播了集训队的滚榜,看到了很多实力选手爆炸。

  原本被钦定的fateice,因为WC爆炸,差一名进入备选队。

  还有实力强劲的whx,因为清华集训的爆炸,被迫离开oi。

  

  集训队的各位都很强,但这毕竟是竞赛,总有人要被淘汰的。

  最后whx的话,也说出了很多选手的心声。

  

  看着各位高三选手一个个离去,觉得自己现在能留在OI真的很幸运。

  虽然大学后还有ACM,但那时候大家的意愿都有所不同,物是人非事事休,留下的,还有多少个故友?

  

  真的很幸运能来WC,虽然成绩失利,但那毕竟是自己的问题。

  能见到各省的OIer,一同在雅礼创造出美好的记忆,虽然互不相识,却异常温馨。

  如果可以,我还想再来一次WC。

  

 如果生命只有最后一天

 我想获得真正自由

 即便

 只有短短的一步

 

 如果生命只有最后的一天

 我想摸摸张熟悉的脸

 哪怕

 是在无尽的梦里

 

 如果生命只有最后一天

 我想看到幸福的未来

 即使

 只是短暂的一瞬

本站总访问量次 | 本站访客数人次

Powered by Hexo | Designed by iTimeTraveler | Refined by CSHwang