2016暑假集训总结

2016暑假集训总结

前言

为期两个月的暑假集训算是告一段落了,我也如愿以偿地进入了一班。这个暑假,我的收获也不少,信息水平也开始上来了,不过仍然存在一些问题,在这里,我将做一个系统的总结。

优势总结

从暑假的各个考试来看,我基本上都能稳定在前几名,那种波动很大的情况只出现了一次,是在选拔考试结束后精神放松了的一次。而全场第一也有过几次,大部分都是题目简单的时候。

因此我发现,我的优势在于简单题,只要没有想错,并且精神集中以及写了对拍,那么这道题我基本不会丢分,而且速度会比别人快很多。这说明我的思维速度是很快的,简单点说就是我有智商优势。虽说如此,但我也经常出现想错了或者考虑不周全的的情况,这也有待改进。

另外一点,我有优势的算法有:贪心、线段树、图论、搜索。这些大概是一些基础的算法,而由于我学习时间较长,因此这些算法都非常熟悉。另外一个就是数学题目,我基本上思考的很快,并且总能想出正解。

劣势总结

事实上我的劣势也很明显。

首先是身体上的劣势。我经常考试的时候精神状态不佳,以至于进入状态较慢,一开始做的题目总是想不清楚。然后出错,幸好我做完题目有写对拍的习惯……所以还好。

另外一个就是考虑不周到,这个考场上很难发现,只能平时做题多总结。

算法方面的问题还是DP、平衡树、LCT等高级算法。

DP总结在下面。

经验总结

虽然感觉DP做的题也不多,但是就已经做过的题目总结一下经验:

  • 传统DP:重点在于设计状态,一般的DP状态设计方法步骤:
  • 划分阶段:如按照物品划分、按照时间划分、按照位置划分……
  • 补充状态:划分阶段以后要让阶段拥有状态,比如按物品划分还要记录剩余容量;按时间划分可能要状压记录已选部分;按位置划分……
  • 写出动规方程:这一步没有什么捷径,主要还是看状态,如果状态划分的好就容易写。
  • 编程解决
  • DP优化

常见的优化方法有:单调队列、二分栈、斜率优化、数据结构优化(线段树、树状数组)、CDQ分治

  1. 单调队列:常用于决策单调的情况,比如每一个状态都由之前的状态转移过来,而如果一个状态y不能从状态x转移过来那么状态y之后的状态也不能从x转移过来;如果一个状态y能转移到的最优状态是x,那么在x的后面一定不存在比x更优的状态。
  2. 二分栈:跟单调队列有点像,但是不满足队首不合要求就可以弹出的性质,因此需要保留队首,在查询的时候二分查找。
  3. 斜率优化:斜率优化一般需要转化式子,将方程式中的含有k的项单独分离出来,变成(y1-y2)/(x1-x2)的形式,也就是维护一个凸包,然后二分找最值。
  4. 如果斜率优化中x不满足单调性,那么我们需要使用cdq分治。

改进方向

现在练习的方向主要有二。

一是不熟练的算法和数据结构,清单如下:

  • 各种动态规划+优化
  • 较难的贪心、需保证正确性的贪心
  • 二分答案后的贪心
  • 平衡树的选择与优化
  • 数学类型题目模型提取与转化
  • 各种算法的常数优化
  • 数据结构的选择与优化
  • 隐式图的提炼与构建

二是考场策略的适应与改进,包括以上讲的时间分配、心态把控和考场检查。

练习方法主要是刷题+总结,争取在接下来的时间里所有算法尽可能多熟悉几遍,常用的算法保证看到题目要迅速得出解法。

考场策略方面要把每次考试都当做联赛,高度重视,在模拟中总结经验,坚持每次考试写心态日记,总结做得好的地方和失误,并时常复习,争取避免再犯。

不如来评论一发?