NOIP2016提高组比赛总结

时间:2021-04-01 19:07:57

首先是各题我的思路

第一题:玩具谜题

水题,解法就不说了。

第二题:天天爱跑步

以为是树形DP,正解想了半天,然后无奈骗分,按照题目数据分段打表,居然写丑了。

第三题:换教室

我直接选择骗分,先用floyd求出两点之间最短路,然后DFS枚举选那个课,ans1=0,然后再DFS2枚举得到哪些科目可以申请成功,DFS2同时算出几率,最后算出这几个教室之间的总距离,ans1+=几率乘上距离,最后DFS2完了就ans=max(ans,ans1);复杂度O(2^2n*n);要注意可以有重边,印象极深,因为自己被坑了。

第四题:组合数问题

由于作死地先做第六题,所以没时间想正解,只好开个longlong边乘边除,n方算法,要爆longlong所以只能过一部分数据。

第五题:蚯蚓

感觉是线段树,优先队列优化也可以,可惜......你为什么要做第六题,但没留时间写,所以写了个n方模拟骗分,连优先队列也没时间写了。最后发现题解是O(n)写法……

第六题:愤怒的小鸟

这题做了2个多小时,我也愤怒了。
这题有毒,本来可以DFS,O(n!*n*t)复杂度很快骗分,但是样例老是过不了,因为卡精度。骗分很简单,只要DFS枚举一下当前要一下清除的两个小鸟,然后再处理一下一下可以一起清除的小鸟就可以了。注意要特判一下只清除这一只小鸟的情况。

最后是对考试状态的总结

炸得不能再炸了。
唉……
唉……
Day1呢,第二题想什么正解,然后浪费超多时间,导致没时间骗分,第三题自我感觉良好,觉得能骗50+,然后考完发现————还可以有重边!
Day2呢,花半个小时看题想正解,然后果断选择先第三题骗分,想着先骗掉第三题在想12题正解,然后就炸了。
嗯,炸了,不仅第三题卡精度调了2个小时,还没过第三组样例。
最后一小时,带着塞住的心,默默写了一二题骗分,然后最后几分钟固执地想写第二题多骗一点分的优先队列,以为考试完了还有几秒来让我去掉“//”
以为…… 当屏幕上出现”考试结束“,锁了键盘鼠标时,心都碎了。
第二题第三题都没去掉“//”
这个教训可真是……
“老师,再给我两分钟,我能多拿90+!”。
然而这并没有什么用。