Home > Old Blog Posts > New Start

New Start


不管考的怎么样,万恶的补考终于过去了。

新的学段已经过了4周,算起来的确很快,离初赛越来越近了,虽然我还没有采取什么实质性的复习行动。

今天又拜读了一下NOIP的复赛大纲,大致列了几点:

1、离散数学

2、分治法

3、模拟法

4、贪心法

5、搜索

6、动态规划

2和4被我无视很久了,但若变种起来也可以难的变态,还是得抽时间看一看,但总的来说,在刷完usaco之后,回过头来看这些东西,与去年这时候的自己相比,不知提升了多少。

于是我又不自量力地看了一下NOI的山寨大纲:

时间复杂度(渐近时间复杂度的严格定义,NP问题,时间复杂度的分析方法,主定理
排序算法(平方排序算法的应用,Shell排序,快速排序,归并排序,时间复杂度下界,三种线性时间排序,外部排序)
数论(整除,集合论,关系,素数,进位制,辗转相除,扩展的辗转相除,同余运算,解线性同余方程,中国剩余定理
指针(链表,搜索判重,邻接表,开散列,二叉树的表示,多叉树的表示)
按位运算(and,or,xor,shl,shr,一些应用)
图 论(图论模型的建立,平面图,欧拉公式与五色定理,求强连通分量,求割点和桥,欧拉回路,AOV问题,AOE问题,最小生成树的三种算法,最短路的三种算 法,标号法,差分约束系统,验证二分图,Konig定理,匈牙利算法,KM算法,稳定婚姻系统,最大流算法,最小割最大流定理,最小费用最大流算法
计算几何(平面解几及其应用,向量,点积及其应用,叉积及其应用,半平面相交,求点集的凸包,最近点对问题,凸多边形的交,离散化与扫描
数 据结构(广度优先搜索,验证括号匹配,表达式计算,递归的编译,Hash表,分段Hash,并查集,Tarjan算法,二叉堆,左偏树,斜堆,二项堆, 二叉查找树,AVL,Treap,Splay,静态二叉查找树,2-d树,线段树,二维线段树,矩形树,Trie树,块状链表
组合数学(排列与组合,鸽笼原理,容斥原理,递推,Fibonacci数列,Catalan数列,Stirling数,差分序列,生成函数,置换,Polya原理
概率论(简单概率,条件概率,Bayes定理,期望值
矩阵(矩阵的概念和运算,二分求解线性递推方程,多米诺骨牌棋盘覆盖方案数,高斯消元)
字符串处理(KMP,后缀树,有限状态自动机,Huffman编码,简单密码学
动态规划(单调队列,凸完全单调性,树型动规,多叉转二叉,状态压缩类动规,四边形不等式
博奕论(Nim取子游戏,博弈树,Shannon开关游戏
搜索(A*,ID,IDA*,随机调整,遗传算法
微积分初步(极限思想,导数,积分,定积分,立体解析几何

其中,标为红色的都是尚未掌握或掌握不深的……

粗略一扫,又被打击了(-_-),山外有山,这是永恒不变的真理,但这份提纲也说明,我还有很多可以学的东西,我还有很多想要去学的东西,总把算法局限于NOIP之内,我可能会因此而失去很多东西。

Lots of things to do…….Now, it’s a new start.

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: