Skip to content

省选训练,0410总结

自从省选训练的上一阶段(做完及总结USACO)圆满结束之后,又过了几天,有必要把这几天再适当总结一下。

写了平衡树两种——自顶向下Splay以及Treap,感觉对后者理解比较深刻,但前者实在强大,二者是都需要十分熟练地掌握的,在省选前还要写个两三遍。

理解了虚二叉树,但它的可替代性比较大,不需要再练习了。

写了2007天津选拔一试,第一遍得分只有140/400。第一题对了,但一开始没看清题导致浪费了一点时间,要注意通读、精读题目。第二题现在还没完全搞懂。第三题当时对了一半,应该主要是没有预先排序的缘故,没有深刻地理解某些东西。第四题的确是想复杂了,当比分有序之后就变成了最少用几个不下降序列覆盖,这个东西等于最长下降序列的长度,这也是刚刚知道的。总之,注意读题。不过想来真正考试的时候有纸版的卷子勾勾划划应该好些。

写了2006浙江选拔一试,第一遍得分170/360,很有进步。第一题显然需要用两个平衡树来乱搞,根本就没有写,哪天精神状态很好时可以尝试写一下,不过考试时真遇到这样的题估计还是放弃;第二题真是要感谢USACO,和“丑数”原来是一样的,WA一组似乎还是因为没看清本质——质因数个数大于前一个数里面的最小的,多加了一个限制条件就漏了解。第三题核心部分是很简单的DP,但预处理得出所有的路径是一个麻烦事;在得出路径时我剪枝很多——当前可以到达终点的只能往终点之类,而这是错的,这是有权图,而且不一定满足三角形不等式,把这剪枝去掉,再加一个若有多余的点则剪枝的条件就能AC了;第四题树形DP,很简单,一遍AC,yeah(不过分值怎么偏小呢……)!这次给我的启迪是:剪枝条件是一定要仔细思考、耐心检查的部分。

下一步准备打印一些经典的代码,比如treap、splay、flow、hungary,等等……多看多背。

本周每天至少写两套题,写一个新算法。

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*