成功的要素没有靠机遇和取巧（遇到已做过的题或直接抄写示例）成功的任何可能，只有靠勤奋+智慧

   基础（数据结构和算法知识+编程技术）+良好的心理素质（沉稳+爆发力）+悟性（在扎实的基础上的灵感和悟顿）

复习

1、  看书、补充知识

2、  作题（家中做题专找“吃不准”的题目，并把问题拿到集训队里来讨论）

3、  总结已做成功的试题，进行一般题形和一般对应算法的“归类”，构建知识网络

竞赛解题分析的思维过程（一般在30分钟以内）

  机理分析法→统计分析法（构造部分解，寻找数学规律）→有无比较合适的贪心策略→用搜索创关

数据结构

1、  并查集（发展趋势：一般并查集→计算并查集中元素的相对位置→？。一般采用树结构，并进行路径压缩）

2、  查找问题：（哈希表（注意哈希函数的选择）、哈夫曼（已知顶点的访问频率）、线段树、在二叉树上进行统计（保留取间的中间点、用一维数组存储）、树状数组）

搜索

1、  事先考虑数学规律和贪心策略（俄罗斯方块）

2、  尽量减少搜索范围（循环变量的上下界和边界条件）、苛刻约束条件（尽量利用计数公式）

动态程序设计

向深层次发展

1、  显性变隐性（难以看出阶段特征、难以确定状态和状态转移方程）

2、  注意递归求解（九头龙）

3、  多进程决策问题（多条最短路径）

4、  双重动态程序设计（在添m条有权边的情况下求最短路径）

5、  对有些具备阶段性和状态转移特征的问题，可通过动态程序设计计算所有方案

6、  对不具备最优子结构、但具备阶段性和状态转移特征的问题，可通过动态程序设计转化为判定性问题，然后递推最优解

模拟问题

1、  直叙式模拟不疏漏任何条件，精心设计数据结构（天鼠行动）

2、  筛选法模拟

3、  构造法模拟（关键是数学模型）

对策问题

注意博弈游戏，关键是哪些情况可产生相同局面，怎样避免它们的重复演算，怎样为局面设计合适的数据结构，怎样从局面的演变过程只找出数学规律

一般性方法

 

l状  态

    列举影响结局胜负的所有因素，综合描述成“状态”。根据对局时状态之间的变化，自顶而下构造出“状态转移的拓扑结构”。

l扩展规则

在某些场合下，还可以记录一个状态先手胜（负）的最大（最小）利益，以数值形式描述，再根据题目中相应的条件，构成新的具有针对性的推算规则

l实现方法

  1预先处理（关键）

  列举状态；构造“状态转移的拓扑结构”；动态规划或记忆化搜索求状态先手胜负。

  1对局策略

  依据已知的状态胜负，时刻把先手必败的状态留给对方。

 

特殊性方法”

l逆向分析

 

是从结局或残局出发，自底而上分析，无须构造“状态转移的拓扑结构”，无须考察所有可能的状态与策略，时间和空间复杂度相对于“一般性方法”都不高。

  

一般性方法：

     自顶而下    考察所有状态胜负

   特殊性方法：

     自底而上    研究一类平衡状态

l胜负规则  

一般性方法：有通行胜负规则    

    特殊性方法：无通行胜负规则

“一般性方法”从统一的角度，考察所有状态，来决定对局策略。

    “特殊性方法”从特殊的角度，考察一类状态，来决定对局策略。

 

几何计算

1、  计算三角形面积和多边形面积

2、  两条有向线段P0P1、P0P1 在公共端点P0处的转向（叉积）

3、  确定两条连续的有向线段P0P1和P1P2 在P1处的转向（添辅助线和叉积）

4、  确定两条线段是否相交（跨立实验和快速排斥试验）、两个长方形是否相交（与坐标轴平行与不平行）、在一组线段中确定任意一对线段是否相交

5、  寻找凸包（graham扫描法或Jarris步进法）

6、 寻找最近点对

图论1、      计算连通图和连通分支、计算求极大强连通子图

2、      对连通的、且不存在“桥” 的无向图G，给定每条的方向，使之成为强连通图。

3、      计算顶点连通度和块（网络流和深度优先搜索）

4、      计算边连通度（网络流）

5、      计算顶色数（贪心法）和边色数（边转化为顶点计算）

6、      二分图的最大匹配（网络流或匈牙利算法），边带权，则为最佳匹配，关键是把问题转化为二分图

7、      在允许重复走边的情况下，计算走遍所有边的最短路径。