NOIp 2018 复赛总结

在这个星期日，经历了长达两天的 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 填数游戏

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

DAY2 T3 保卫王国

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