《NOIP2010集训小资料(1)》由会员分享，可在线阅读，更多相关《NOIP2010集训小资料(1)（5页珍藏版）》请在金锄头文库上搜索。
1、NOI20集训小资料 章琨目录1反约瑟夫问题2。空间的计算3。树的性质.最大公约数. Ctalan数6。最短路floyed。小技巧8。最短路PF9.move函数1.最长上升(下降）子序列nogn11.字母树1.几类背包问题3最长上升公共子序列14。树的遍历1。循环小数转分数16.字典序法求排列。康托展开8。随机顺序19.最小区间覆盖问题2.短路 Fbonai数列2关键路径。中缀转后缀24后缀转中缀2最小生成树Krus考试心得1.考试中在一定的时间如果没有想出过全点的算法就抓紧时间编写一个能过部分点的朴素或可过样例的骗分算法。2.考试应该想好了在编程前要想好算法编写时要思考语句是否会带来不良的影
2、响。3.考试时要善于发现规律，而且推出某个规律时，要多次进行验证以保证其正确性。看题时一定要仔细,特别是某些没有样例的题。当算法正确，程序错误时，暂时放弃，过几天再重打一遍。6考试时要注意数据范围，当数据范围较小时可先使用枚举等方法然后再进行动规或搜索。7考试时要在重要的(可能出错的)地方用笔划记，使不该犯的错误尽可能避免，每次都能发挥出自己的水平。8.一个题目不一定就是只有一种算法可能是几个算法的结合。9。注意题目中与所代表的意义；与 所代表的意义。10.程序编写完成时要注意特殊情况和极端情况的考虑.11。在所有题目编完后，要出几个极限数据判断是否会出现、215等错误。12。在遇到数学或物理
3、问题时要先把问题分析清楚，再编程。13。考试时想到的思路和思维的闪光要在草稿纸上记录下来，再验证其可行性(包括：编程复杂度、实现时间、时间复杂度、空间复杂度）,可行性较低的要及时舍弃。14。如果实在想不到好的算法就赶快打一个搜索.15.数组最好比题目中的数据范围大一些，避免边境情况未考虑完全时出现21。6.能开it64的尽量开,数组最好从开始17。做题时不要一开始就想骗分算法，最好先想正确算法.算法精华1. 反约瑟夫环问题 fi代表个人报数，报到j的出局时最后出圈的人的序号 =1 =(fi-1+1) md i+12. 空间的计算常用类型的字节数long 4integer 2in64 8Exte
4、de1Booean 1trin 256l 6每类型所占字节*104*102个数（单位M）3. 如果一个图中任意两点有且只存在一条简单路径那么它就是一棵树4. 求最大公约数(欧几里德算法)=链接 untincd(x，y:lngt）：longnt； begin if =0 tengc:x elc：=d(,xmod y)； en；最小公倍数*最大公约数=两数之积5. 卡特兰数链接 通项公式：= 递推公式：fn=f*fn-f2fn2+fn-1f1 n=2 f1=1前十项1位2位位4位位6位7位8位位1位1214421329304267966. floed求最短路=链接 Fork：=1 o n do f
5、ori：=1 to n do for j:= to n do ifi，kfk,jfi，th fi，j：=i，k+，j； 中间值要放在外层循环7. 小技巧 div 2 的时间长于 shr1 i：i+ 的时间长于inc(i) i:=i1的时间长于 dc（i） loint 比 tge 快8. SPFA求单元最短路链接 注意事项： 1Nexti代表在边集数组中下标为的边的同起点的边在边集数组中的下标 2iai代表起点为的边在边集数组中的下标 3无向边要分为两个有向边9. mve函数的用法(速度是循环的10倍以上）考试时最好不要使用 Move,bj，szof(类型)*代表从数组第i位到第i+k-1位的部
6、分赋值给b数组第j位到第+1位10. nlog的最长上升(下降)子序列=链接 Shu代表数列的第i位 F代表以第i项结尾的最长上升子序列的长度 Gk代表长度为的最长上升子序列的最小值（Gk=min(shi） i满足fi=k） L为数组的尾指针 主要步骤: 1当shuiglen那么尾指针后移1位，glen：=shi 2当ui=gle那么在，len这个区间二分查找shi在x，中则f：=y并更新gy:=i11. 字母树的建立=链接 Trei，c代表父亲节点为i的点，本身字母为c的点的编号 e为除根节点外节点个数 可用于找公共前缀12. 各类背包问题的分析=链接 为费用 T为价值 10/1背包 For
7、 i：= 1 to n o or j:=vonto 1d Iffjfi-w+tithen j:f-w+ti 2完全背包 Fr i：= 1to n For j: t v d If f链接 代表b序列尾位为i时的最长长度 Fi=max(f）1 i14. 树的3种遍历的顺序: 先序遍历顺序:根节点左子树右子树 中序遍历顺序：左子树根节点右子树 后序遍历顺序：左子树右子树根节点15. 循环小数转为分数=链接 0。 a a a = 位 X位0 b a a a a = Y位 X位 X个9 Y个 Y个注: 表示循环节16. 字典序法求下一个排列=链接 主要步骤: 从右往左找到第一个比右边的数小的数的编号j
8、2在j+1,n中找到比aj大最小的数编号为k 交换j和位置上的数 将区间j+1，n中的数倒转17. 全排列的项数与排列的转换求排列在全排列中的项数（康托展开)： i表示排列中的第位（从右往左)的右边有多少个数比比它小 项数= 求全排列的第i项得排列 把i变为阶乘进制数 f fiI th bein fi+：i1+idv；f:=imo ;end； 即 第j位为剩下的数中第j+1小的数，然后依次还原排列18. 随机一个顺序 时间复杂度O（n) 枚举每一个点与随机到的位置交换19. 最小区间覆盖问题=008年周小博论文描述：有n个区间，选择尽量少的区间，使得这些区间完全覆盖某线段s，t算法：1按左端点
9、坐标排序2每次选择覆盖点的区间中右端点坐标最大的一个，并更新s3直到所选区间已包含t20. 无向图中第K短路的求法链接 二分K短路的长度 每次求出长度小于等于二分长度的路径条数 条数大于等于K时右边界左移 条数小于K时左边界右移直到左右边界相差,k为1时输出;否则输出y21. Fboncci数列 递推公式：f=fi-1fi-2 通项公式：22. 关键路径算法步骤：1添加一个起点和终点，求出AE网中的拓扑序列,若有环工程无法开始。起点的最早发生时间为0,按拓扑序列的顺序求出其他节点的最早发生时间(父节点的最早发生时间为子节点中最早发生时间加上到父节点的权值最大的一个）。终点的最早发生时间等于最晚
10、发生时间，按拓扑逆序列求出其他节点的最晚发生时间（子节点的最晚发生时间为父节点的最晚发生时间减去子节点到父亲的时间)。4如果节点的最早发生时间等于最晚发生时间则该工程为关键工程。5依次连接关键工程即为关键路径。23. 中缀转后缀算法步骤:1判断式子是否被括号所包裹,有则去除。在式子中找到一个不在括号中的最靠后的加减号。在式子中找到一个不在括号中的最靠后的乘除号.4如果存在加减号则取加减否则取乘除5左右进行递归处理.24. 后缀转中缀算法步骤：1依次将式子中的字符入栈，如果发现符号则将栈顶的元素变为字符的右儿子，次栈顶元素变为左儿子,栈顶指针减2。2输出时先输出左子树,然后输出本身，再输出右子树，注意添加括号。3子树递归处理。25. 最小生成树Kruskal算法步骤:将边按长度从小到大排序2每次取出最小的边，若不会构成环则加入树中,用并查集将两端点合并文中如有不足，请您指教！ /
