NOIp 2018 复赛总结

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

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

<!-- more -->

得分分布

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

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

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

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

DAY1 T1 修路

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

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

之所以没有彻底模拟每一天填的状况,是因为好像这是一道小学奥数题(我管这个叫奥数优化

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