首页>>技术前沿>>网站/软件行业动态
初期
一.基本算法:
枚举.
递归和分治法.
递推.
二.图算法:
图的深度优先遍历和广度优先遍历.
最短路径算法
最小生成树算法
二分图的最大匹配 (匈牙利算法)
最大流的增广路算法(KM算法).
三.数据结构.
串
排序(快排、归并排(与逆序数有关)、堆排)
简单并查集的应用.
哈希表和二分查找等高效查找法(数的Hash,串的Hash)
哈夫曼树
堆
trie树(静态建树、动态建树)
四.简单搜索
深度优先搜索
广度优先搜索
简单搜索技巧和剪枝
五.动态规划
背包问题.
简单DP (最长公共子序列) (最优二分检索树问题)
六.数学
组合数学: 1.加法原理和乘法原理. 2.排列组合. 3.递推关系.
数论. 1.素数与整除问题 2.进制位. 3.同余模运算.
计算方法. 1.二分法求解单调函数相关知识
七.计算几何学.
几何公式.
叉积和点积的运用(如线段相交的判定,点到线段的距离等).
多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)
凸包.
中级:
一.基本算法:
C++的标准模版库的应用.
二.图算法:
差分约束系统的建立和求解.
最小费用最大流
双连通分量
强连通分支及其缩点.
图的割边和割点
最小割模型、网络流规约
三.数据结构.
线段树.
静态二叉检索树.
树状树组
RMQ.
并查集的高级应用.
KMP算法.
四.搜索
最优化剪枝和可行性剪枝
搜索的技巧和优化
记忆化搜索
五.动态规划
较为复杂的动态规划(如动态规划解特别的旅行商TSP问题等)
记录状态的动态规划.
树型动态规划(
六.数学
组合数学: 1.容斥原理. 2.抽屉原理. 3.置换群与Polya定理4.递推关系和母函数.
数学. 1.高斯消元法2.概率问题. 3.GCD、扩展的欧几里德(中国剩余定理)
随机化算法
七.计算几何学.
坐标离散化.
扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用)
几何工具的综合应用.
高级:
一.基本算法要求:
代码快速写成,精简但不失风格
保证正确性和高效性.
二.图算法:
度限制最小生成树和第K最短路.
最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)
小生成树.
无向图、有向图的最小环
三.数据结构.
trie图的建立和应用.
LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和 在线算法
双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的目的).
左偏树(可合并堆).
四.搜索
广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法.
深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法.
五.动态规划
需要用数据结构优化的动态规划.
四边形不等式理论.
较难的状态DP
六.数学
组合数学. 1.MoBius反演2.偏序关系理论.
博奕论. 1.极大极小过程2.Nim问题.
七.计算几何学.
半平面求交
可视图的建立
点集最小圆覆盖
【全文完】
版权声明:
1、陕西弈聪网站内容中凡注明“来源：XXX（非陕西弈聪网站）”的作品，转载自其它媒体，转载目的在于传递更多信息，其中涉及的网站建设，网站优化，百度关键词优化，西安软件开发等技术细节并不代表本站赞同支持其观点，并不对其真实性负责。对于署名“陕西弈聪”的作品系本站版权所有，任何人转载请署名来源，否则陕西弈聪将追究其相关法律责任。
2、本站内容中未声明为“原创”的内容可能源自其它网站，但并不代表本站支持其观点，对此带来的法律纠纷及其它责任与我方无关。如果此内容侵犯了您的权益，请联系我方进行删除。
企业动态
