好久没管博客了,主要原因是太懒了一直在做AtCoder以及各种NOI(P)模拟题,而Atcoder的题一般都有详细的官方题解.接下来遇到一些好题还是可以多写写博客吧.

NOIP考完了当然还是要总结一下说是总结其实是游记

Day0

据路边社消息今年联赛会比较难?

不过也许是好事这样考挂就有理由了

考前一天几乎没打模板,唯一看的模板是vimrc…讲道理不会考什么高端东西吧

可能是一直以来考前的习惯,下午看了部电影熔炉

我们一路奋战,不是为了改变世界,而是为了不让世界改变我们

Day1

Math

打开T1, 感觉打开了某NOIP模拟赛(说好的送分模拟呢).

大概花了20min推出了结论(似乎并不是那么简单),$a * b$ Problem 与 $a + b$ Problem 综合版.

由于已经(伪)证出了正确性就没写对拍了,此时已经过去30+min了.

不过感觉NOIP这样的比赛考结论题十分不合适,直接坑害了一些较高水平选手.

Complexity

原来模拟在这里,玩具谜题加强版.

不过加强了不只一点…

细节非常多,竟然打了100+行.由于不是很细心漏掉了不少细节,调了10-20min小样例又花了更多的时间调大样例…

还好样例很良心不然果断gg

写完后时间大概剩110min, 调试能力还要加强啊…

Park

题意十分简洁,与NOIP模拟赛画风相近.

题目有一定难度,大概花了40min 思考具体的实现方法和细节,最终发现记忆化搜索十分好写并且很好判断题目中无限条边的情况.

30min就写完了,竟然过了大样例?

诶,为什么这么慢.

把大样例改成三组就T了,而且大样例还没到极限.

于是先加个取模优化,再加个register,再加个getchar_unlocked. 终于能过大样例了,然而自己造的数据随便T成5s+.

改了很久并没有什么改善,算了去检查一下T2的细节吧,能不能a就靠CCF的老爷机了…

题目还算合适,但是卡常差评.

后记

似乎T3被卡常是正常现象,然后…一群人说T1是小学奥数原题

准备回去看知乎的吐槽

似乎Day1情况不错,那么下午就…

本来准备继续看电影的,结果看见deemo更新了于是点开之后跟某7级曲耗了大半个下午.

Day2

Cheese

真$\cdot$计算几何.

不过也差不多是模拟题了…结果好像要开unsigned long long?!

然而考场上并没有发现(还一本正经地算了下发现不会爆long long, 一本正经地算错了)

还好最多20pts

Treasure

看数据范围像搜索…或者状压DP?

开始想DP一直都只会$O(4^n \times n^2)$, 大概花了40min终于发现有一维状态是多余的,变成$O(3^n \times n^2)$(竟然还要枚举子集).

题目质量不错,但不得不说NOIP的DP难度又上了一个台阶.

做完T2已经只剩100min, 而且没有对拍.

Phalanx

数据结构?真$\cdot$NOIP模拟赛

似乎就是一个要求支持末端插入和中间删除以及查询第$k$个元素的数据结构.

Splay?NOIP应该不会考吧,而且我已经半年没打过了,常数看起来也十分危险.

于是想到用线段树来维护,然而由于此时只剩不到1h, 没想清楚就开始打,结果打出一个错误算法,而且由于没有及时发现错误还调试了很久.

没办法,打个30分暴力交吧.其实50-70分也挺好拿的,然而没时间写了.

后记

T1似乎很多人都没有注意到unsigned long long的问题,希望没有专门卡的数据.

T2搜索+剪枝也是可行的做法.听说大样例很水,没有对拍感觉有点虚…

T3有不少dalaoA掉,还是考场上没有想清楚导致挂掉吧

总共写的分是530,(然而去年写的分是540, 挂掉55),比去年还弱的节奏?

T1估计会挂掉20,希望剩下的不会挂.

Summary

进入正题.

一年下来对于简单的题目应该还是稳了很多,但是仍然有一些问题.比如说对于实现细节不够细致,导致了比较长的调试时间.再比如对一些次要数据范围没有特别注意.

像D1T2这样题意比较繁琐的题目,一定要看清题目中的每一句话.在彻底弄清楚题意并且有很清晰的思路后再开始码.比如D1T3正因为找到了简单的实现方式所以能很快解决,而D2T3正是因为没有想清楚所以导致挂掉.

考试需要抓紧时间,但是切不能因为时间比较紧张就乱了思路.越是到最后越需要冷静下来思考,这样才能利用好考试的每一分钟.

总的来说,这次NOIP并不算考挂,只能说在思维能力和代码能力上都还有所欠缺,还需要在大型考试中锻炼.

接下来是HNOI,可以考虑调整一下做题类型,比如多做一些近年省选中稍简单的题以及CF上比较具有OI风格的题来练手,(毕竟AtCoder在题目风格上与OI相差甚远).

HNOI2018!