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

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复习资料
NOIP2010集训小资料 13页 免费 NOIP题目方向 6页 免费 NOIP实用算法 33页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行...
noip2010提高组解题报告
这个最小 值是多 全国信息学奥林匹克联赛(NOIP2010)复赛 提高组 第 5 页共 7 页少? 【输入】 输入文件名为 prison.in。输入文件的每行中两个数之间用一...
noip2010热身赛
NOIP2010训练 38页 1财富值 NOIP2010复赛通知 3页 免费喜欢此文档的还喜欢 NOIP2010模拟赛2 5页 免费 NOIP2010集训小资料 13页 免费 noip2010模拟赛 9页 1财...
2010NOIP必备代码
2010noip复赛 9页 免费 NOIP2010集训小资料 13页 1下载券 基础代码汇总整理 for...一,基本算法 1,最小公倍数 int lcm(int a,int b) { int i; if(a0)...
2010NOIP模拟测试与题解
7页 免费 NOIP2010集训小资料 13页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
备战NOIP2010复赛经验总结分享
NOIP2010集训小资料 13页 免费 历年NOIP(普及组提高组)试... 2页 免费 NOIP复习心得 2页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建...
2010noip提高组解题报告
百度文库 专业资料 IT/计算机上传文档支持以下设备:...2010noip提高组解题报告 带pascal源程序2010noip提高组...这样先排序,从大到小往里添加边,每次判断是否有...
NOIP2010初赛练习(1)
NOIP2010考前训练题1 3页 2财富值 NOIP2010初赛练习...NOIP初赛复习 69页 免费 NOIP初赛资料——栈 67页...最小的数是( ) A.(11011001)2 B.(75)10 C....
NOIP2010提高组
百度文库 专业资料 IT/计算机上传文档支持以下设备:...NOIP2010 提高组(部分)试题 提高组(部分)单项选择题...CPU 所访问的存储单元通常都趋于聚集在一个较小的连续...
NOIP2010初赛练习(2)
NOIP2010初赛练习(3) 6页 1财富值 NOIP2010训练 ...NOIP复赛冲刺资料集锦10 45页 免费 NOIP实用算法 33...一个高度为 h 的二叉树最小元素数目是( A) 2h...
更多相关标签: