THUWC2018滚粗记

Day 0

这次THUWC有Pretest简直很良心啊……但是听说隔壁PKU直接IOI赛制,并且可以实时看榜?想想都觉得恐怖……

考前刷了一点数据结构题,发现自己的数据结构简直一无所知……匆忙背了一下vim配置,然后就睡了。

Day 0.5

上午报道之后,开始试机。试机题是Codeplus11月的三道月赛题,不太想写……于是就随便码了一下T1,T2乱写了一下就走了。但是写的时候遇到了一个问题,那就是我的脚总是会不自觉地踢到插座……然后电脑就关机了……还好关机并不会把所有东西清掉……但是如果没保存,那就gg了……(flag)

Day 1

心路历程

下午的考试时间略有些不适应,不过影响不大。
好的崩盘从现在开始:
T1似乎是个签到题?开始想简单了,就随便贪心了一发,写到一半才发现好像不对,没有考虑两个数组的负数个数差得很多的情况……于是匆忙改改改,改得自己觉得差不多了,就急忙交了一发。结果wa了……Pretest只过了三个点……并且还是三个特殊数据的分数,连$n,m \leqslant 4$的分都是wa的。没过多久才发现,自己的写法似乎有些问题……于是又是一阵改改改,又交一发,结果还是wa了……而且Pretest变成只过了一个点……此后的一个小时里头,我的Pretest得分就一直在三个点和一个点之间徘徊。最后实在没办法了,就写了一个只能跑$4$的暴力拍了一下,瞬间拍出错……调了一阵之后,终于把T1给过了……然而此时已经过去了两个多小时……
T2看上去会$O(n^2)$,但是暴力只有10分,于是先跳过了,去看T3。
T3研究了一会性质之后,然后一阵激动:这……后缀数组套个二分不就没了?然后急匆匆的开始写,觉得今天有戏啊……(flag$\times$2)。然而写到一半,发现后缀数组不是那么记得了= =,又回忆了好一阵后缀数组。在整个写T3的过程中,连续两次一脚踢到插座……没过多久就把我认为正确的T3写完了。然而……交上去之后,又wa了,而且wa得一个点也不剩……想了一会……才发现我的算法是个错的,心里一阵凉。稍微冷静下来之后,我发现,我的算法要改成$50$pts非常轻松,于是马上去改。可惜,自从发现我的T3的想法是错的之后,我的心态开始有点崩,$50$pts往死里调也调不出来。最后想了想,我直接写暴力的$15$pts吧。结果暴力也是各种wa,然后就这样……一直wa到了考试结束……
Day1考试结束的那一刻,其实我已经知道这次THUWC肯定没戏了。作为一名本身没什么实力的选手,想要在THUWC上签掉,大概就是要保住所有分吧。
出考场问其他同学,发现大家都至少有150+。哎凉了凉了。

题目回顾

snack 零食

Pretest: 100
正解好像和我写的是一样的,是一种有点偏细节的贪心。然而我的同学们都是一种非常好的方法:考虑枚举其中一种零食被分为了$n$区间,然后另一种零食只可能被分为$n-1,n,n+1$个区间,然后计算一下答案就可以了。

city 城市规划

Pretest: 0
正解是一个线段树合并,然而我连线段树合并都不会……听说$O(n^2)$再把没用的状态去掉,就能拿到$40$~$50$pts……

字胡串

Pretest: 0
正解是后缀自动机。然而我还是不会……

Day 2

心路历程

想着Day1早已完炸,似乎心态也放开了?
Day2的考试时间一推再推,一直推迟到了2:20才开始,然而我们1:50就进了系统,打完配置大概2:05,我干等着没事干,就打了个FFT的模板,结果,想不到还真就是T2的正解……FFT倒是罕见地手打一遍过了,感觉今天状态不错?
拿到题目,看了看T1觉得似乎不太可做……T2又是个比较明显的DP,于是我就先开了T2。T2想了很久之后,转化为了一个我很熟悉的问题:在$n$维空间上,需要从起点走向终点,每次可以在某一维上走一步,有一些点是不能走的,问从起点走向终点的方案数。然后我就想起了猫曾经出过的一道题:CF559C。于是写了个DP+容斥,但是并没有预处理,交了一发,有$40$pts,但是其中有个点跑了4925ms,然而时限是5000ms,心里很虚,拿了个极限数据,发现要5300ms左右。卡了很久还是没什么效果,于是就弃掉了。此时大概过了1.5h。思考了20min正解,但是觉得并不可做,于是暂时放下了T2。
T1和T3之间选择了一下。T1我不太会,T3的材料实在太多了,还有什么中英文的材料,根本不想看。于是先看了T1。
T1的贪心策略想了很久,一直没有一个很靠谱的,最后想了想,T3的分应该还容易搞?于是又暂时弃掉了T1,去看T3。
T3我本来是不打算认真去写的,于是交了个随机数上去……结果爆0了。后来发现我的随机数不合法(???)然后交了个正确的随机数,$20$pts,似乎很可观啊。猛然间觉得T3是挺好搞分的,于是开始看他给的材料。看完一部分材料,开始写三个算法中最好写的FAST。然而效果非常不理想,得分竟然和随机数是一样的= =。此时时间只剩下了两个小时左右。于是我开始各种玄学调参,但是调了很久,Pretest也只有$23$pts,效果很不好。他给的那些工具,我很多都不太会用,调起来非常不方便。剩下的时间也不太多了,于是又暂时把T3给放下来了,去写T1。
T1的贪心策略仍然没有想到一个靠谱的,思考了许久之后,敲了一个$5$pts的暴力上去,之后就在想$15$分,结果直到最后,连$15$分的都不知道怎么写。
考试结束后问了一圈,T1小学生直接A掉了(orz),T2我好像搞到了为数不多的$40$。勇石博士T3搞了$59$pts,而且他写的也是FAST(???)后来他跟我说,是不是你的$w$和$h$读反了,我仔细一想,好像还蛮符合他说的那些问题……我……真不知道说些什么……如果T3也搞了个五六十分,也许……可能就Day2翻盘了?

题目回顾

sunrise 明天的太阳照样会升起

Pretest: 5
此题的正解是一个偏细节的倍增。先考虑一下$15$分的$O(nm)$的贪心,贪心策略大概是这样:

  • 在所有在这个点能加满油能走到的地方中,寻找第一个油价比出发的地点低的点,如果存在这样一个点,那么就直接把油刚好加到那个城市即可。
  • 如果不存在这样一个点,那么就在这个点把油加满,并且开到一个能开到的油价最低的点。

然后注意到对于每个点,它都只有一条唯一的出边,所以就可以倍增了。倍增的时候要处理一些起点和终点的细节就可以了。

sequence 七彩序列

Pretest: 40
这道题的正解是个NTT……然而窝太菜了,根本没听懂……

cd 角点检测

Pretest: 23
乱搞题,正解不存在的……听说std长达40k(???)不是,我真的有点忍不住了……

Day $\infty$

这次THUWC,其实真的浪费了太多的机会……Day1T2,Day1T3,Day2T3的失分都真的很可惜……听说和面试分数线就差一个暴力,想想也是觉得很可惜。但是,毕竟自己的考试策略也有一定的问题,在想到Day1T3的一个算法之后,我并没有直接去证明算法的正确性,而是急匆匆地开始码,这个选择无论是从哪个角度来讲,都是不太理智的。而最后直接连暴力都调不出来,应该来讲心态上的调整做得不够到位。Day2的话个人觉得发挥还行,没有太受到Day1的影响(你Day1都滚粗了还有什么影响……)但是这个创新题搞得并不好,还是不太敢去花大量的时间去搞一个不知道自己能搞多少分的题。不过话说回来,自己这次的收获还是很多的,也算是认识到了自己还是比较菜吧……
最后,强势围观勇石博士直接无条件(省队)一本!orzorzorz
雅礼整体签得略惨,6个进面试只有3个拿了约,不过罗大神最后也拿约啦~
完结撒花~HNOI继续奋斗吧~相信自己吧!