NOI2019网络同步赛总结

先说说分数:\(100+20+0+100+0+0=220\)
我果然还是个大蒟蒻……


Day1

比赛之前还在回顾着《灵笼》,时间一到就立刻进入比赛。
快速地浏览了一遍题目,然后开始刚T1。
T1还是很简单的。首先,是个人都会想到最短路。然后我想到了分层的最短路,然后连分层的最短路都不用,直接变成了一个DP。然后这个DP可以斜率优化。这本该是一道水题,但是我打和调了三个小时……终于过了大样例。
看着T2觉得是一道神仙题,所以去看T3。T3一看就认定为贪心,所以开始乱搞。
后面几乎一直在刚T3,想了多种贪心方式,然后小样例都没过……
(为什么我比赛时没有想到过费用流,这能水不少分啊……)
除了在最后一小时的时候停下来打T2的纯暴力,自信\(20\)分有了。
然后整场比赛就没了。


Day2

还是快速浏览了一遍题目。
T3是交互题?这是什么东西?
因为完全不知道交互题是什么东西,所以也搞不懂它到底让我们做什么。
于是T3果断弃疗。
然后从T1开始想:
这不就是一道裸题吗?直接二维线段树套\(Dijsktra\)不就好了?
然而我还没有打过二维线段树,不敢冒这个险,于是想偷懒打\(KD-Tree\)。
自然要习惯性地计算一下时间复杂度,发现,诶,这题\(\sqrt n\leq \log_2^2n\)啊!
难道是专门为\(KD-tree\)出的?(后来才发现这题似乎会卡裸的二维线段树的空间,但用\(KD-tree\)的时候几乎是不用担心空间的)
我很开心,于是开开心心地打完了T1。
然而细节很多,于是我调到只剩一个小时……
开始刚T2,感觉上可以拿\(40\)分,然后打了个DP。
然而样例挂掉了……比赛结束都没有调出来。


总结

首先,感觉上NOI的T1都是能切的,所以这块肥肉一定要抢到。
后面的题目也会有多多少少的部分分。
然后就是要加强代码实现能力,不能调这么久,浪费时间。
还有,要试着接触一下非传统的题目类型……
最后是多动脑子……

上一篇:kd树 寻找k近邻算法 python实现


下一篇:「LOJ3159 NOI2019 弹跳」 - KD-Tree + 最短路