NOIP2017滚粗记

​ 本来不想写,毕竟自己太弱了。但怕以后在没有机会写,未来便再没有什么回忆了。

Day0

​ 期中考……晚上补了一波模板,听说有个同学复习了高斯消元??

Day1:

​ 那道题面先看题

​ T1:这……不是原题吗?A*B-A-B啊。嗯……数据范围挺好要LL,等下再拍一下。

​ T2:这……看起来挺恶心的模拟?

​ T3:感觉是DP,咦,怎么还有0环?

​ 于是很快拍过T1,做T2,要不是T2有大样例,找出了我不下3个错误。

​ 大概还有两个半小时的样子,开始做T3。

​ 没有0的,貌似最短路再套个DP就行了。有0环?貌似SPFA判一下就可以了?

​ 心里想:NOIP应该没人卡SPFA吧

​ 大概10点半左右过了样例,然而,大样例跑了4秒。

​ 于是开始卡常数,11点左右卡到了3秒。

​ 然后听说CCF的机子跑得很快。嗯,单元运气好点——事实证明,我听说的是CF,而CCF的老年机非常慢!

​ 出考场,有人告诉我SPFA的 复杂度在判负环(或者0环)基本上每次都能到达极限。

估分:100+100+100 60 PS:删除线为出考场时的估分

实际得分:100+100+70,除了0环我竟然没被卡常数呐。

​ 晚上和SYY看电影,大概到11点左右打算睡觉,结果被子太热睡不着,起来上厕所貌似第二天了……于是Day2滚粗。

Day2

​ 早上起来头特别晕,发现捏自己的脸都不会感到痛,很想去跑几圈,但是衢州下着雨……

​ 当时希望自己RP能好,但也预感到爆炸。

​ 拿到题面。

​ T1:貌似不难,sqrtsqrt判一下再BFS一下?

​ T2:爆搜??状压??有点假

​ T3:50分貌似可以直接做,还有20分?貌似splaysplay可做,貌似可做3030分。——然而当时太naivenaive的我只是听说过有splay,BST这种东西,而真正了解一点的,也就只有set的insert的lower_bound。

​ 不过如果拿个250一等应该也稳了。

​ 于是开始刚T1,和D1T1差不多很快就做出来了,加了一个eps。当时有点怕sqrtsqrt会不会超时,但觉得NOIPNOIP不会有人卡sqrtsqrt,事实证明真的没卡,有些人有乘法来比较,据范围要unsigned long long,很多人用了long long也都过了。

T2T2先愉快地想到了分层状压,然而当时脑子有点昏,计算复杂度大概是O(4n2n)O(4^n * 2^n),当时想的大概是枚举下一层的状态,预处理出是否可行。

​ 一算,这只能过70分呀,我还是先做T3吧。

​ 于是T3写了50分做法。写完大概还有两个半小时,小样例过了,大样例一测竟然有五六处错误,这些错误还不是诸如最后一排的特殊……于是认真地调起了50分暴力。

​ 中间发现一直找不出错误,开始想T2的100分做法。

​ 然后我应该是想到了最优解一定会被算到,然而又新YY的一个错误的DP,事实证明一个错误的DP样例都过不起但是浪费了不少时间。

​ 有点痛苦,于是T2开始写O(n!)O(n!)的暴力(当时不知怎么的忘记了之前想到的状压),发现还是没写对。

​ 这时候离考试结束只有1个小时了。

​ 我悲壮地写了40分做法。然后样例自己的小数据过了。

​ 我开始悲壮地继续调T3,到考试结束还没有找出错误。

​ 返程的火车上,我回忆起T3,突然想到自己在处理最后一列的问题的时候少了一个特判,会导致这一排的前面的都有问题。然后如果数据比较大,期望还是有得分的。然后没发现我还有个一个致命的错误:爆LLLL

​ 看了zzqzzq的题解,发现我T2的状压做法距离正解就差一个预处理!

估分:100 80+40+0 30 ;PS:删除线为出考场时的估分

实际得分:100+5+35.

​ 我T2炸成5分了??我要是当时写状压呢???万一一不小心满分了呢???那也比不过WZP呀!

​ 我T3竟然有35分.

后记

​ 我当时的想法就是混个提高组一等,结果真的只混了一个提高组一等。当时以为

​ 然后遇到了各种神犇,像初三就510的王展鹏。

​ 我在想,要是我之前就学会了splay等平衡树,我是不是能多拿30分?

​ 然而发现情况比我想象的复杂,Day2我睡眠不足,神情恍惚,精神状态不对——好吧,只是我弱的一个借口。

​ 我省初三神犇太多啦……

​ 我省初一神犇太多了……

​ 我本来想,ZJOI2018也许自己会更好(去年爆蛋)。然而貌似我得AFO啦,所以记下这篇文章。

文章目录
  1. 1. Day0
  2. 2. Day1:
  3. 3. Day2
  4. 4. 后记