成功的要素没有靠机遇和取巧（遇到已做过的题或直接抄写示例）成功的任何可能，只有靠勤奋+智慧
基础（数据结构和算法知识+编程技术）+良好的心理素质（沉稳+爆发力）+悟性（在扎实的基础上的灵感和悟顿）
复习
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、 在允许重复走边的情况下，计算走遍所有边的最短路径。
本文地址：http://com.8s8s.com/it/it32576.htm