NOIp 2018 复赛总结

Thu Nov 15 2018 19:49:18 GMT+0000

在这个星期日,经历了长达两天的 NOIp 复试,是时候做个总结了( ;∀;) ( tcl )( 好像 www.noi.cn 出了点问题)

只有第一天前两道题能确切的拿到分啊 / 第二天的题完全没有希望::=

而且考完 NOIp 就期中考试真的没关系?

总感觉自己好弱,( dalao 们求罩了)

现在还是正经点说一下我做出来的部分qwq

DAY1 T1 修路

我的思路和 luogu 的题解有些不同。

  • 我定义了区间数组 int arr[100002];
  • 然后用这个数组储存了整条路(区间)。
  • 写一个函数 check() 判断 arr[1]~arr[n] 是否全为零(已填平)。
  • 写一个函数 fill()arr[1] 开始向后寻找连续的不为零的区段,并找出最浅的地方,并把每个地方的深度修改为 当前深度 - 最浅深度 (把该地向上填) 并使答案增加最浅的深度(一天填一层所以 “天数 = 深度” )
  • 因为保证初始区间全不为零,所以使用 do-while :
    do{
    fill();
    }while(check());
    

并没有彻底模拟每一天填的状况。

这个算法的算法复杂度在 O(n^2) 到 O(n).
具体取决于输入数据,如果是金字塔形的就会被逼到 O(n^2) 如果是崎岖不平的而差别不太大的数据 复杂度就接近 O(n)

DAY1 T2 货币系统

一开始自己感觉没有思路,不过回想了一下学过的知识发现这道题就是一个很常规的筛法,如果用 dfs 的话第二个样例就吃不消了, 尝试写了一下 dp 还是太菜就放弃了 ,最后用 dfs 只拿了60分。

DAY1 T3 赛道修建

这道题有点思路,想到了二分,但是不会写啊,时间也很紧,然后就丢了(哭)。

DAY2 T1 旅行

这道题看了一会儿就知道要干什么了,匆匆忙忙开始写。结果写完一后只过了一个样例,另一个样例完全不符,十分头疼。半个小时也没想出来是为什么。

考完后来去看别人题解,原来是要枚举边,而我枚举的是点。

估计是出题人好心,测试数据中有两个是枚举点也能过得,最后拿了 20 分。

DAY2 T2 填数游戏

这道题一开始拿来还是很自信的,毕竟是规律题,做不出来还可以猜,结果我琢磨了半个小时也没琢磨明白,去猜的过程中手算也算不了几个数据,只能发现两条边上的结果是 2n ,就只写了这么多,最后拿了 15 分虽然有些不甘心,但是总比扔掉要强。

DAY2 T3 保卫王国

这道题看完题我觉得是要用 dp 就写,接着发现是动态 dp 就瞬间放弃,我 dp 本来就不熟练,加点东西就更废了,时间也不够了,这道题也只好扔掉了。

Made with ♥️ by npofsi. Powered by Hexo. Deployed by Github.

Website since 2017. Content licensed CC BY 3.0.