当前位置:首页 >> 其它考试 >>

NOIP2010集训小资料


NOIP2009 集训小资料

NOIP2009 集训小资料
——章琨
目录
1.反约瑟夫问题 反约瑟夫问题 2.空间的计算 空间的计算 3.树的性质 树的性质 4.最大公约数 最大公约数 5. Catalan 数 6.最短路 floyed 最短路 7.小技巧 小技巧 8.最短路 SPFA 最短路 9.move 函数 10.最长上升 下降 子序列 最长上升(下降 子序列[nlogn] 最长上升 下降)子序列 11.字母树 字母树 12.几类背包问题 几类背包问题 13.最长上升公共子序列 最长上升公共子序列 14.树的遍历 树的遍历 15.循环小数转分数 循环小数转分数 16.字典序法求排列 字典序法求排列 17.康托展开 康托展开 18.随机顺序 随机顺序 19.最小区间覆盖问题 最小区间覆盖问题 20.K 短路 21. Fibonacci 数列 22.关键路径 关键路径 23.中缀转后缀 中缀转后缀 24.后缀转中缀 后缀转中缀 25.最小生成树 Kruskal 最小生成树

By zk

NOIP2009 集训小资料
考试心得
1.考试中在一定的时间如果没有想出过全点的算法就抓紧时间编写一个能过部分点的朴素 或可过样例的骗分算法。 2.考试应该想好了在编程前要想好算法编写时要思考语句是否会带来不良的影响。 3.考试时要善于发现规律,而且推出某个规律时,要多次进行验证以保证其正确性。 4.看题时一定要仔细,特别是某些没有样例的题。 5.当算法正确,程序错误时,暂时放弃,过几天再重打一遍。 6 考试时要注意数据范围,当数据范围较小时可先使用枚举等方法然后再进行动规或搜索。 7 考试时要在重要的(可能出错的)地方用笔划记,使不该犯的错误尽可能避免,每次都能发 挥出自己的水平。 8. 一个题目不一定就是只有一种算法可能是几个算法的结合。 9.注意题目中 x 与 y 所代表的意义;m 与 n 所代表的意义。 10.程序编写完成时要注意特殊情况和极端情况的考虑。 11.在所有题目编完后,要出几个极限数据判断是否会出现 201、215 等错误。 12.在遇到数学或物理问题时要先把问题分析清楚,再编程。 13.考试时想到的思路和思维的闪光要在草稿纸上记录下来,再验证其可行性(包括:编程复 杂度、实现时间、时间复杂度、空间复杂度),可行性较低的要及时舍弃。 14.如果实在想不到好的算法就赶快打一个搜索。 15.数组最好比题目中的数据范围大一些,避免边境情况未考虑完全时出现 201。 16.能开 int64 的尽量开,数组最好从 0 开始 17.做题时不要一开始就想骗分算法,最好先想正确算法。

算法精华 1. 反约瑟夫环问题
f[i]代表 i 个人报数,报到 j 的出局时最后出圈的人的序号 f[1]=1 f[i]=(f[i-1]+j-1) mod i+1

2. 空间的计算
常用类型的字节数 longint integer int64 Extended 4 2 8 10 Boolean String Real 1 256 6 每类型所占字节*1024*1024*个数(单位 M)

3. 如果一个图中任意两点有且只存在一条简单路径那么它就是一棵树 4. 求最大公约数(欧几里德算法)=>链接
function gcd(x,y:longint):longint; begin if y=0 then gcd:=x else gcd:=gcd(y,x mod y);
By zk

NOIP2009 集训小资料
end; 最小公倍数*最大公约数=两数之积

5. 卡特兰数=>链接
通项公式:f[n]=

(2n)! 2n × (2 * n 1) × .... × (n + 3) × (n + 2) = n! × (n + 1)! n × (n 1) × .... × 3 × 2
f[1]=1 8位 1430 9位 4862 10 位 16796

递推公式:f[n]=f[1]*f[n-1]+f[2]*f[n-2]+…+f[n-1]*f[1] n>=2 前十项 1位 2位 3位 4位 5位 6位 7位 1 2 5 14 42 132 429

6. floyed 求最短路=>链接
For k:= 1 to n do for i:= 1 to n do for j:= 1 to n do if f[i,k]+f[k,j]>f[i,j] then f[i,j]:=f[i,k]+f[k,j]; 中间值要放在外层循环

7. 小技巧
div 2 的时间长于 shr 1 i:=i+1 的时间长于 inc(i) i:=i-1 的时间长于 dec(i) longint 比 integer 快

8. SPFA 求单元最短路=>链接
注意事项: [1]Next[i]代表在边集数组中下标为 i 的边的同起点的边在边集数组中的下标 [2]Dian[i]代表起点为 i 的边在边集数组中的下标 [3]无向边要分为两个有向边

9. move 函数的用法(速度是循环的 10 倍以上)[考试时最好不要使用]
Move[a[i],b[j],sizeof(类型)*k]代表从 a 数组第 i 位到第 i+k-1 位的部分赋值给 b 数组第 j 位到第 j+k-1 位

10. nlogn 的最长上升(下降)子序列=>链接
Shu[i]代表数列的第 i 位 F[i]代表以第 i 项结尾的最长上升子序列的长度 G[k]代表长度为 k 的最长上升子序列的最小值(G[k]=min(shu[i]) Len 为 G 数组的尾指针 主要步骤: [1]当 shu[i]>g[len]那么尾指针后移 1 位,g[len]:=shu[i]

i 满足 f[i]=k)

By zk

NOIP2009 集训小资料
[2]当 shu[i]<=g[len]那么在[0,len]这个区间二分查找 shu[i]在[x,y]中则 f[i]:=y 并更新 g[y]:=i

11. 字母树的建立=>链接
Tree[i,ch]代表父亲节点为 i 的点,本身字母为 ch 的点的编号 ge 为除根节点外节点个数 可用于找公共前缀

12. 各类背包问题的分析=>链接
W 为费用 T 为价值 [1]0/1 背包 For i:= 1 to n do For j:=v downto 1 do If f[j]<f[i-w[i]]+t[i] then f[j]:=f[i-w[i]]+t[i] [2]完全背包 For i:= 1 to n do For j:= 1 to v do If f[j]<f[i-w[i]]+t[i] then f[j]:=f[i-w[i]]+t[i] [3]多重背包:将 n[i]个物品拆成 n[i]个后再进行 0/1 背包 [4]分组背包 For i:= 1 to n do For j:=v downto 1 do For k:= 1 to z do If f[j]<f[i-w[k][i]]+t[k][i] then f[j]:=f[i-w[k][i]]+t[k][i]

13. 最长上升公共子序列=>链接
F[i]代表 b 序列尾位为 i 时的最长长度 F[i]=max(f[i`])+1 i`<i

14. 树的 3 种遍历的顺序:
先序遍历顺序:根节点—左子树—右子树 中序遍历顺序:左子树—根节点—右子树 后序遍历顺序:左子树—右子树—根节点

15. 循环小数转为分数=>链接
0.[ a ][ a ][ a ] [ a ]…… = X位

[a] 99999......9999
X位

By zk

NOIP2009 集训小资料
0.[ b ][ a ][ a ][ a ] [ a ]……=

[a] [b] + 99...99000...000 100....00
X个9 Y个0 Y个0

Y位 X位 注:[ a ]表示循环节

16. 字典序法求下一个排列=>链接
主要步骤: [1]从右往左找到第一个比右边的数小的数的编号 j [2]在[j+1,n]中找到比 a[j]大最小的数编号为 k [3]交换 j 和 k 位置上的数 [4]将区间[j+1,n]中的数倒转

17. 全排列的项数与排列的转换
求排列在全排列中的项数(康托展开): F[i]表示排列中的第 i 位(从右往左)的右边有多少个数比比它小 项数=

∑ F[i] × (i 1)!
i =1

n

求全排列的第 i 项得排列 把 i 变为阶乘进制数 if f[i]>=I then begin f[i+1]:=f[i+1]+f[i] div I; f[i]:=f[i] mod I; end; 即 I = f [n] × (n 1)!+ f [n 1] × (n 2)!+...... + f [2] × 1!+ f [1] × 0! 第 j 位为剩下的数中第 f[j]+1 小的数,然后依次还原排列

18. 随机一个顺序
时间复杂度 O(n) 枚举每一个点与随机到的位置交换

19. 最小区间覆盖问题=>2008 年周小博论文
描述:有 n 个区间,选择尽量少的区间,使得这些区间完全覆盖某线段[s,t] 算法: [1]按左端点坐标排序 [2]每次选择覆盖点 s 的区间中右端点坐标最大的一个,并更新 s [3]直到所选区间已包含 t

20. 无向图中第 K 短路的求法=>链接
二分 K 短路的长度 每次求出长度小于等于二分长度的路径条数 条数大于等于 K 时右边界左移 条数小于 K 时左边界右移 直到左右边界相差 1,k 为 1 时输出 x;否则输出 y

21. Fibonacci 数列
By zk

NOIP2009 集训小资料
递推公式:f[i]=f[i-1]+f[i-2] 通项公式: F[n] =

5 1+ 5 1 5 )^ n ( )^ n ( 5 2 2

22. 关键路径
算法步骤: [1]添加一个起点和终点,求出 AOE 网中的拓扑序列,若有环工程无法开始。 [2]起点的最早发生时间为 0,按拓扑序列的顺序求出其他节点的最早发生时间(父节点 的最早发生时间为子节点中最早发生时间加上到父节点的权值最大的一个)。 [3]终点的最早发生时间等于最晚发生时间,按拓扑逆序列求出其他节点的最晚发生时 间(子节点的最晚发生时间为父节点的最晚发生时间减去子节点到父亲的时间)。 [4]如果节点的最早发生时间等于最晚发生时间则该工程为关键工程。 [5]依次连接关键工程即为关键路径。

23. 中缀转后缀
算法步骤: [1]判断式子是否被括号所包裹,有则去除。 [2]在式子中找到一个不在括号中的最靠后的加减号。 [3]在式子中找到一个不在括号中的最靠后的乘除号。 [4]如果存在加减号则取加减否则取乘除 [5]左右进行递归处理。

24. 后缀转中缀
算法步骤: [1]依次将式子中的字符入栈,如果发现符号则将栈顶的元素变为字符的右儿子,次栈 顶元素变为左儿子,栈顶指针减 2。 [2]输出时先输出左子树,然后输出本身,再输出右子树,注意添加括号。 [3]子树递归处理。

25. 最小生成树 Kruskal
算法步骤: [1]将边按长度从小到大排序 [2]每次取出最小的边,若不会构成环则加入树中,用并查集将两端点合并

By zk


相关文章:
NOIP2010集训小资料.doc
NOIP2010集训小资料 - NOIP 集训小资料 NOIP 集训小资料 目录
NOIP2010复习资料大全.doc
NOIP2010复习资料大全 - NOIP 图论相关内容 1. 图的存储 相邻矩
Noip考前冲刺-考试练习.ppt
冲刺NOIP2010模拟试题五 4页 免费 NOIP2010集训小资料 13页
NOIP2010复习资料大全(优化版).pdf
NOIP2010集训小资料 13页 免费 noip备战模拟题(有解答) 13页
NOIP2010第十六届初赛试题及答案资料.doc
NOIP2010第十六届初赛试题及答案资料_幼儿读物_幼儿教育_教育专区。NOIP2010 ...[i] := LEFT 本小题中,LEFT 可用 true 代替,LEFT_TO_RIGHT 可用 true ...
2010NOIP模拟测试与题解.doc
7页 免费 NOIP2010集训小资料 13页 免费如要投诉违规内容,请到百度文
NOIPnoi信息学奥赛习题NOIP.ppt
80页 免费 (信息学奥赛辅导)程序设计... 51页 免费 信息学奥赛题库 79页 1财富值 信息学奥赛培训 50页 免费 NOIP2010集训小资料 13页 免费如...
noip2010 初赛集训一.ppt
NOIP2010考前训练题1 3页 2财富值 NOIP2010集训小资料 13页
NOIP2010考前训练题1.doc
NOIP2010考前训练题1_理学_高等教育_教育专区。noip冲刺 信息学竞赛试题 信息学...NOIP2010集训小资料 13页 2下载券 NOIP2010第十六届初赛试... 12页 免费 ...
NOIP2010题解_图文.ppt
NOIP2010题解 - NOIP2010提高组 NOIP2010提高组 题目分
NOIP2010junior.pdf
NOIP2010junior - 全国信息学奥林匹克联赛(NOIP2010)复赛 普及组 全国信息学奥林匹克联赛(NOIP2010)复赛 普及组 (请选手务必仔细阅读本页内容) 一.题目概...
NOIP2010提高组解题报告.doc
NOIP2010提高组解题报告 - 1:机器翻译 var m,n,i,j,k,p
NOIP2010提高组解题报告.doc
NOIP2010提高组解题报告_IT/计算机_专业资料。提高组解题报告 NOIP2010 提高组解题报告 首先对这次比赛 做一个总体分析。第一题我觉得没什么好说的,作为一道简单 ...
NOIP2010普及组.pdf
NOIP2010普及组 - 全国信息学奥林匹克联赛(NOIP2011)复赛 普及
Noip2010提高组试题.doc
Noip2010提高组试题 - 全国信息学奥林匹克联赛(NOIP2010)复赛 提高组 全国信息学奥林匹克联赛(NOIP2010)复赛 提高组 (请选手务必仔细阅读本页内容) 一.题目概况...
NOIP2010 题解.doc
NOIP2010 题解_计算机软件及应用_IT/计算机_专业资料。1. #include <stdio.h...NOIP2010集训小资料 13页 2下载券 noip2010提高组解题报告 11页 免费 ...
NOIP2010第十六届初赛试题及答案.doc
NOIP2010第十六届初赛试题及答案_学科竞赛_初中教育_教育专区。2010
noip2010提高组解题报告.doc
这个最小 值是多 全国信息学奥林匹克联赛(NOIP2010)复赛 提高组 第 5
NOIP2010提高组试题.doc
NOIP2010提高组试题 - 全国信息学奥林匹克联赛(NOIP2010)复赛 提高组 全国信息学奥林匹克联赛(NOIP2010)复赛 提高组 (请选手务必仔细阅读本页内容) 一.题目概况...
NOIP2010解题报告.doc
NOIP2010解题报告 - NOIP2010 解题报告 天津市南开中学 钱桥
更多相关标签: