4
20
2016
0

HNOI2016

膜拜一下我校的三位队爷,%hcy,%wdz,%wl,以及差点进队的zzd。

Day1

一进考场,习惯性的打头文件的模板,突然发现为什么emacs的风格这么像我平时用的。然后打开.emacs文件一看,几乎就是我平时用的的缩减版,什么时候HNOI都自带emacs配置了。不知道以后的会不会也有。

打开题目,花了20分钟把题目都看了一遍,发现第一题40分算法很好写,多分析一下应该可以多20分,第二题似乎很可做,并且脑中有了一个大致的想法,第三题只会写30分暴力。

忽然想起向总在考前说过的话,如果发现一道题可以做出来,一定要把其他题的暴力写出了。然后就开始写T1的40分和T3的30分,大概花了1个小时。

写完暴力之后就开始钻T2了,思考了一下最初的想法,感觉很靠谱。因为样例太大手算麻烦而且感觉方法很正确,便没有手算样例。用了15分钟飞速地码了出来,一测样例,WA。一开始以为是我写错了,调试调到一半突然发现算法是错了。哎,白浪费了15分钟。

又想了10多分钟,想出一个$O(nlog^3n)$的cdq分治+树链剖分的算法,感觉会被卡常数,便迟迟没有去写,又分析了10多分钟,并没有想出更好的算法,只能写那个算法了。用了大概40分钟,终于写了出来并且调对了,写了个对拍,拍了一下并没有拍出错。测一下极限数据,发现要跑4s,优化了下常数,比如:将常调用的短函数改成宏定义,线段树改成zkw线段树,终于把时间优化到了1s。干完这些后就已经11:30了。

接着又开始分析T1的20分部分分,写了大概30分钟,又对拍了一下,发现没有问题。又想了会正解,发现似乎可以分块,然而只有30分钟了,肯定写不完了。

然后分析T3,突然发现60分算法可以做,便开始飞速码。码到一半,突然发现复杂度有些问题,想了想改进后,突然发现,没时间了。

第一天,就这样结束了。虽然考试中间出现了不少问题,比如:没有完全想清就去写代码,结果白白浪费时间,但是结果也还不错,190分,和预计的没有区别。

Day2

看完题目之后,发现T2根本不可做,便把它扔到了一边。

开始考虑T3,发现分块可以做,便写了起来。写完拍对了之后大概是9:30,测了一发极限数据发现根本跑不出来,只能优化算法了。想了一会发现有大量地方可以优化。优化了一个多小时,终于把算法复杂度和常数压了下来。

写完T3后,开始写T1,写了两个非完美算法,一个复杂度是$O(n^2)$,另一个的复杂度是$O(nq)$,把两个算法对拍了,发现并没有问题就没管了。

搞完T1的部分分后只能来思考T2了,突然发现有20分,好像是可以扣出每一个域之后直接暴力判断,然而异常难写。写写调调用了一个半小时,终于过了样例,又手测了几组数据,发现没有问题便没有管了。

之后又开始思考T1,发现那个$O(nq)$的算法可以优化一下变成$O(n*树高)$,如果有数据点不强的话还是能多拿一些分的。

第二天,就这样结束了。最后的结果是T1真的跑过了,然而T2一分都没有,T3被卡常了20分。

总体感觉

就题目而言,感觉今年考察的知识点相当少,6个题中有5个题是数据结构或分块,剩下的那个又是个平面图码农题,不知道是不是出题人没有商量好的原因。而且有一种分块、莫队可以打天下的感觉。

就我自己而言,虽然这次以#2进了省队,但是在考试中,还是有不少错误出现,比较严重一点的就是D1T2没有想清就去写,还有就是D2T2的考场写了半天结果一分都没有,这两个问题都浪费了不少的时间。这也反映了我对于问题的分析并没有特别详细,这个缺点一定要在以后改正过来。

题解

话说,这个坑好像坑了好久的样子。

Category: 考试 | Tags: HNOI2016 | Read Count: 1109
blog comments powered by Disqus

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com