HBOI2018游记

Posted by Panda2134's Blog on April 10, 2018

挺难过的……

本来以为网络流学的很好,结果d2t1写了假的动态加边最大流,直接自爆

Day -1

晚上熬夜打模板……

Day 0

动车上想到还没写过CRT,看了半天chrt的讲解,然后赶快把《训练指南》上面的抄了一遍。

然后开始颓Minecraft

由于前几天答应了教练给高一去划水的同学讲骗分,一到宾馆就开始做slide,连模板都没看。

做了一会slide,就去试机。今年省选又是在华科一楼机房……(去年小凯的疑惑就是在这里爆炸的),debuff++

和好久没见的anoxiacxy聊了一会,问了半天nonamenotitle怎么还没来,最后发现她坐我们前面,蜜汁尴尬。

WGSZ的xlj好强啊,我高一这个时候还在学文化课,他试机随手敲后缀数组……我敲了半天,还差点敲错了……

最后不知道干啥就拿学长的surface颓MC(rp–),发现KS君在后排某个机,过去聊了一会。

晚上胡吹完如何应用初中数学骗HNOI2017礼物就睡觉了。

Day 1

差点原地爆炸。

进场发现anoxiacxy坐我右边,顿感紧张。

开解压包后看了一会T1:woc怎么是博弈啊,是不是要弃疗啊

一看数据范围 $n, m \le 10$ ,好像Minimax搜索可做?这样的话来一发AlphaBeta剪枝怕不是可以A?但是好像我以前只跑过 $n, m \le 6$ 的博弈搜索啊……不管了先写再说。

连写完带拍完大概一个小时不到,然后发现 $10 \times 3$ 格子跑不出来, $6 \times 6$ 顶着时限跑出来。

慌了,不知道怎么办,最后先把Minimax搜索丢那儿。

看T3,感觉不可做,打暴力完事。

又看T2,$d_i \ge d_{\left\lfloor\frac{i}{k}\right\rfloor}$ 这个式子好像很熟悉啊……堆?

等等,要求字典序最小,堆怎么实现啊……

打了30pts暴力之后就开始各种脑补如何贪心,贪心了2个多小时发现是错的。这时候已经11:30了。

最后的时间就在检查T1,看文件名中度过。

本来很稳,弱省这个成绩应该还行。

结果最后 5min 我把题意看错了!我看成了左边和上面棋子,把“都”看漏了!

疯狂改possible判断函数,发现样例输出-inf

又改,发现样例输出 inf

又改发现样例输出3.答案是2.

这时候已经到了最后的一分钟。我已经没有什么知觉了(后来cxy告诉我我在考场上喊“全完了”什么的)

最后二十几秒钟我意识到可能是新题意有问题。怎么办怎么办怎么办?已经改错了!改回去来不及了!

Ctrl-Z!

我按住Ctrl-Z,看屏幕上面错误的修改一闪而过,直到退回到重开文件的状态。g++ -o chess chess.cpp -std=c++11 -DDEBUG 编译。编译成功。./chess < chess.in 。没有时间测试小样例了。 chess.in是调试的时候做的大样例。输出-106579,是那个样例在改之前的结果。

比赛结束。工作人员要我立刻停止作答,我跟他解释说我在删文件。

删完文件我就走了。没看一眼代码。

出场后就跟cxy说我退役了。和WGSZ信息组的同学出去吃了个饭。纠结了半天才确定是我最后几分钟看错了题意。

令人欣慰的是,我的Ctrl-Z没有挂。这个题70.

总分115。听说武汉二中广雅中学一个初三的同学当场A掉了,用的轮廓线DP,day1 rk2。好强啊……我真的好弱啊……现在想想,就算不会轮廓线DP,要是当时拿出一些瞎搞T2的时间想想怎么优化暴力也能过……毕竟棋子只会越来越多,所以肯定是个DAG……unordered_map存状态后记忆化搞就行……

虽然错误挽回了,但是对我心态还是造成了不少影响。

下午想颓废,发现宾馆网不好,想写题,发现打不开bzoj和洛谷。只好用手机热点。

写了个费用流题,发现莫名TLE(flag)。拿原始对偶都过不去。和KS一起看了一个最大流题,居然没想到二分(flag)。

滚去睡觉。

Day 2

开场网络流。

看懂题意就用了40min,然后随便yy了一个可行的建模。发现和标题的“匹配”呼应,嗯,有意思……

排名靠前的优先?动态加边就好了。上升多少排名?二分一下。想着想着就开始码。没想到给自己挖了个大坑。

首先,我的动态加边不是动态地addedge,而是先把每层边拆出一个点,再给对应点打删除标记……

然后,我每次二分后直接清空了所有的流量……

码完发现过不了大样例,第二行全是0.

于是先弃疗看T2,发现10分都要树上DP/点分治,弃疗。

又看T3,好像后缀数组+莫队可以做,但是计数不是很熟练,好像全是0的公式都不会推,怎么办?

先回去调T1。调了半天发现手残把state[u] > hope[u] 写成了 state[u] > hope[i],改过来之后发现了更大的问题。$n=50$ 单组数据都跑了半秒,怎么办?难道是网络流复杂度太高?

我当时根本没想到会是动态加边的问题。

最后交卷也没想出来。成绩出来之后发现这个题的假网络流连暴力分都不如,只有30. 兄弟学校某同学爆搜加剪枝,60+.

于是 day2 最终 45 分滚粗。


cxy、wqs和barrin大爷切了这个题(虽然被卡常了)。Fire_storm和我省选一个分,但是NOIP比我多混了一个点。他们进了A队。

我的假动态加边最大流让我掉进B队。

总结

很难过吧。。。考得完爆了。。。

。。。。。。其实也没什么可以说的。。。都是蒟蒻的借口罢了。。。

。。。自己果然还只是半吊子水平呢。。。。

–WJMZBMR

然而clj在day2 ak了。我原地爆炸。

我,才是真正的“半吊子水平”。

写了那么多网络流的题,多是建出模型就完事,如果TLE就开O2. 想不到我最后挂在网络流的实现上。

感觉自己学过斜率优化DP,d2t2却根本没想到是DP,更别想斜率优化。

说来学过爆搜,学过记忆化,学过哈希表。拿到了d1t1却只会套高级算法拿部分分。

更别说还有那么多不会的东西。


去年暑假,我看着chrt退役写下的OI故事流泪许久;6个月后的今天,我才发现不久后那个退役的就会是我。

当初停课,是为了追梦,却不曾料到,我停课后的进度并不如我想象的多。想想自一月份停课到现在,在机房的效率又有多高呢?享受着一个人一个机房的待遇,我却感觉自己一天比一天颓废了。也许可以说,是孤独,让我有时候甚至丧失了对算法竞赛的热情。我还记得刚开始做网络流相关省选题那几天。有一天下着大雪,班上的同学都在后山玩雪。我在机房里面望着看不懂的题解,不知如何下手。那种感觉真的很绝望。有时候我很羡慕上一届我校的学长学姐们。至少有人一起努力,而不至于怠惰,更不至于被当做异类。想想现在的我,每天有多少时间花费在做题和写题解上,有多少时间用来学新算法、讨论题目;又有多少时间拿来水群,有多少时间在闲逛知乎和Blog中白白浪费了呢?我常常跟学弟学妹说少颓废多刷题,我现在真的百分之百地做到了吗?

再过几天之后就是HNOI了。我已经跟雅礼的教练商量好了,等HNOI完了之后,我回来收拾一下东西,就到雅礼去学。我相信,真正系统而刻苦的学习,才能带来令人满意的结果。而这样的目标,对我而言,在一个人在学校里独自学这样的情况下,是不可能达到的。而且,对于NOI的考点,我相信那边的训练比我自己找题目做要更精准,更有效。

高一的一年文化课让我知道了一点:我不是一个吃不了苦的人。刚入校的时候,我完全不会物理,物理考试一般最后一题完全不会做。没有办法,我就不断整理各种模型,每天去问老师、同学问题。努力了许久,我的物理水平终于提高到了很不错的程度,就算NOIP前停课将近一个月,回去七校联考物理也是全校第二(当然,现在看来肯定有运气成分)。同样地,在雅礼,无论是多大的煎熬和困难,无论是多么复杂的算法和数据结构,我都会忍受过去,努力学习。因为这一切都是为了心中的梦想。如果就系统的OI学习来看,我起步的非常晚。但是我相信,三个半月的时间,实现质的飞跃,是个可能的事情。

如果有缘的话,各位NOI再会,那时,我们将会一决高下。

最后还是那句话:

但行好事,莫问前程。

谨以这句与所有同学共勉。不管你是省选之后宣告退役,还是继续在OI的路上走下去,我都希望你能“活出让自己和自己爱的人高兴的样子”,拥抱自己的成功。

panda_2134

2018/4/10 晚