第N次模拟(2018年10月16日) 总结

这是我第一次做$\text{NOI}$导刊的题，这套题难度适中~~（事实上只有$\sout{\text{T2}}$比较难）~~，做起来还是比较愉快的。 $\text{T1}$是比较简单的一道题，可以做到总复杂度$\text{O}(n)$，可是有大佬写了使用复杂数据结构的方法，实在是tql，%%%。 $\text{T3}$也相对比较简单，看题解其实用堆就可以解决问题，但是我当时没有太多思路，于是手写了一棵$\text{Treap}$，动态维护……当然，其实我的做法的最劣时间复杂度是不满足题目要求的，但是平均时间复杂度可以接受。 $\text{T4}$的数据范围其实不难过，用$\text{dfs}$＋剪枝、$\text{Floyd}$或者最优比率路径的二分法都可以。但是比赛题目的数据有环（题目描述中指明是有向无环图），所以$\text{dfs MLE}$了，只有$\text{Floyd}$能过。 $\text{T2}$是一道$\text{dp}$题（这就触及到我的知识盲区啦），确实需要好好做做。这道题没有涉及太难的优化方法，只是计算的顺序上要有所调整。 总结一下，解决$\text{dp}$后效性的方法主要有两种，一是扩充状态，即把有后效性的内容记入状态；二是调整计算顺序。第一种方法我比较熟悉，而第二种方法我还要多进行学习。