noip2018游记

day 0

sd的比赛地点在昌邑，考场有两个，一个是昌邑一中，另一个是某职业学校（忘记名字了）

然后我成功抽签抽到了某职业学校的考点，导致每天都得坐大巴去。

当天晚上，一开始不让外出住，后来就莫名的可以了。

试机的时候，发车延迟了，我到了大巴车的地方并且上了车，才发现上到了普及的车，结果就是延迟了试机，而且在那里等了好久。

那天晚上我写了一个spfa和堆优化的dijkstra,结果我还把对拍写坏了（反正我也没用上对拍）

day1

第一题一眼看上去，好像做过，因为我上次做都是2017年初了，根本不可能记得了。然后我读完题也基本要干什么操作，结果我不会写……然后自己乱搞了10分钟，想出来了一个线段树的奇怪的做法（day1t1怎么可能考线段树），时间复杂度是$o(nlog^2n)$，是可以过的、

第二题，我一眼看上去像是qdcy中学普及组模拟赛的第三题，然后进过我长时间的分析，发现根本不一样……我一开始想到了gcd这个奇怪的东西，因为当一个数能另一个数数，那个这个数肯定不能要，先是把数据分治了一下，把n==2||n==3的时候手写个一堆特判，而且我还成功在后来发现了我的漏洞。接下来，我就开始想，如果一个数是可以被别的数组合出来，那么这个数就肯定不要，我就写了一个暴力dfs加剪枝，就瞎写完了，时间复杂度$o(玄学)$

第三题，我先是把k==1的写完了，因为是一个树，所以找一下树的直径就好了呀，然后我就再特判一下，k==n-1的情况，这样恰好就是边权的最小值。其他的全瞎写的

结果考试的时候，那个学校还做操，放歌，导致了一些不好的事情。。

day 2

第一题，我看完题，就觉得前60分随便写,接下来我就搞后40分，我搞了很多强力的数据，能过全是环的玩意，然后我就继续写我的玄学算法，就是先从1号点出发，每次把能扩展的点都加入优先队列中，我每次找堆顶，然后判断上次到的点和这个点有没有连边，如果有连边，就直接走，如果没有的话，我们就找如果到这个点，在往回走的路上把哪些点删掉然后如果有在删去这个点后，无法再去访问，那么就放弃这个操作，改成别的（因为退回去以后是不可以再前进的），结果我写坏了，没有调出来。。时间复杂度也是$o(玄学)$的，不写玄学算法就难受。这个题我还写了2h。

第二题，我一看，啥都不会，就去做第三题了，回来以后，我就觉得我今天完了，今天极可能爆炸（好像真的是）我就看前30%的数据，发现，打表不就可以……我就先把（2,2）（3,3）的打了表，然后就开始玄学的思考，我一开始觉得是个dp的题，然后就开始想各种各样的dp，结果不会……，我最后惊奇发现了一个玄学的结论（结果错了），这个结论就是对于每一个斜线，我们就想，从右上角开始到右下角，如果出现了一次1那么后面只能全是1，如果是0那么下一位就是都可以，那么这样的序列就是这个斜线上的数的数量+1，那么这样乘起来，就是答案呀，我开心的测了一下样例，发现（2,2）是对的，然后非常开心去测另一个样例，发现错了……整个人都颓废了，然后我就开始分解质因数，看看答案有什么规律，因为左上角和右下角那两个点都是0/1都可以的，就相当于忽略这两个数以后，答案乘以四，我瞎搞了几次，有一次忘了把打表的东西删掉，以为自己对了，结果一看代码……就整个人又完了……然后我这个结论配上打表也只能过前30%的数据，暴力没大有时间写了……

第三题，看上去就是个树形dp，然后读完题，就突然发现我居然忘了树形dp怎么写了！！！啊啊啊啊，难受死我了，然后我自己现场yy了一下，也没yy出来，然后我又一次感觉到了我完了，结果出了考场我才知道这个是动态dp……根本不可能会，我前一天晚上还躺在床上看洛谷的模板，当看到动态dp是个黑题的时候，就觉得noip绝对不可能考，结果就被奶中了……

还是在放音乐！！差评！！

day2结束，noip2018比赛阶段结束

后来的某些天里都觉得自己会写挂些什么东西，内心十分难受，十分忐忑不安，而且星期三出代码的时候，我整个人都垮掉了，根本学习不进去，最后zyb巨佬还是帮我测了一下，然后把那个担子放下去了，心情有所好转。

最终noip2018的成绩为296，菜极了，noip2019加油。

czn

写于2018.11.15