[NOIP 2017]滚粗记

[文章目录]

时间:2017-11-11(话说光棍节noip诶。)

Day 0

早早就去睡觉了,带来的结果是晚上入睡很难,脑子里总是蹦出来什么扩展gcd之类的不太熟悉的知识点。。。

Day 1

6:40 出发,前往吉大南校考试,路上很顺畅,并没有出现什么堵车之类的东西。到的时候发现还是有很多人已经到了。

7:30 开始抽签。 “离谱————!离谱到了吗?”感觉全场只有我反应过来那个老哥好像念错了(那个字是‘晋’啊!老哥你你该戴眼镜了。。。),抽完签,二考场38号。

8:30 进入考场,等待下发解压密码的我发现其他人好像都可以看题了,原来解压包没有密码。
开始做题:

T1,好像是一道脑洞题?扩展gcd好像解不了。推了半面草纸式子发现没有什么太大的进展。继续往下看题。(讲真有点慌了。)

T2,这不是个大模拟吗?一会再码,不着急。

T3,分层图DP???-1的话判断一下是不是在1~n的一条可行路上存在0边构成的环就好了啊。感觉好像可写。

稳定了一下心情,重新推T1。
诶???可以用一些小聪明啊。。。假设x为答案,那么x+a一定可达,并且x+a=k1*b (k1< a) x+b=k2*a (k2< b) 。得到方程:(k1+1)*b=(k2+1)*a,a,b互质,只有一个解啊,不就是a*b-a-b么。。。检查了两个样例,发现没问题,又重新整理了一下思路,感觉稳了。(话说为什么不把最后的40%搞成多组数据啊。)此时考试时间已经过去了1h。

T2,码码码码。调大样例,找出了几处BUG。调过了就不管了。

看了一眼T3。纠结了一下拍T1还是写T3。最后还是拍了T1,过了。

看了下时间,还剩1h20min,上了一下厕所。

下面是噩梦的开始(我为什么开始慌啊。):

T3,经过简单的思考后就开始码了(无限自责中。。。我好菜啊啊啊啊啊啊!!!),堆优化dij求最短路,然后spfa分层图DP(由于各种注意常数导致码了很长时间)。小样例没过,怎么调都调不出来了(重复更新)。看了一下时间(电脑上的),还剩30min。
果断放弃30分,直接分层图。改为枚举层,再枚举点更新。接着各种调,总感觉枚举点的顺序不对,改成了dij的最短路优化顺序。这应该对了啊。发现还是调不过。没事,我还有10min,一定能调出来的。

诶,怎么收卷了。瞬间出冷汗。电脑时间还有10min啊。啊啊啊啊啊啊!我的电脑的时间慢了10min!!!!
【后来发现,记录最短路顺序的计数器多组数据TMD没有清0,并且有些点可能都没有在这个出堆序中出现(从1节点不可达),dp的时候循环应该到计数器的位置,而不是n(可能有上一组的数据残留,影响结果)。哭死 QwQ 呜呜呜】

那一瞬间,怎么形容呢???感觉连破口大骂的愤怒都没有了,脑子一片空白,机械地离开考场,路过一些见过的面孔,耳朵里回响着讨论题解的一些声音,脑子却锈住了,一点都思考不了。
到楼下看到吉大机竞的战友们,好像都不错。
见到东东爸:“你考咋样啊?”“不咋样。”(突然感觉自己说话态度不对,然后脑子开始分析了起来)“前两题好像没有问题,T3没调出来,期望0分。总分期望200-”。
记得东东爸最后告诫我“千万不能因为今天的失误影响明天的考试”。(好像除了这种话也不能说什么了吧,考试的话,除了靠自己,别的,白扯)

和GXZlegend去吃了熟悉的旋转小火锅,强迫自己觉得在吃一顿大餐,实际上感觉从吃开始到最后都没有食欲,吃完,打车回家。
回到家之后,父母问道:“考得怎么样啊?”,“挺好的啊,感觉还不错。”,装出一副没什么事的样子,吃水果,和父母聊一会天,之后回到房间里睡觉,一觉睡到了晚上。
睡死过后终于活了过来,吃过晚饭。开始分析:“今天最高200,500+无望,明天得......”

老子可是lijinnn啊,怎么可能浑浑噩噩惨败啊?

调整心态2h+,终于有信心第二天好好考了,睡觉。
[day1分数:220]

Day 2

和第一天一样时间到,结果却没有几个人到,和CQzhangyu聊了第一天的考试。听说好像有很多人的表都慢。
进入考场,直接开始答题
昨天下午考普及用我电脑???昨天代码没删,删对拍代码???

T1,一眼并查集,判球相交开根精度好像不行,平方好像爆longlong(虽然并不是),开了longdouble。

T2,这不是状压?当前最深层数和可及情况为状态,预处理点到状态中任一点路径的最短长度,枚举子集算代价复杂度O(n^2*3^n)。
好像子集代价可以递推?研究了一下,真的可以。大概看了一眼T3,之后开始码T2。
调过了大样例之后巨开心(Jesus! paralysed and relieved)。

还剩1h40min,看了机房前面的表,确定真的是1h40min。

看T3,好像O(q^2)+平衡树可以80分。不会O(q^2)可以60。
想了一会O(q^2),想不出来。打了30分裸暴力。剩下30分在犹豫写splay还是非旋转treap的过程中,选择了熟悉的splay。手玩了几组样例,过了,之后肉眼调试。

剩20min,各种检查。(突然反应过来好像昨天的失利并没有对今天产生影响,感觉自己棒棒的。)
不过话说我咋没检查出来T3需要开long long啊,好吧,我菜。

考完,期望分数260。[实际分数250]
成功讹到大师的顺风车,开心。
得知需要开long long后,总期望得分:450
[day2分数:250]

发分了

Day1 T3由于数据水得到了20分,感谢出题人。坐标弱省吉林,总分470。
宋爷和CQzhangyu由于DayT3大数据结构题不约而同地没开longlong,白丢50。
EdwardFrog,CQzhangyu,GXZlegend Day1 T3都被卡常了,70分。不过卡常什么的好像和我没关系啊(无力)。

mk703、Ciel退役了
Superbia_zyb说文化课学好了好像还是会回来的。
机房现在高二只剩下5人了。

总之还是可以的吧。坎坎坷坷什么的,如果没有的话,岂不是很无聊啊。

4 条评论

发表评论

邮箱地址不会被公开。 必填项已用*标注