NOIP2018赛后总结

DavidW · 2018-11-11 18:21:53 · 个人记录

Day 0

上午收拾收拾行李，下午做学校大巴车去南京。旅馆的条件挺好的，不得不说普通标间和豪华房差别真是大啊...晚上走了来回差不多45min去1.3km外的KFC吃了晚饭，没写题，看了看书，九点半就睡觉了。

~~p.s. : 做梦梦到Day1 177分(100+70+7) 很慌~~

考场外很慌，但进考场之后就不怎么慌了，觉得精神还不错。

发题之后先看T1，乍一看好像是一道我们学校模拟赛的题啊，而且那题写爆炸了，惊恐万分，再仔细看一眼，发现哦原来只能横着减不能竖着减啊，题目难度陡然降低。

看数据范围，这70pts很好写啊，还可以对拍用，果断先码一个 O(nd) 的暴力。

后面又想了一会儿，发现不就是每次找到一个单峰的顶点加一加么，然后就写了一个差分看看对不对，过对拍之后就开始看T2。

T2看完题面，第一反应就是肯定要从这输入的数里面删数嘛，就开始看应该怎么删。看了一会儿发现是这么一个式子：a_i=\sum_{j=1}^{i-1}k_j*a_j\ \ (k≥0)

排完序后的第 i 个数如果满足这个式子，那么就可以被删掉。呦这不是exgcd么，应该 O(T\ n^2\log{n}) 过去，于是开始写，写完了发现不对啊，我没法判断每个k能不能是非负数啊，烂掉了。

一看时间发现十点钟了，很急，想来想去突然发现要把满足这个式子的 a_i 全删掉，应该可以dp做，想到dp就发现哎呀这不就是个完全背包么，五分钟拍完，大样例一测就过了，开始T3。

看完T3题面，第一反应是二分+树上差分乱搞一下（可能是前几天才做过运输计划的原因吧x）。想一想发现这不对，烂掉了。

想了很久想不出来，一看数据范围，哦呦这个骗分能搞到55pts啊，果断写了。120行代码写完已经11点了。

继续想标算，二分肯定是要用的，主要是这个判断怎么写。想来应该是个dp吧，先写了一个 f[i] 表示 i 到最下面长度最大是多少，然后发现还是不会做，弃疗，检查完其他题目差不多就要收题了。T1估分255。

下午晚上继续复习，押Day2大概会考图论&数论&dp。

今天就没怎么睡好了，早上起来非常困，试机的时候睡了一会儿，期望考试时候头不要疼。

发题，先扫一遍T1 T2 T3，一眼看过去T1看起来可做，T2是个统计的dp？T3非常的不可做，准备打暴力。

那么首先开T1，一开始没看见只能返回到第一个来的点，码了个堆+类似拓扑上去，发现样例WA了啊。仔细看题之后才看见这一条。

看数据范围 m=n/n-1 那肯定是数据分治了，树很简单，边排遍序就可以直接做了。n=m的连通图，妈耶这不是基环树么，哪个人跟我讲noip不考基环树的。。。

冥思苦想，突然发现 n≤5000 这就非常良心了，dfs一遍找到环，然后枚举环上哪条边断掉就切题了。一次过大样例，开始T2。

T2先码了一个dp上去，一跑发现3 3怎么144啊，于是就开始写暴力，写来写去发现写了一个 O(4^{nm}) 的无敌大暴力出来，但是发现5 5跑个十几秒也就出了。

为什么dp不对呢，因为路径可以交叉嘛，于是想来想去还是打表看看是不是大凯的疑惑比较好。这不打不要紧，一打吓一跳啊。

当 m≥n+2 时，有 Ans[n,m]=3Ans[n,m-1]，这下好了，65pts拿到手，开始看T3。

这时候仅仅只剩下80min了，而我T3竟然没有看出来这是没有上司的舞会，竟然首先码了一个 O(n2^n) 大暴力上去，此时仅仅只剩下50min了。

吃完一袋台式烤香肠冷静一下之后，终于发现这是没有上司的舞会了，挑战手速极限，疯狂敲键盘，一开始式子竟然都记错了，把Sigma记成了min，终于，在11:30肝完了44pts，11:40开始对拍，过了！

11:50填好程序大小记录表，总算是松了一口气，Day2估分209，所以两天合起来就是464分，期望不要写炸吧。

如果今年拿到国一了，那就可以安心AFO了。

希望这一篇总结，是我在OI上的第一篇，也是最后一篇总结吧！

今天回班上课了，发现还是编程训练比较省脑子...同时，今天JS公布了选手程序，学校测出464，洛谷测出474，还好没犯什么低级错误，那这样应该是国一非常稳了，可以安心AFO啦。