前言
在这里立一个可能无法实现的 flag:
把 NOIP 从古至今 (luogu 上有) 的每一年都写一篇复盘!!!
伏拉格综合征开始了
在复盘就不讲那些伤心的话了.
D1T1 铺设道路
考试时居然不知道这道题是原题...
一共有两种做法:
递推 / 贪心.
设一个数组 \(f\), 顺序遍历. 是这么更新的:
\[f[i]=f[i-1]+max(0,a[i]-a[i-1])\]
反正我没做过原题想不出来
分治.
弄一个递归的函数, 暴力统计区间最小值, 暴力区间减, 再来一个遍历找出断点, 把所有的答案加起来就完事了.
但是据说这种做法是会被卡成 \(O(n^2)\)的. 但是幸好 NOIP 的数据没卡.
不然我就省四退役了
代码:
D1T2 货币系统
最初的想法是在一个大一点的范围内看看表示的会不会一样多.
不知道为什么就发现: 只要看看能否表示出给你的所有货币.
从小到大排序, 选到能表达出所有货币为止.
表示方法有两种:
dfs 暴力搞.
暴力枚举出每一个数前面乘的数, 看看能否表达就是了.
但是这种做法因为效率不高而只能搞 80pts.
dp 背包方案.
因为任何一种货币都能选到够, 所以这不就是完全背包吗?
所以使用完全背包, 从能够表达的状态转移到另一个状态即可.
同时, 这个 dp 数组是可以循环利用的. 如果每次枚举选几种货币的话会 T 掉.
这个就是正解了.
代码:
D1T3 赛道修建
待填...
D2T1 旅行
这道题让我认识了什么叫做基环树!
这道题就是两个部分分:\(m=n-1\)或 \(m=n\).
\(m=n-1\)部分明显就是一棵树, 那需要看怎么遍历这棵树才能得到答案.
仔细观察可以发现: 把所有的边从小到大排序, 然后从 1 节点开始遍历即可. 60pts 到手!
剩下的 \(m=n\)部分分就是重点了.
基环树有这么几个性质:
基环树断了一条边可能就是一棵树.
基环树有且只有一个环.
再看到数据范围:\(1 \leq n \leq 5000\)!
结合去年的 i7 8700k, 不由得让你想到了 \(n^2\)算法!
所以算法出来了: 枚举所有的边, 每次断掉其中的一条边, 在新图上面 dfs, 求出最小字典序的答案.
还想优化? 先跑一遍 tarjan 的点双, 若一条边的两个端点属于同个点双即为环上的边, 在上面断边, 会去掉那些不是树的断法.
在 luogu 上面这两种做法开 O2 都是能过的.
加强版不会做
代码:
D2T2 填数游戏
待填...
D2T3 保卫王国
动态 dp. 这辈子都不可能学的.
来源: http://www.bubuko.com/infodetail-2945128.html