我还是太菜了。
DAY1
一上来看到第一题,就直接看成了序列。然后开始肝,当时的想法是要按照时间顺序加边,然后对于每个点维护以时间为下标的凸包搞斜率优化就好了。但是当时不知道为什么,想法是按照排序之后维护下标的凸包,于是就写了个去维护支持插入的凸包。
在的时候发现了过不去样例,这时候才发现样例是和第二个一样是具有特殊性质的。瞬间意识到,这是图。
于是我的问题就变成了“在拓扑序上用多个平衡树去维护多个凸包顺便斜率优化”,又码了后自闭了。
最后随手上个暴力,暴力竟然瞬间跑出来了的样例。
然后最后,我还是抱着“大家都我不切一题怎么活”的心态,没有去打48pts两题暴力,而是想到了一个没法证明正确性的贪心。
这个贪心很不好维护,我只手玩了几个小的样例就开始码了,要用四个类型不同的堆维护,最后还没有码出来,于是就只有的暴力分了。
然后告诉我切了???仔细想一下好像也是可能的,因为他卡一种暴力就会放过另一种暴力,最后估计干脆数据随机了,而我的算法在随机下非常优秀。
DAY2
感觉就是个板子题啊。很快就想了一个二维线段树优化连边的算法,然后打了好久才发现:"此题空间限制128M。",瞬间心态爆炸,都这个年代了怎么还有卡空间的出题人啊啊啊。冷静了一会,想出了的分块算法,发现可以和暴力获得一样的好成绩(后来听说这是那一档部分分?)。果断暴力打完走人。
感觉的不难,多出来的也就是矩阵快速幂优化一下。但是很难调试,因为取模和一些细节调了才搞出来。
只有写交互题了,才明白了题目意思并知道怎么玩这个,最后很快的敲完了暴力的,发现二分图的只要二进制分组一下就可以解决,赶紧码码码,好在最后还是码完了。
那么期望得分就是了。
总结:
这两天的考试,我都出现了想到了正解但是写不出的情况,这是很不好的。尽管第一天我的想法有些麻烦,要打多个平衡树维护凸包,但是假设如果我的码力足够,是可以直接打正解而不会花很多时间还写不出来而被迫暴力,第二天的我是有的想法,但是我不知道怎么用这东西优化连边就弃了。然后就是我第一天在最后时刻出现了不打暴力直接拼正解的赌博心态,其实老老实实打暴力可以稳,但是我总觉得“别人会很强我一定要切题”,最后才发现别人往往没那么强,而我的赌博往往搞得还不如暴力选手。
最后线段树优化连边只开了倍空间,于是挂了,最后是
铜牌滚粗了。