Skip to content

Tag Archives: 省选

省选训练,0410总结

自从省选训练的上一阶段(做完及总结USACO)圆满结束之后,又过了几天,有必要把这几天再适当总结一下。 写了平衡树两种——自顶向下Splay以及Treap,感觉对后者理解比较深刻,但前者实在强大,二者是都需要十分熟练地掌握的,在省选前还要写个两三遍。 理解了虚二叉树,但它的可替代性比较大,不需要再练习了。 写了2007天津选拔一试,第一遍得分只有140/400。第一题对了,但一开始没看清题导致浪费了一点时间,要注意通读、精读题目。第二题现在还没完全搞懂。第三题当时对了一半,应该主要是没有预先排序的缘故,没有深刻地理解某些东西。第四题的确是想复杂了,当比分有序之后就变成了最少用几个不下降序列覆盖,这个东西等于最长下降序列的长度,这也是刚刚知道的。总之,注意读题。不过想来真正考试的时候有纸版的卷子勾勾划划应该好些。 写了2006浙江选拔一试,第一遍得分170/360,很有进步。第一题显然需要用两个平衡树来乱搞,根本就没有写,哪天精神状态很好时可以尝试写一下,不过考试时真遇到这样的题估计还是放弃;第二题真是要感谢USACO,和“丑数”原来是一样的,WA一组似乎还是因为没看清本质——质因数个数大于前一个数里面的最小的,多加了一个限制条件就漏了解。第三题核心部分是很简单的DP,但预处理得出所有的路径是一个麻烦事;在得出路径时我剪枝很多——当前可以到达终点的只能往终点之类,而这是错的,这是有权图,而且不一定满足三角形不等式,把这剪枝去掉,再加一个若有多余的点则剪枝的条件就能AC了;第四题树形DP,很简单,一遍AC,yeah(不过分值怎么偏小呢……)!这次给我的启迪是:剪枝条件是一定要仔细思考、耐心检查的部分。 下一步准备打印一些经典的代码,比如treap、splay、flow、hungary,等等……多看多背。 本周每天至少写两套题,写一个新算法。

省选训练,下一步的计划

现在USACO Training还剩5道题,今晚不准备再做了。明天或后天应该可以做完。 下一步就是对一些重要的算法、数据结构之类要进行学习研究。 第一步必须要学的罗列在这里: 平衡树。掌握一种即可,还是优先选择treap或splay。(3) 线段树。要灵活掌握,熟练编程。(4) 图的DFS:割点、桥、强联通子图。都要会写。(5) 树状数组。记住公式。(1) KMP算法。仔细体会,不妨背下来。 (1) 括号中是需要练习的题数。 研究完每种都要写一篇短文尽量清晰地描述其思想。

省选训练计划

I. 需掌握的算法与数据结构: 网络流(最短路增广,写一次最小费用流) 二分匹配(Hungary,可能的话KM) 平衡树(Treap or Splay) 可并堆(斜堆) Hash表(至少写一次需解决冲突的,用拉链) 扩展的欧几里德 KMP算法 树状数组 后缀树(n^2的当然熟练掌握,其它尽量) 线段树(多练习各种变形) A*/IDA*搜索(多找几道,练习这个框架) 计算几何(先背下来叉乘那些公式吧,写一次凸包) 动态规划(看论文,多练) 组合数学(学哪些呢?) 图的DFS的高级应用(割点与桥) 块状链表(尽量掌握) 高精度运算(加减乘当然要熟练,除法尽量) II.需要做的题 USACO Training剩下全部的题。 USACO近几次月赛中Silver的题,尽量作些Gold的题。 能找到数据的所有河南省选题。 尽可能多的做各方面与省选难度接近的题。(在黑书、Ural、NOI、IOI……中选题目) III.时间安排

那就拼一次

前天班主任和教务主任告诉我说,这次考试完以后安排我停上正课、训练奥赛,以备战4月21日的省队选拔。 那就拼搏一次吧。三周的时间,全天在机房里,无尽地做题与思考。 我希望进入省队,我希望打开一片新的天地。 明天制定详尽的备战计划,不过不会发出来。 这一段时间里,我的blog不会更新“程序园”、“军机处”、“诗日记”之外的内容,见谅。