坠机

· · 生活·游记

好笑吗?不如初二初三。

进考场。

先看了四个题,怎么是贪心,图论,找充要计数,二分后神秘 dp?

先秒了 T1,然后 T2 题面很长,认真读题,先想了下地铁线路是什么样的,单向的吗?于是我又去仔细看题,发现题目里表示的是一个地铁线路依次经过的是……

于是我认为依次就该是按着顺序单向走的走,按照这个题意想了半个多小时发现还是不会,感觉这个图没啥性质啊?是不是看错题了,于是我再次去题目里想要验证,两个样例都没有说明这种情况,而且题目里确实没有说地铁是双向的且那个依次一直在告诉我貌似就是单向的;于是就这样又想了半个多小时,感觉根本不能做啊,S T2 这么难吗?那有没有可能地铁就是双向的呢?这个依次实际上表示的不是单向的意思?

然后我就以地铁是双向的快速敲了一份代码,跑 Floyd 然后询问的时候暴力看走哪个站台就行了;发现直接迅速通过了大样例!!!不是,双向的话为什么要说依次啊……这个时候已经 2h 了,心态有点小炸。

赶紧去看 T3,这个时候有点慌,手摸了一下发现没啥思路,感觉直接算会算重啥的;于是也去看看 T4,先二分答案,那么每个点半径为 mid 的树上圆中都与 S 有交,然后就不太会了,感觉确实应该比 T3 难,于是回到 T3 了。

再手摸了一下,找了个看起来还行的性质,匆忙写了下 O(n^2) 暴力,可以过前三个大样例,我丢,那不是直接优化吗?写了个 O(n \log n) 发现后面大样例几乎都过了,但是等差数列那个特殊性质没过???而且很小的等差数列都会挂???

这时候特别红啊,再摸了一下瞎改改了过了这个大样例,此时只剩下半个小时,之前写题的时候想了个 T4 的 O(nk) 做法,感觉润去写,结果最后都没调过样例,应该保龄了……

T3 不知道假没假,它大样例特别水啊,希望不挂吧,大概是 100 + 100 + [56, 100] + 0。

复盘一下,这把打的主要问题是被 T2 这个位置的题卡了太久,导致心态有点崩,而且本来 T3 这种难度主要在找性质的题我也不是很擅长(要加训 CF 了),匆匆忙忙之下拼过了大样例希望不要挂吧。

然后 T4 其实也不是很难,只是看到 S 最多两个连通块没有想到断一条边后分开考虑,还是实力不太够啊……