NOI2019网络同步赛游记

我还是太菜了。

DAY1

一上来看到第一题,就直接看成了序列。然后开始肝,当时的想法是要按照时间顺序加边,然后对于每个点维护以时间为下标的凸包搞斜率优化就好了。但是当时不知道为什么,想法是按照p排序之后维护q下标的凸包,于是就写了个set去维护支持插入的凸包。

2h的时候发现了过不去样例3,这时候才发现1,2样例是和第二个subtask一样是具有特殊性质x<y的。瞬间意识到,这是

于是我的问题就变成了“在拓扑序上用多个平衡树去维护多个凸包顺便斜率优化”,又码了1h后自闭了。

最后随手上个暴力,O(n^2)暴力竟然瞬间跑出来了10w的样例。

然后最后1h,我还是抱着“大家都200pts我不切一题怎么活”的心态,没有去打48pts两题暴力,而是想到了一个没法证明正确性的T3贪心。

这个贪心很不好维护,我只手玩了几个小的样例就开始码了,要用四个类型不同的堆维护,最后还没有码出来,于是就只有T1的暴力分了。

然后告诉我T1切了???仔细想一下好像也是可能的,因为他卡一种暴力就会放过另一种暴力,最后估计干脆数据随机了,而我的算法在随机下非常优秀。

DAY2

T1感觉就是个板子题啊。很快就想了一个二维线段树优化连边的O(nlog^3n)算法,然后打了好久才发现:"此题空间限制128M。",瞬间心态爆炸,都这个年代了怎么还有卡空间的出题人啊啊啊。冷静了一会,想出了O(n\sqrt{nlogn}logn)的分块算法,发现可以和暴力获得一样的好成绩(后来听说这是88pts那一档部分分?)。果断暴力打完走人。

T2感觉O(n^3)DP不难,多出来的10pts也就是矩阵快速幂优化一下。但是很难调试,因为取模和一些细节调了1h才搞出来。

只有1h写交互题了,20min才明白了题目意思并知道怎么玩这个grader,最后很快的敲完了暴力的20pts,发现二分图的16pts只要二进制分组一下就可以解决,赶紧码码码,好在最后还是码完了。

那么期望得分就是72pts+30pts+36pts=138pts了。

总结:

这两天的考试,我都出现了想到了正解但是写不出的情况,这是很不好的。尽管第一天我的想法有些麻烦,要打多个平衡树维护凸包,但是假设如果我的码力足够,是可以直接打正解而不会花很多时间还写不出来而被迫暴力,第二天的T1我是有KD-Tree的想法,但是我不知道怎么用这东西优化连边就弃了。然后就是我第一天在最后时刻出现了不打暴力直接拼正解的赌博心态,其实老老实实打暴力可以稳48pts,但是我总觉得“别人会很强我一定要切题”,最后才发现别人往往没那么强,而我的赌博往往搞得还不如暴力选手。

最后DAY2线段树优化连边只开了4倍空间,于是挂了12pts,最后是

100pts+0pts+0pts+60pts+30pts+36pts=226pts

铜牌滚粗了。

0%