NOIP复习资料 6页

NOIP复习资料一、重要定理和公式1.Fibonacci数列A[1]=1;A[2]=1;A[n]=A[n-1]+A[n-2];2.Catalan数：考虑具有n个结点不同形态的二叉树的个数H[n]H[0]=1;H[n)=H[0]H[n-1]+H[1]H[n-2]+H[2]H[n-3]…+H[n-2]H[1]+H[n-1]H[0];->H[n]=(1/(n+1))*C(n,2n)3.第二类Stirling数：集合总的划分数s(n,k)表示含n个元素的集合划分为k个集合的情况数A.分类：集合{An}存在，则有s(n-1,k-1);不存在则An和放入k个集合中的任意一个，共k*s(n-1,k)种。s(n,k)=0(k=0ornk>=1)*:求一个集合总的划分数即为sigema(k=1..n)s(n,k).4．数字划分模型*NOIP2001数的划分将整数n分成k份，且每份不能为空，任意两种分法不能相同(不考虑顺序)。d[0,0]:=1;for(p:=1;P<=n;P++)for(i=p;i<=n;i++)for(intj=k;j>=1;j--)dp[i][j]=d[i][j]+d[i-p][j-1];cout<表示，则Ee[I]=Ve[j];d.边活动最晚开始时间El[I],若边I由表示，则El[I]=Vl[k]–w[j,k];若Ee[j]=El[j]，则活动j为关键活动，由关键活动组成的路径为关键路径。求解方法：a.从源点起topsort,判断是否有回路并计算Ve;b.从汇点起topsort,求Vl;c.算Ee和El;6．拓扑排序找入度为0的点，删去与其相连的所有边，不断重复这一过程。7.回路问题Euler回路(DFS)定义：经过图的每条边仅一次的回路。（充要条件：图连同且无奇点）Hamilton回路定义：经过图的每个顶点仅一次的回路。一笔画充要条件：图连通且奇点个数为0个或2个。9．判断图中是否有负权回路Bellman-ford算法x[I],y[I],t[I]分别表示第I条边的起点，终点和权。共n个结点和m条边。10．第n最短路径问题*第二最短路径：每举最短路径上的每条边，每次删除一条，然后求新图的最短路径，取这些路径中最短的一条即为第二最短路径。*同理，第n最短路径可在求解第n-1最短路径的基础上求解三、背包问题1．0-1背包：2．可重复背包A求最多可放入的重量。B.求可以放入的最大价值。C.求恰好装满的情况数。2．多重背包\n四、排序算法1.快速排序：B.插入排序：1.快速排序：B.插入排序：C.选择排序：D.冒泡排序E.堆排序：F.归并排序五、高精度计算1．高精度加法2．高精度减法3．高精度乘以低精度4．高精度乘以高精度5．高精度除以低精度6．高精度除以高精度六、树的遍历1．已知前序中序求后序2．已知中序后序求前序3．已知前序后序求中序的一种七进制转换1任意正整数进制间的互化除n取余2实数任意正整数进制间的互化乘n取整3负数进制：设计一个程序，读入一个十进制数的基数和一个负进制数的基数，并将此十进制数转换为此负进制下的数：-R∈{-2，-3，-4,....-20}八全排列与组合的生成1排列的生成：（1..n）2组合的生成(1..n中选取k个数的所有方案)九.查找算法1二分查找2树形查找二叉排序树：每个结点的值都大于其左子树任一结点的值而小于其右子树任一结点的值。查找\n十、贪心会议问题（1）n个活动每个活动有一个开始时间和一个结束时间，任一时刻仅一项活动进行，求满足活动数最多的情况。解：按每项活动的结束时间进行排序，排在前面的优先满足。（2）会议室空闲时间最少。（3）每个客户有一个愿付的租金，求最大利润。（4）共R间会议室，第i个客户需使用i间会议室，费用相同，求最大利润。回溯法DfsBfs双向bfs十五、数据结构相关算法1．链表的定位2．单链表的插入操作3．单链表的删除操作4．双链表的插入操作（插入新结点q）5．双链表的删除操作第四章搜索问题一.递归与回溯1.n皇后问题一、匹配问题1两行正整数，第一行与第二行中相同的数可匹配，求最大匹配数满足：a.每条p匹配线段恰好和一条q-匹配线段相交(p<>q),b.不存在两条线段从一个数出发。F[I,j]:第一行前I个与第二行前j个的最大匹配数。F[I,j]=Max{f[I,j-1],f[j,I-1],max{f[p-1,q-1]+2}}([p,j]和[I,q]是两个匹配)2河两岸各有n个城市，两岸城市一一对应为友好城市，求友好城市的最大匹配使任意友好城市间的航线不相交。*可转化为求最长非递降子序列二、序列问题1最长非递降子序列2最长公共子串(LCS)三、分割问题四、矩阵路径五、资源分配问题