当前位置:首页 >> 学科竞赛 >> NOIP算法整理

NOIP算法整理


前言
离 NOIP 还有一个星期,匆忙的把寒假整理的算法补充完善,看 着当时的整理觉得那时还年少。第二页贴了几张从贴吧里找来的图 片,看着就很热血的。旁边的同学都劝我不要再放 PASCAL 啊什么 的了, 毕竟我们的下一级直接学 C++。 即便我本人对 C++也是赞赏有 加,不过 PASCAL 作为梦的开始终究不能忘记。不像机房中其余的 OIERS,我以后并不想学计算机

类的专业。当年来学这个竞赛就是为 了兴趣,感受计算机之美的。经过时迁,计划赶不上变化,现在尚处 于迷茫之中,也很难说当时做的决定是对是错。然而我一直坚信迷茫 的时候选择难走的路会看见更好的风景。 这篇文章简单的说了一下 NOIP 考试中会常用的算法,可能难度 掌握的不是太好,有一部分内容不是 NOIP 考查范围,然而随着难度 的增加,看一些更高级的算法也没有坏处。还有一些非常非常基础的 比如链表啊什么的就直接没有写上 (别问我为什么整理了那么多的排 序算法) 。 最后祝大家在 NOIP 中取得理想的成绩!

NOIP 算法总结

1

山东省广饶一中 杨庆礼

NOIP 算法总结

2

山东省广饶一中 杨庆礼

目录 搜索 .............................................................................................. 6
DFS............................................................................................................................................. 6 框架................................................................................................................................... 6 优化................................................................................................................................... 6 BFS............................................................................................................................................. 6 框架................................................................................................................................... 6 优化................................................................................................................................... 7

排序 .............................................................................................. 7
冒泡排序................................................................................................................................... 7 选择排序................................................................................................................................... 7 插入排序................................................................................................................................... 8 桶排序....................................................................................................................................... 8 快速排序................................................................................................................................... 9 堆排序....................................................................................................................................... 9

数学定理.................................................................................... 10
中国剩余定理......................................................................................................................... 10 康托展开................................................................................................................................. 11 错排通项................................................................................................................................. 11 费马大定理............................................................................................................................. 11 费马小定理............................................................................................................................. 11 逆元................................................................................................................................. 11 欧拉函数......................................................................................................................... 12 Stirling 数 ................................................................................................................................ 12 Stirling's approximation .......................................................................................................... 12

数论 ............................................................................................ 13
GCD&LCM ............................................................................................................................ 13 素数......................................................................................................................................... 13 快速幂..................................................................................................................................... 14 模运算法则............................................................................................................................. 15 组合和全排列......................................................................................................................... 15 阶乘......................................................................................................................................... 15 约瑟夫环问题......................................................................................................................... 15 Catalan 数 ............................................................................................................................... 16 扩展欧几里德算法................................................................................................................. 17 对自然数因子的计算............................................................................................................. 17 矩阵乘法................................................................................................................................. 18 位运算..................................................................................................................................... 18

动态规划.................................................................................... 20
NOIP 算法总结 3 山东省广饶一中 杨庆礼

特征......................................................................................................................................... 20 步骤......................................................................................................................................... 21 关键......................................................................................................................................... 21 格式......................................................................................................................................... 21 推荐参考资料......................................................................................................................... 21 推荐习题................................................................................................................................. 22

图论算法.................................................................................... 22
回路问题................................................................................................................................. 22 Euler 回路 ...................................................................................................................... 22 Hamilton 回路 ................................................................................................................ 22 一笔画问题............................................................................................................................. 22 图的遍历................................................................................................................................. 25 DFS................................................................................................................................. 25 BFS ................................................................................................................................. 25 最短路径................................................................................................................................. 27 dijkstra 算法 ................................................................................................................... 27 floyd 算法 ....................................................................................................................... 28 spfa 算法 ........................................................................................................................ 29 最小生成树............................................................................................................................. 32 prim 算法 ........................................................................................................................ 32 Kruskal 算法 .................................................................................................................. 33 topology 排序 ......................................................................................................................... 35 关键路径................................................................................................................................. 36 利用拓扑排序................................................................................................................. 36 按照概念......................................................................................................................... 37 次短路..................................................................................................................................... 39 次小生成树............................................................................................................................. 39 匈牙利算法............................................................................................................................. 39

博弈 ............................................................................................ 40
取对称状态............................................................................................................................. 40 取 NIM 值 ............................................................................................................................... 41

分治 ............................................................................................ 42 回溯 ............................................................................................ 43
N 皇后..................................................................................................................................... 43 Hanoi Tower ............................................................................................................................ 44

高精度计算................................................................................ 44
高精度加法............................................................................................................................. 44 高精度减法............................................................................................................................. 45 高精度乘法............................................................................................................................. 47
NOIP 算法总结 4 山东省广饶一中 杨庆礼

高精度除法............................................................................................................................. 48 高精度阶乘............................................................................................................................. 50

高级数据结构 ........................................................................... 51
二叉树..................................................................................................................................... 51 并查集..................................................................................................................................... 54 树状数组................................................................................................................................. 54 线段树..................................................................................................................................... 55 二叉搜索树............................................................................................................................. 57

进制转换.................................................................................... 61
1.将 m 进制数 n 转化成一个十进制数 ................................................................................ 61 2.将十进制数 n 转换成 m 进制数......................................................................................... 62

后记 ............................................................................................ 63

NOIP 算法总结

5

山东省广饶一中 杨庆礼

搜索

DFS

框架
procedure dfs(x); var begin if 达到目标状态 then 输出结果并退出过程; if 满足剪枝条件 then exit; for i:=1 to 搜索宽度 do begin 备份现场;(注意如果现场使用了全局变量,则需要使用局部变量备份) dfs(参数+增量); 恢复现场; end;

优化 (1) 最优化剪枝:求最优值时,当前的状态无论如何不可能比最优值更优,则退 出,可与展望结合剪枝 (2) 可行性剪枝:提前判断该状态是否能得到可行解,如不能则退出 (3) 记忆化搜索:对于已经搜索过的状态直接退出 (4) 改变搜索顺序:对于看起来希望更大的决策先进行搜索 (5) 优化搜索策略 (6) 预处理找到大体搜索翻译 (7) 改写成 IDA*算法 (8) 卡时(注意现在联赛中禁止使用 meml 掐时) BFS

框架
初始化;把初始布局存入 设首指针 head=0; repeat inc(head),取出队列首记录为当前被扩展结点; NOIP 算法总结 6 山东省广饶一中 杨庆礼 尾指针 tail:=1;

for i:=1 begin

to

规则数 do

{r 是规则编号}

if 新空格位置合法 then begin if 新布局与队列中原有记录不重复 tail 增 1,并把新布局存入队尾; if 达到目标 end; end; until head>=tail; {队列空} then 输出并退出;

优化 判重的优化:hash,二叉排序树 双向广搜或启发式搜索 改写成 A*算法 二分优化

排序

冒泡排序
var a:array[1..100] of longint;t,n,i,j:longint; procedure sort; begin for i:=1 to n-1 do{与每个数都进行比较} for j:=1 to n-i do if a[j]>a[j+1] then begin t:=a[j]; a[j]:=a[j+1]; a[j+1]:=t; end; end;

选择排序
var a:array[1..100] of longint;t,n,i,j:longint; NOIP 算法总结 7 山东省广饶一中 杨庆礼

procedure sort; begin for i:=1 to n-1 do for j:=1+i to n do{大数沉小数浮} if a[j]>a[i] then begin t:=a[j]; a[j]:=a[i]; a[i]:=t; end; end;

插入排序
var a:array[0..100] of longint;n,i,j,t:longint; procedure sort; begin for i:=2 to n do for j:=1 to (i-1) do begin if (a[i]<a[j]) then begin t:=a[j]; a[j]:=a[i]; a[i]:=t; end; end; end;

桶排序
var a,b:array[0..100] of longint;r,i,j,t,k,n:longint; procedure sort; begin for i:=0 to 100 do b[i]:=0;{为 B 数组清零,小桶内容清零} for i:=1 to n do b[a[i]]:=b[a[i]]+1; {桶的序号就是那个要排序的东西;出现一次,桶里得旗数加一} for i:=0 to 100 do{扫描所有的桶} begin if b[i]<>0 then{桶里有旗} for j:=1 to b[i] do write(i,' ');{桶的序号就是那个数} end; end;

NOIP 算法总结

8

山东省广饶一中 杨庆礼

快速排序
var a:array[1..100] of longint; n,i,h,g:longint; procedure kp(l,r:longint);{变量不能与全局变量相同,否则会被抹去} var b,m,i,j,t:longint; begin i:=l; j:=r; m:=a[(l+r) div 2];{基准数最好从中间取} repeat while a[j]>m do dec(j); while a[i]<m do inc(i);{两侧的哨兵移动} if i<=j then {哨兵未碰面}{“=”利用 repeat 循环的性质,使 repeat 循环得以结束} begin t:=a[j]; a[j]:=a[i a[i]:=t;{交换两个哨兵的值} inc(j); dec(j);{哨兵继续运动} end; until i>j; if j>l then kp(l,j); if i<r then kp(i,r);{都是循环不结束后进行的动作} end; begin read(n); for i:=1 to n do read(a[i]); kp(1,n); {“一”位置与“N”位置} for i:=1 to n-1 do write(a[i],' '); write(a[n]);{防止多输出空格使程序结果出错} end.

堆排序
var a:array[1..100] of longint; n,i,b:longint; procedure jianshu(i:longint); begin while ((a[i]>a[i*2])or(a[i]>a[i*2+1]))and(i<=n div 2) do {当父亲数大于子女数时并且他有孩子时进行} begin

NOIP 算法总结

9

山东省广饶一中 杨庆礼

if a[i*2]<=a[i*2+1]{左儿子小于右儿子} then begin b:=a[i*2]; a[i*2]:=a[i];a[i]:=b;{左右儿子的值互换} jianshu(i*2);{继续为左儿子建树} end else begin b:=a[i*2+1];a[i*2+1]:=a[i];a[i]:=b; jianshu(i*2+1);{上同,不过是为右儿子建树} end; end; end; procedure tiao; begin while n<>0 do begin write(a[1]); a[1]:=a[n]; n:=n-1; for i:=(n div 2) downto 1 do jianshu(i); end; end; begin read(n); for i:=1 to n do read(a[i]); for i:=(n div 2) downto 1 do jianshu(i); tiao; end.

数学定理

中国剩余定理 若有一些两两互质的整数 m1, m2,? mn,则对任意的整数:a1,a2,...an,以下联立同余方 程组对模数 m1, m2,? mn 有公解:

NOIP 算法总结

10

山东省广饶一中 杨庆礼

康托展开 a[i]为当前未出现的元素中是排在第几个(从 0 开始) 把一个整数 X 展开成如下形式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[2]*1!+a[1]*0! 其中 a[i]为当前未出现的元素中是排在第几个 (从 0 开始) , 并且 0<=a[i]<i(1<=i<=n) 错排通项 考虑一个有 n 个元素的排列, 若一个排列中所有的元素都不在自己原来的位置上, 那么 这样的排列就称为原排列的一个错排。 f[1]=0;f[2]=1; f[n] =(n-1)(f[n-2) + f[n-1]) f[n]:=n![1-1/1!+1/2!-1/3!??+(-1)^n*1/n!] f[n] = (n!/e+0.5),其中 e 是自然对数的底,[x]为 x 的整数部分。 费马大定理 ? ? 费马大定理,又被称为“费马最后的定理”,由法国数学家费马提出。它断言当整 数 n >2 时,关于 x, y, z 的方程 xn + yn = zn 没有正整数解。 被提出后,经历多人猜想辩证,历经三百多年的历史,最终在 1995 年被英国数学家 安德鲁·怀尔斯证明。

费马小定理 假如 a 是一个整数,p 是一个素数,那么 ap ≡a (mod p)。 如果 a 不是 p 的倍数,这个定理也可以写成 ap-1 ≡1 (mod p)。----这个更加常用 逆元 由费马小定理:假如 p 是质数,且 gcd(a,p)=1,那么 ap-1≡1(mod p) 逆元:如果 ab≡1(mod p) ,那么在模 p 意义下,a、b 互为逆元。 所以,假如 p 是质数,且 gcd(a,p)=1,那么 a 的逆元是 ap-2 逆元的作用:在模意义下进行除法。乘 a 的逆元等同于除以 a。

NOIP 算法总结

11

山东省广饶一中 杨庆礼

欧拉函数 在数论中,对正整数 n,欧拉函数是小于或等于 n 的正整数中与 n 互质的数的数目。此函数 以其首名研究者欧拉命名,它又称为φ 函数、欧拉商数等。 若 m,a 为正整数,且 m,a 互素,(gcd(a,m) = 1),则 aφ (m)≡1,其中为φ (m)欧拉函数, mod m 为同余关系。 欧拉定理实际上是费马小定理的推广。 Stirling 数 第一类 s(p,k)的一个的组合学解释是:将 p 个物体排成 k 个非空循环排列的方法数。 s(p,k)的递推公式: s(p,k)=(p-1)*s(p-1,k)+s(p-1,k-1) ,1<=k<=p-1 边界条件:s(p,0)=0 ,p>=1 s(p,p)=1 ,p>=0 递推关系的说明: 考虑第 p 个物品,p 可以单独构成一个非空循环排列,这样前 p-1 种物品构成 k-1 个非 空循环排列,方法数为 s(p-1,k-1); 也可以前 p-1 种物品构成 k 个非空循环排列, 而第 p 个物品插入第 i 个物品的左边, 这 有(p-1)*s(p-1,k)种方法。 第二类 S(p,k)的一个组合学解释是:将 p 个物体划分成 k 个非空的不可辨别的(可以理解 为盒子没有编号)集合的方法数。 k!S(p,k)是把 p 个人分进 k 间有差别(如:被标有房号)的房间(无空房)的方法数。 S(p,k)的递推公式是:S(p,k)=k*S(p-1,k)+S(p-1,k-1) 边界条件:S(p,p)=1 ,p>=0 S(p,0)=0 ,p>=1 ,1<= k<=p-1

递推关系的说明: 考虑第 p 个物品,p 可以单独构成一个非空集合,此时前 p-1 个物品构成 k-1 个非空的不可 辨别的集合,方法数为 S(p-1,k-1); 也可以前 p-1 种物品构成 k 个非空的不可辨别的集合, 第 p 个物品放入任意一个中, 这样有 k*S(p-1,k)种方法。 PS:第一类斯特林数和第二类斯特林数有相同的初始条件,但递推关系不同。 Stirling's approximation 快速求阶乘,不推荐用于竞赛。

更加精确的近似公式为:

NOIP 算法总结

12

山东省广饶一中 杨庆礼

其中:
?

.

数论

GCD&LCM
//GCD function gcd(a,b:longint):longint; begin if b=0 then gcd:=a else gcd:=gcd (b,a mod b); end ;

//LCM function lcm(a,b:longint):longint; begin if a<b then swap(a,b); lcm:=a; while lcm mod b>0 do inc(lcm,a); end;

素数
//单个判断 function prime (n: longint): boolean; var i longint; begin for i:=2 to trunc(sqrt(n)) do if n mod i=0 then exit(false) exit(true); NOIP 算法总结 13 山东省广饶一中 杨庆礼

end;

//筛法打表 procedure main; var i,j:longint; begin fillchar(f,sizeof(f),true); f[0]:=false;f[1]:=false; for i:=2 to trunc(sqrt(maxn)) do if f[i] then begin j:=2*i; while j<= begin f[j]:=false; inc(j,i); end; end; end; maxn do

快速幂

X

n

2 ? (n为偶数) (X n / 2) ? ? n ?1 ? X (n为奇数) ?X

{a^b mod n} function f(a,b,n:int64):int64; var t,y:int64; begin t:=1; y:=a; while b<>0 do begin if(b and 1)=1 then t:=t*y mod n; NOIP 算法总结 14 山东省广饶一中 杨庆礼

y:=y*y mod n; {这里用了一个很强大的技巧,y*y 即求出了 a^(2^(i-1))不知道这是什么的看原理} b:=b shr 1;{去掉已经处理过的一位} end; exit(t); end;

模运算法则 (A+B) mod C = (A mod C (A-B) mod C = (A mod C (A * B) mod C = (A mod (A / B) mod C = ??? 结合律 ((a+b) mod p + c)mod p ((a*b) mod p * c)mod p 分配律 ((a +b)mod p × c) mod 组合和全排列 排列 A(n,m)(m 是上标)=n!/(n-m)!=nx(n-1)x...xm 组合 C(n,m)=n!/m!(n-m)!=[nx(n-1)x...xm]/m! 阶乘
function fac(n1:longint):longint; var j,k:longint; begin k:=1; for j:=1 to n do k:=k*j; fac:=k; end;

+ B mod C) mod C - B mod C) mod C C) * (B mod C) mod C

= (a + (b+c) mod p) mod p = (a * (b*c) mod p) mod p p = ((a × c) mod p + (b × c) mod p) mod p

约瑟夫环问题 递 推 公 式 , 设 有 n 个 人 ( 0,...,n-1 ), 数 m , 则 第 i 轮 出 局 的 人 为 f(i)=(f(i-1)+m-1)%(n-i+1),f(0)=0;
NOIP 算法总结 15 山东省广饶一中 杨庆礼

例:有 M 个猴子围成一圈,每个有一个编号,编号从 1 到 M。打算从中选出一个大王。经过 协商,决定选大王的规则如下:从第一个开始,每隔 N 个,数到的猴子出圈,最后剩下来的 就是大王。要求:从键盘输入 M,N,编程计算哪一个编号的猴子成为大王。
var a:array[1..1000] of longint; m,n,i,j,sum:longint; weizhi:longint=0; begin readln(m,n); for i:=1 to m do a[i]:=i; sum:=m; repeat weizhi:=weizhi+1; if weizhi>m then weizhi:=weizhi-m; if a[weizhi]<>0 then begin j:=j+1; if j=n then begin a[weizhi]:=0; j:=0; sum:=sum-1; end; end; until sum=1; for i:=1 to m do if a[i]<>0 then write(a[i]); end.

Catalan 数 h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2)
h[0]:=1; h[1]:=1; for i:=2 to n do begin j:=i-1; k:=0; while k<>i do begin h[i]:=h[i]+h[k]*h[j]; dec(j); NOIP 算法总结 16 山东省广饶一中 杨庆礼

inc(k); end; end;

1. 2. 3. 4. 5.

矩阵连乘: P=a1×a2×a3×??×an,依据乘法结合律,不改变其顺序,只用 括号表示成对的乘积,试问有几种括号化的方案?(h(n-1)种) 一个栈(无穷大)的进栈序列为 1,2,3,?,n,有多少个不同的出栈序列。 对于一个二进制的 01 串,共 n+m 位,满足 n 个 1,m 个 0,且 0<=n-m<=1, 该串还满足从左向右 1 的个数永远大于 0 的个数。问共有多少种排列方式。 在一个凸多边形中,通过若干条互不相交的对角线,把这个多边形划分成了 若干个三角形。求不同划分的方案数。 给定 N 个节点,能构成多少种不同的二叉树?

扩展欧几里德算法 若存在一组解 x0,y0,满足 b*x0+(a mod b)*y0=d 则取 x=y0,y=x0-(a div b)*y0,有 ax+by=d 这样,我们可以用类似辗转相除的迭代法求解。
function extended-gcd(a, b:longint; var x, y:integer); var x1, y1 :integer; begin if b=0 then begin extended-gcd:=a; x:=1; y:=0 end else begin extended-gcd:=extended-gcd(b, a mod b, x1, y1); x:=y1; y:=x1-(a div b)*y1; end; end;

对自然数因子的计算 怎样求一个数有多少个因数? 对于一个已知的自然数,要求出它有多少个因数,可用下列方法: 首先将这个已知数分解质因数, 将此数化成几个质数幂的连乘形式, 然后把这些质数的 指数分别加一,再相乘,求出来的积就是我们要的结果。 例如:求 360 有多少个因数。 因为 360 分解质因数可表示为:360=2^3×3^2×5,2、3、5的指数分别是3、2、 1,这样360的因数个数可这样计算出: (3+1) (2+1) (1+1)=24个。 怎样求有 n 个因数的最小自然数? 同样拥有 n 个(n 为确定的数)因数的自然数可以有多个不同的数,如何求出这些数中的最 小数? 这是与上一个问题相反的要求,是上一题的逆运算。 比如求有24个因数的最小数是多少?
NOIP 算法总结 17 山东省广饶一中 杨庆礼

根据上一问题解决过程的启示,可以这样做,先将24分解因式,把24表示成几个数 连乘积的形式,再把这几个数各减去1,作为质数2、3、5、7......的指数,求出这些 带指数的数连乘积,试算出最小数即可。具体做法是: 因为:24=4×6, 24=3×8, 24=4×3×2, 现在分别以这三种表示法试求出目标数 x: (1) 、24=4×6,4-1=3,6-1=5 X=2^5×3^3=864 (2) 、24=3×8,3-1=2,8-1=7 X=2^7×3^2=1152 (3)24=4×3×2,4-1=3, 3-1=2, 2-1=1 X=2^3×3^2×5=360 综合(1)、(2)、(3)可知360是有24个因数的最小数。 矩阵乘法

矩阵乘法有下列三要素: (1)可乘原则:前列数 = 后行数 (2)乘积阶数:前行数 × 后列数 (3)Cij 乘积元素:= 前矩阵的第 i 行元素与后矩阵的第 j 列对应元素的乘积之和 矩阵乘法求斐波那契数列的原理: f(n) 是第 n 项的值。 f(1)= 1; f(2) =1; f(n)= f(n-1) + (n-2) 分两步推导:

位运算 Pascal 和 C 中的位运算符号 下面的 a 和 b 都是整数类型,则: C 语言 | Pascal 语言 ——-+————a & b | a and b a | b | a or b a ^ b | a xor b ~a | not a
NOIP 算法总结 18 山东省广饶一中 杨庆礼

a << b | a shl b a >> b | a shr b 注意 C 中的逻辑运算和位运算符号是不同的。520|1314=1834,但 520||1314=1, 因为逻辑运算时 520 和 1314 都相当于 True。同样的,!a 和~a 也是有区别的。 注意:在数学中 TRUE 对应一;FALSE 对应 0 常用位运算 === 1. and 运算 === and 运算通常用于二进制取位操作,例如一个数 and 1 的结果就是取二进制的最末位。 这可以用来判断一个整数的奇偶,二进制的最末位为 0 表示该数为偶数,最末位为 1 表示 该数为奇数. X and –X 返回的值是 X 第一个 1 出现的位数 === 2. or 运算 === or 运算通常用于二进制特定位上的无条件赋值,例如一个数 or 1 的结果就是把二进制最 末位强行变成 1。如果需要把二进制元元元元最末位变成 0,对这个数 or 1 之后再减一就可 以了,其实际意义就是把这个数强行变成最接近的偶数。 === 3. xor 运算 === xor 运算通常用于对二进制的特定一位进行取反操作,因为异或可以这样定义:0 和 1 异 或 0 都不变,异或 1 则取反。 xor 运算的逆运算是它本身,也就是说两次异或同一个数最后结果不变,即(a xor b) xor b = a。 === 4. not 运算 === not 运算的定义是把内存中的 0 和 1 全部取反。使用 not 运算时要格外小心,你需要注意 整数类型有没有符号。如果 not 的对象是无符号整数(不能表示负数) ,那么得到的值就是 它与该类型上界的差,因为无符号类型的数是用$0000 到$FFFF 依次表示的。 === 5. shl 运算 === a shl b 就表示把 a 转为二进制后左移 b 位(在后面添 b 个 0) 。例如 100 的二进制为 1100100,而 110010000 转成十进制是 400,那么 100 shl 2 = 400。可以看出,a shl b 的 值实际上就是 a 乘以 2 的 b 次方,因为在二进制数后添一个 0 就相当于该数乘以 2。 === 6. shr 运算 === 和 shl 相似,a shr b 表示二进制右移 b 位(去掉末 b 位) ,相当于 a 除以 2 的 b 次方(取 整) 。我们也经常用 shr 1 来代替 div 2,比如二分查找、堆的插入操作等等。想办法用 shr 代替除法运算可以使程序效率大大提高。最大公约数的二进制算法用除以 2 操作来代替慢 得出奇的 mod 运算,效率可以提高 60%。 常用位运算详细示例 功能 | 示例 | 位运算 ———————-+—————————+——————– 去掉最后一位 | (101101->10110) | x shr 1 在最后加一个 0 | (101101->1011010) | x shl 1 在最后加一个 1 | (101101->1011011) | x shl 1+1 把最后一位变成 1 | (101100->101101) | x or 1 把最后一位变成 0 | (101101->101100) | x or 1-1 最后一位取反 | (101101->101100) | x xor 1
NOIP 算法总结 19 山东省广饶一中 杨庆礼

把右数第 k 位变成 1 | (101001->101101,k=3) | x or (1 shl (k-1)) 把右数第 k 位变成 0 | (101101->101001,k=3) | x and not (1 shl (k-1)) 右数第 k 位取反 | (101001->101101,k=3) | x xor (1 shl (k-1)) 取末三位 | (1101101->101) | x and 7 取末 k 位 | (1101101->1101,k=5) | x and (1 shl k-1) 取右数第 k 位 | (1101101->1,k=4) | x shr (k-1) and 1 把末 k 位变成 1 | (101001->101111,k=4) | x or (1 shl k-1) 末 k 位取反 | (101001->100110,k=4) | x xor (1 shl k-1) 把右边连续的 1 变成 0 | (100101111->100100000) | x and (x+1) 把右起第一个 0 变成 1 | (100101111->100111111) | x or (x+1) 把右边连续的 0 变成 1 | (11011000->11011111) | x or (x-1) 取右边连续的 1 | (100101111->1111) | (x xor (x+1)) shr 1 去掉右起第一个 1 的左边 | (100101000->1000) | x and (x xor (x-1)) 补码 计算机用$0000 到$7FFF 依次表示 0 到 32767 的数,剩下的$8000 到$FFFF 依次表示-32768 到-1 的数。32 位有符号整数的储存方式也是类似的。稍加注意你会发现,二进制的第一位 是用来表示正负号的,0 表示正,1 表示负。这里有一个问题:0 本来既不是正数,也不是 负数,但它占用了$0000 的位置,因此有符号的整数类型范围中正数个数比负数少一个。对 一个有符号的数进行 not 运算后,最高位的变化将导致正负颠倒,并且数的绝对值会差 1。 也就是说,not a 实际上等于-a-1。这种整数储存方式叫做“补码”。

动态规划

PS: 鉴于网上有大量的专门讲述 DP 的文章, 这里不多做累赘的说明。 总而言之, DP 作为 NOIP 必考算法,熟练的掌握是极其必要的。 特征 1、最优子结构 如果问题的一个最优解中包含了子问题的最优解, 则该问题具有最优子结构。 也称最 优化原理。 最优子结构也可以理解为“整体最优则局部最优” 。反之不一定成立。 2、重叠子问题 在解决整个问题时,要先解决其子问题,要解决这些子问题,又要先解决他们的子子 问题 ??。而这些子子问题又不是相互独立的,有很多是重复的,这些重复的子子问题称 为重叠子问题。 动态规划算法正是利用了这种子问题的重叠性质, 对每一个子问题只解一次, 而后将 其解保存在一个表中,以后再遇到这些相同问题时直接查表就可以,而不需要再重复计算, 每次查表的时间为常数。 3.无后效性原则 已经求得的状态,不受未求状态的影响。
20

NOIP 算法总结

山东省广饶一中 杨庆礼

步骤 1、找出最优解的性质,并刻画其结构特征; 2、递归地定义最优值(写出动态规划方程) ; 3、以自底向上的方式计算出最优值;记忆化搜索(树型) 、递推 4、根据计算最优值时得到的信息,构造一个最优解。 关键 状态转移方程的构造是动态规划过程中最重要的一步,也是最难的一步.对于大多数的 动态规划,寻找状态转移方程有一条十分高效的通道,就是寻找变化中的不变量 (已经求得的 值).定量处理的过程也就是决策实施的过程. 格式 动态规划的一般倒推格式为:
f[Un]=初始值; for k←n-1 downto 1 do for U 取遍所有状态 do for X 取遍所有决策 do //枚举阶段 //枚举状态 //枚举决策

f[Uk]=opt{f[Uk+1]+L[Uk,Xk]};

L[Uk,Xk]:状态 Uk 通过策略 Xk 到达状态 Uk+1 的费用 输出:f[U1]:目标

动态规划的一般顺推格式为:
f[U1]=初始值; for k←2 to n do for U 取遍所有状态 do for X 取遍所有决策 do f[Uk]=opt{f[Uk-1]+L[Uk-1,Xk-1]}; //枚举每一个阶段

L[Uk-1,Xk-1]: 状态 Uk-1 通过策略 Xk-1 到达状态 Uk 的费用 输出:f[Un]:目标

推荐参考资料 刘永辉: 《通过金矿模型介绍动态规划》
NOIP 算法总结 21 山东省广饶一中 杨庆礼

dd_engi:《背包九讲》 ncepu: 《动态规划_从新手到专家》 董的博客: 《背包问题应用》 知乎问题:什么是动态规划?动态规划的意义是什么? 推荐习题 PS:以 CODEVS 为主要 OJ,POJ 上的 DP 题目早有人整理 背包型动态规划:1014,1068 序列型动态规划:1044,1576,3027 区间型动态规划:1048,1154,1166 棋盘性动态规划:1010,1169,1219,1220, 划分型动态规划:1017,1039,1040 树型动态规划:1163,1380

图论算法

回路问题 概念补充:奇点就是从这个点出发的线有奇数条的点。 Euler 回路 定义: 若图 G 中存在这样一条路径, 使得它恰通过 G 中每条边一次,则称该路径为欧拉路径。 若该路径是一个圈,则称为欧拉(Euler)回路。 充要条件:图连通且无奇点 Hamilton 回路 定义:经过图的每个顶点且仅一次的算法 充要条件:图连通且奇点数为 0 个或 2 个 一笔画问题 如何判断一个图形是否可以一笔不重地画出 ■⒈凡是由偶点组成的连通图,一定可以一笔画成。画时可以把任一偶点为起点,最后 一定能以这个点为终点画完此图。 ■⒉凡是只有两个奇点的连通图(其余都为偶点) ,一定可以一笔画成。画时必须把一 个奇点为起点,另一个奇点终点。 ■⒊其他情况的图都不能一笔画出。(奇点数除以二便可算出此图需几笔画成。)
NOIP 算法总结 22 山东省广饶一中 杨庆礼

Einstein 学起了画画, 此人比较懒~~,他希望用最少的笔画画出一张画。 。 。 给定一个无向图,包含 n 个顶点(编号 1~n),m 条边,求最少用多少笔可以画出图 中所有的边 解法:注意此题可能图不是联通的,所以需要用并查集预处理后完成
var n,m,i,u,v,sum1,sum2,mid:longint; b,f:array[0..1010] of longint; procedure intt; begin assign(input,'draw.in'); assign(output,'draw.out'); reset(input); rewrite(output); end; procedure outt; begin close(input); close(output); end; procedure sort(l,r: longint); var i,j,x,y: longint; begin i:=l; j:=r; x:=f[(l+r) div 2]; repeat while f[i]<x do inc(i); while x<f[j] do dec(j); if not(i>j) then begin y:=f[i]; f[i]:=f[j]; f[j]:=y; y:=b[i]; b[i]:=b[j]; b[j]:=y; inc(i); j:=j-1;

NOIP 算法总结

23

山东省广饶一中 杨庆礼

end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r); end; function root(x:longint):Longint; begin if f[x]=x then exit(x) else root:=root(f[x]); f[x]:=root; exit(root); end; begin intt; readln(n,m); for i:=1 to n do f[i]:=i; for i:=1 to m do begin read(u,v); if root(u)<>root(v) then f[root(u)]:=root(v); inc(b[u]); inc(b[v]); end; for i:=1 to n do mid:=root(i); sort(1,n); v:=n; while v>1 do begin while f[v-1]<>f[v] do dec(v); inc(sum2); mid:=f[v]; while f[v]=mid do begin if b[v] mod 2=1 then inc(sum1); dec(v); end; if sum1>0 then sum1:=sum1-2; sum2:=sum2+sum1 div 2; sum1:=0; end;

NOIP 算法总结

24

山东省广饶一中 杨庆礼

writeln((sum1 div 2)+sum2); outt; end.

图的遍历

DFS 遍历算法(递归过程) : 1)从某一初始出发点 i 开始访问: 输出该点编号;并对该点作被访问标志(以免被重复 访问) 。 2)再从 i 的其中一个未被访问的邻接点 j 作为初始点出发继续深搜。 (按序号从小到大的 顺序访问) 3)当 i 的所有邻接点都被访问完,则退回到 i 的父结点的另一个邻接点 k 再继续深搜。 直到全部结点访问完毕。
var a:array[1..100,1..100]of longint;p:array[1..100] of boolean;m,n,j:longint; procedure init; var i,x,y:longint; begin readln(n);readln(m); for i:=1 to m do begin read(x,y);a[x,y]:=1;a[y,x]:=1; end; end; procedure dfs(k:longint); var i:longint; begin write(k,' ');p[k]:=true; for i:=1 to m do if ((p[i]=false)and(a[k,i]=1)) then dfs(i);{k(i)是具体的点} end; begin fillchar(p,sizeof(p),false); init; dfs(1); end.

BFS 按层次遍历: 从图中某结点 i 出发, 在访问了 i 之后依次访问 i 的各个未曾访问的邻接点 (按序号由
NOIP 算法总结 25 山东省广饶一中 杨庆礼

小到大的顺序) , 然后分别从这些邻接点出发按广度优先搜索的顺序遍历图, 直至图中所有可被访问的结 点都被访问到。
var a:array[1..100] of longint; closed:longint=1; open:longint=0; t:array [1..100,1..100] of longint; p:array [1..100]of boolean; j,n,m,g:longint; procedure add(x:longint); begin inc(closed); a[closed]:=x; end; function del:longint; begin inc(open); del:=a[open]; end; procedure init; var i,x,y:longint; begin readln(n); readln(m); for i:=1 to m do begin read(x,y); t[x,y]:=1; t[y,x]:=1; end; end; procedure bfs(j:longint); var i,k:longint; begin a[1]:=(j); write(j,' '); p[j]:=true; while open<closed do begin inc(open); k:=a[open]; for i:=1 to n do if ((p[i]=false)and(t[k,i]=1)) then begin

NOIP 算法总结

26

山东省广饶一中 杨庆礼

write(i,' '); p[i]:=true; inc(closed); a[closed]:=i; end; end; end; begin for g:=1 to m do begin p[g]:=false; a[g]:=0; end; init; bfs(1); end.

最短路径

dijkstra 算法 ? 算法思想 设给定源点为 Vs,S 为已求得最短路径的终点集,开始时令 S={Vs} 。当求得第一条最短路 径(Vs ,Vi)后,S 为{Vs,Vi} 。根据以下结论可求下一条最短路径。 设下一条最短路径终点为 Vj ,则 Vj 只有: ◆ 源点到终点有直接的弧<Vs,Vj>; ◆ 从 Vs 出发到 Vj 的这条最短路径所经过的所有中间顶点必定在 S 中。 即只有这条最短路 径的最后一条弧才是从 S 内某个顶点连接到 S 外的顶点 Vj 。 若定义一个数组 dist[n], 其每个 dist[i]分量保存从 Vs 出发中间只经过集合 S 中的顶点而到达 Vi 的所有路径中长度最小的路径长度值, 则下一条最短路径的终点 Vj 必定 是不在 S 中且值最小的顶点,即: dist[i]=Min{ dist[k]| Vk∈V-S } 利用上述公式就可以依次找出下一条最短路径。 ? 示例程序
var a:array[1..100,1..100]of integer;//邻接矩阵 flag:array[1..100] of boolean;//已经找到最短路径的节点标志 path:array[1..100]of integer; w,x,n,i,j,min,minn,k:integer; begin readln(n,k); for i:=1 to n do//读取邻接矩阵,无路径写-1 begin for j:=1 to n do

NOIP 算法总结

27

山东省广饶一中 杨庆礼

begin read(a[i,j]); If a[i,j]=-1 then a[I,j]:=maxint; End; readln; end; fillchar(flag,sizeof(flag),false);//标明所有节点都未找到最短路径 flag[k]:=true; fillword(path,sizeof(path) div 2,k); path[k]:=0; minn:=k;//标记最小的点 for x:=2 to n do begin min:=32767;//标记要找下一个最短路径点的距离 for i:=1 to n do//找下一点点 if (a[k,i]<min) and (flag[i]=false) then begin min:=a[k,i]; minn:=i; end; flag[minn]:=true;//标记下一个点的找到 for j:=1 to n do //更新最短路径 if (j<>minn) and (a[k,minn]+a[minn,j]<a[k,j]) and (flag[j]=false) then begin a[k,j]:=a[k,minn]+a[minn,j]; path[j]:=minn; end; end; for for end. i:=1 to n do write(a[k,i],' ');//输出源点到各个点的距离 i:=1 to n do write(path[i],' ');//输出源点到各个点的距离 writeln; //源节点除外

floyd 算法 ? 算法思想 在原路径里增加一个新结点, 如果产生的新路径比原路径更小, 则用新路径值代替原路径的 值。这样依次产生 n 个矩阵(n 为网络结点数) (1) ( 2) (3) ( n) 用公式表示就是,对于 K=1,2,3?n,第 k 个矩阵 D , D , D ,?D
(k ) ( k ?1) ( k ?1) ( k ?1) dij ? min{ dij , dik ? dkj }

运算过程中 K 从 1 开始,而 i,j 则分别从 1 到 n 取遍所有值,然后 k 加 1,直到 k 等于 n 时停止。 ? 示例程序
var st,en,f:integer; NOIP 算法总结 28 山东省广饶一中 杨庆礼

k,n,i,j,x:integer; a:array[1..10,1..10] of integer;//邻接矩阵 path:array[1..10,1..10] of integer;//path[a,b]为 A 点到 B 点的最短路径要走的第一个点 begin readln(n);//读取节点数 for i:=1 to n do//读取邻接矩阵 begin for j:=1 to n do begin read(k); if k<>0 then a[i,j]:=k else a[i,j]:=maxint; path[i,j]:=j; end; readln; end; for x:=1 to n do//I,J 点之间加入 X 点,判断是否更短,并更新。 for i:=1 to n do for j:=1 to n do if a[i,j]>a[i,x]+a[x,j] then begin a[i,j]:=a[i,x]+a[x,j]; path[i,j]:=path[i,x]; end; readln(st,en);//读取开始结束点 writeln(a[st,en]);//写出开始结束长度 f:=st; while f<> en do//写出路径 begin write(f); write('-->'); f:=path[f,en]; end; writeln(en); end.

spfa 算法 ? 算法思想 2.1.SPFA 算法需要什么 SPFA 需要用到一个先进先出的队列 Q。 SPFA 需要对图中的所有顶点做一个标示,标示其是否在队列 Q 中。 2.2.SPFA 是怎样执行的 2.2.1 SPFA 的初始化
NOIP 算法总结 29 山东省广饶一中 杨庆礼

SPFA 的初始化和 Dijkstra 类似。 先把所有顶点的路径估计值初始化为代价最大值。比如:maxint。 所有顶点都标记为不在队列中。 起始顶点放入队列 Q 中。 起始顶点标记在队列中。 起始顶点的最短路径估计值置为最小值,比如 0。 然后下面是一个循环 2.2.2 SPFA 循环 循环结束的条件是队列 Q 为空。第一次进入循环的时候,只有起始顶点一个元素。 每次循环,弹出队列头部的一个顶点。 对这个顶点的所有出边进行松弛。 如果松弛成功, 就是出边终点上对应的那个顶点的路 径代价值被改变了,且这个被松弛的顶点不在队列 Q 中,就把这个被松弛的顶点入队 Q。注 意,这里顶点入队的条件有 2:1.松弛成功。2.且不在队列 Q 中。 当队列 Q 没有了元素。算法结束 ? 示例程序
const maxp=10000;{最大结点数} maxv=100000;{最大边数} var p,c,s,t:longint;{p,结点数;c,边数;s:起点;t:终点} a,b:array[1..maxp,0..maxp]of longint; {a[x,y]存 x,y 之间边的权;b[x,c]存与 x 相连的第 c 个边的另一个结点 y} d:array[1..maxp]of integer;{队列} v:array[1..maxp]of boolean;{是否入队的标记} // rn:array[1..maxp]of integer;{各个点的入队次数} dist:array[1..maxp]of longint;{到起点的最短路} head,tail:longint;{队首/队尾指针} procedure init; var i,x,y,z:longint; begin read(p,c); for i:=1 to c do begin readln(x,y,z); {x,y:一条边的两个结点;z:这条边的权值} inc(b[x,0]);b[x,b[x,0]]:=y;a[x,y]:=z; {b[x,0]:以 x 为一个结点的边的条数,b[x,a]:x 点连接的第 A 个节点} inc(b[y,0]);b[y,b[y,0]]:=x;a[y,x]:=z;{无向图的操作,取舍} end; readln(s,t); end; procedure spfa(s:longint); var i,j,now,sum:longint;

NOIP 算法总结

30

山东省广饶一中 杨庆礼

begin fillchar(d,sizeof(d),0); fillchar(v,sizeof(v),false); for j:=1 to p do dist[j]:=maxlongint; dist[s]:=0; v[s]:=true; d[1]:=s; // rn[s]:=1; {队列的初始状态,s 为起点} head:=1;tail:=1; while head<=tail do{队列不空,注意:此处 head>tial 未空} begin now:=d[head]; for i:=1 to b[now,0]do{now 指向的所有节点} if dist[b[now,i]]>dist[now]+a[now,b[now,i]]then {如果最短路径大于 now 节点的最短路径和 now 节点到该节点的路径之和} begin dist[b[now,i]]:=dist[now]+a[now,b[now,i]];{修改最短路} if not v[b[now,i]]then{扩展结点入队——如果此节点尚未入队,则入队,且表示} begin inc(tail); d[tail]:=b[now,i]; v[b[now,i]]:=true; // // inc(rn[b[now,i]]); if rn[b[now,i]]>c then begin writeln('fu huan');halt; end; end; end; v[now]:=false;{释放结点,一定要释放掉,因为这节点有可能下次用来松弛其它节点} inc(head); end; end; procedure print; begin writeln(dist[t]); end; begin init; spfa(s); print; end.

NOIP 算法总结

31

山东省广饶一中 杨庆礼

最小生成树

prim 算法 ? 算法思想 假设 N=(V,E)是连通网,TE 是 N 上最小生成树中边的集合。 1、算法实现:算法从 U={u0}(u0∈V),TE={}开始,重复执行下述操作: 在所有 u∈U,v∈V-U 的边(u,v)中找一条代价最小的边(u0 ,v0),将其并入集合 TE,同时 将 v0 并入 U 集合。 当 U=V 则结束,此时 TE 中必有 n-1 条边,则 T=(V,{TE})为 N 的最小生成树。时间复杂度 为 0(n2) 2、算法思想:普里姆算法构造最小生成树的过程是从一个顶点 U={u0}作初态,不断贪心寻 找与 U 中顶点相邻且代价最小的边的另一个顶点,扩充到 U 集合直至 U=V 为止。 ? 优化方法 我们很容易就可以发现 prim 算法的关键: 每次如何从生成树 T 到 T 外的所有边中, 找 出一条最小边。例如,在第 k 次前,生成树 T 中已有 k 个顶点和(k-1)条边,此时,T 到 T 外得所有边数为 k*(n-k),当然,包括没有边的两顶点,我们记权值为“无穷大”的边在 内,从如此多的边中查找最短边,时间复杂度为 O(k(n-k)),显然无法满足我们的期望。 我们来看 O(n-k)的方法:假定在进行第 k 次前已经保留着从 T 中到 T 外的每一个顶 点(共 n-k 个)的各一条最短边,在进行第 k 次时,首先从这(n-k)条最短边中,找出一 条最最短边(它就是从 T 到 T 外的最短边) ,假设为(vi,vj) ,此步需要进行(n-k)次比较; 然后把边(vi,vj)和顶点 vj 并入 T 中的边集 TE 和顶点集 U 中,此时,T 外只有 n-(k+1) 个顶点,对于其中的每个顶点 vt,若(vj,vt)边上的权值小于原来保存的从 T 中到 vt 的 最短边的权值,则用(v,vt)修改之,否则,保持原最小边不变。这样就把第 k 次后 T 中到 T 外的每一个顶点 vt 的各一条最短边都保留下来了,为第(k+1)次最好了准备。这样 Prim 的总时间复杂度为 O(n^2)。 ? 示例程序(优化后)
const max=1000; var map:array[1..MXN,1..MXN] of longint; cost:array[1..MXN] of longint; visit:array[1..MXN] of boolean; i,j,n,m,x,y,v:longint; function prim():longint; var i,j,min,mini,ans:longint; begin ans:=0; for i:=1 to n do begin visit[i]:=false;cost[i]:=maxlongint;end; //visit[i]是 i 点是否被访问的标志,cost[i]是到 i 点的最小权边。 for i:=2 to n do if map[1,i]<>0 then cost[i]:=map[1,i];visit[1]:=true;

NOIP 算法总结

32

山东省广饶一中 杨庆礼

for i:=1 to n-1 do begin min:=maxlongint; for j:=1 to n do if not visit[j] and (cost[j]<min) then begin min:=cost[j];mini:=j;end; visit[mini]:=true;inc(ans,min); for j:=1 to n do if not visit[j] and (map[mini,j]>0) and (map[mini,j]<cost[j]) then cost[j]:=map[mini,j]; //更新圈内圈外存储的最短距离 end; exit(ans); end; begin readln(n,m); for i:=1 to m do begin readln(x,y,v); if (map[x,y]=0) or (map[x,y]>v) then begin map[x,y]:=v;map[y,x]:=v; end; end; writeln(prim()); end.

Kruskal 算法 ? 算法思想 先构造一个只含 n 个顶点、 而边集为空的子图, 把子图中各个顶点看成各棵树上的根结 点,之后,从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树, 则将其加入子图,即把两棵树合成一棵树,反之,若该条边的两个顶点已落在同一棵树上, 则不可取,而应该取下一条权值最小的边再试之。依次类推,直到森林中只有一棵树,也即 子图中含有 n-1 条边为止。 时间复杂度为为 O(e^2), 使用并查集优化后复杂度为 O(eloge) ,与网中的边数有关, 适用于求边稀疏的网的最小生成树。 设图 G 的度为,G=(V,E),设该图的最小生成树为 T=(V,TE),设置边的集合 TE 的初始状 态为空集。将图 G 中的边按权值从小到大排好序,然后从小的依次开始选取,若选取得边使 生成树 T 不形成回路,则把它并入 TE 中,保留作为 T 的一条边;若选取得边使生成树形成 回路,则舍弃;如此继续进行,直到使 TE 中包含 n-1 条边为止。 实现克鲁斯卡尔(Kruskal)算法时,要解决以下两个问题: 1.选择代价最小的边(堆排序,或简单选择排序); 2.判定边所关联的两个顶点是否在同一个连通分量中(集合) ? 算法的关键与优化:
NOIP 算法总结 33 山东省广饶一中 杨庆礼

kruskal 算法实现过程中的关键和难点在于:如何判断欲加入的一条边是否与生成树 中已经保留的边形成回路?我们可以将顶点划分到不同的集合中, 每个集合的顶点表示一个 无回路的连通分量。初始时,我们把 n 个顶点划分到 n 个集合中,每个集合只有一个顶点, 表明顶点之间互不相通。当选取一条边时,若它的两个顶点分属两个不同的集合,则表明此 边连通了两个不同的连通分量, 因每个连通分量无回路, 所以连同后得到的连通分量仍无回 路。因此这条边应该保留,且合并成一个连通分量,若选取得边的两个顶点属于同一个连通 分量,则应舍弃,因为一个无回路的连通分量内加入一条新边必然产生回路。 ? 示例程序
const MXN=1000; type rqmap=record s,t,v:longint; end; var map:array[1..MXN*MXN] of rqmap; father:array[1..MXN] of longint; n,m,i,ingraph,ans:longint; procedure qsort(b,e:longint);//排序 var i,j,x:longint; t:rqmap; begin i:=b;j:=e;x:=map[(i+j)>>1].v; while (i<=j) do begin while (map[i].v<x) do inc(i); while (map[j].v>x) do dec(j); if (i<=j) then begin t:=map[i];map[i]:=map[j];map[j]:=t;inc(i);dec(j);end; end; if i<e then qsort(i,e); if j>b then qsort(b,j); end; function find(x:longint):longint; begin if (father[x]=x) then exit(x); father[x]:=find(father[x]);//路径压缩 exit(father[x]); end; procedure union(a,b:longint); //并查集 begin father[find(a)]:=find(father[b]); end; begin readln(n,m);

NOIP 算法总结

34

山东省广饶一中 杨庆礼

for i:=1 to n do father[i]:=i; for i:=1 to m do readln(map[i].s,map[i].t,map[i].v); qsort(1,m);ans:=0;ingraph:=1;i:=0; while (ingraph<n) do begin inc(i); if find(map[i].s)<>find(map[i].t) then begin inc(ingraph);inc(ans,map[i].v);union(map[i].s,map[i].t); end; end; writeln(ans); end.

topology 排序 整体思想:扫描纵列,如果纵列上没有任何后继节点,则找到,把这一列的横排都填为零
var a:array[1..100,1..100] of longint; s:array[1..100] of longint; ans:array[1..100] of longint; i,j,n,kg,x,w:longint; begin readln(n); fillchar(a,sizeof(a),0); fillchar(s,sizeof(s),0); for i:=1 to n do for j:=1 to n do begin read(a[i,j]); end; i:=1; x:=1; for j:=1 to n do begin kg:=0; for w:=1 to n do if a[w,j]=1 then inc(kg); if kg=0 then begin ans[x]:=j; inc(x); for w:=1 to n do a[j,w]:=0; end; end; NOIP 算法总结 35 山东省广饶一中 杨庆礼

for i:=1 to n do write(ans[i],' '); end.

关键路径

利用拓扑排序
const maxx=50; var a:array[1..maxx,1..maxx]of longint;//邻接矩阵 p:array[1..maxx] of longint;//拓扑路径 b:array[1..maxx] of longint;//b[i]表示第 i 个点到起点的距离 c:array[1..maxx] of longint;//c[i]表示在关键路径时 i 点的前驱 pd:array[1..maxx] of boolean; n,m,i,j,k:longint; procedure change; var i,j:longint; begin fillchar(a,sizeof(p),0); fillchar(b,sizeof(b),0); fillchar(c,sizeof(c),0); fillchar(p,sizeof(p),0); fillchar(pd,sizeof(pd),false); end; procedure tp(k:longint); var i,j:longint; begin if k=n+1 then exit; for i:=1 to n do begin if (b[i]=0) and (pd[i]) then begin p[k]:=i;//拓扑序列 pd[i]:=false; for j:=1 to n do if a[i,j]<>0 then dec(b[j]);//b[j] 用来存入度 tp(k+1); end; end; end; procedure main; var i,j:longint; begin

NOIP 算法总结

36

山东省广饶一中 杨庆礼

b[p[1]]:=0; c[p[1]]:=0; for i:=2 to n do for j:=1 to n do if b[p[j]]+a[p[j],p[i]]>b[p[i]] then begin b[p[i]]:=b[p[i]]+a[p[j],p[i]]; c[p[i]]:=p[j]; end; end; procedure output; var i:longint; begin for i:=1 to n-1 do write(c[i],'-->'); writeln(c[n]); writeln(b[n]); end; begin change; readln(n); for i:=1 to n do for j:=1 to n do read(a[i,j]); tp(1); main; output; end.

按照概念 (1)关键路径:AOE 网中,从事件 i 到 j 的路径中,加权长度最大者称为 i 到 j 的关键路 径(Critical Path) ,记为 cp(i,j)。特别地,始点 0 到终点 n 的关键路径 cp(0,n)是整个 AOE 的关键路径。 (2)事件最早/晚发生时间 etv:事件 vi 的最早发生时间为,从始点到 vi 的最长(加权)路径长度,即 cp(0,i) ltv:事件 vi 的最晚发生时间为:在不拖延整个工期的条件下,vi 的可能的最晚发生时间。 即 ltv(i) = etv(n) - cp(i, n) 要从右往左推 (3)活动最早/晚开始时间 活动 ak=<vi, vj>的最早开始时间 ete(k): 等于事件 vi 的最早发生时间, 即 ete(k) = etv(i) = cp(0, i) 活动 ak=<vi, vj>的最晚开始时间 lte(k)定义为:在不拖延整个工期的条件下,该活动的允 许的最迟开始时间,
NOIP 算法总结 37 山东省广饶一中 杨庆礼

即 lte(k) = ltv(j)–len(i, j),这里,ltv(j)是事件 j 的允许的最晚发生时间,len(i, j) 是 ak 的权。 活动 ak 的最大可利用时间:定义为 lte(k)-ete(k) 4.关键路径:是活动的集合 若活动 ak 的最大可利用时间等于 0(即(lte(k)=ete(k)) ,则称 ak 为关键活动,否则为非 关键活动。 显然,关键活动的延期,会使整个工程延期。但非关键活动不然,只要它的延期量不超过它 的最大可利用时间,就不会影响整个工期。
const maxx=100; var a:array[1..maxx,1..maxx] of longint; et,eet:array[1..maxx] of longint; //eet 表示活动最早可以开始的时间,et 表示活动最迟应该开始的时间 n,i,j,k,x,y,w:longint; min,max:longint; begin fillchar(a,sizeof(a),char(-1)); fillchar(et,sizeof(et),0); fillchar(eet,sizeof(eet),0); readln(n); readln(x,y,w); while x<>0 do begin a[x,y]:=w; readln(x,y,w); end; eet[1]:=0; for i:=2 to n do begin max:=0; for j:=1 to n do if a[j,i]<>-1 then if a[j,i]+eet[j]>max then max:=a[j,i]+eet[j]; eet[i]:=max; end; et[n]:=eet[n]; for i:=n-1 downto 1 do//最迟开始时间需要倒着推 begin min:=maxint; for j:=1 to n do if et[j]-a[i,j]<min then//事件 vi 的最晚发生时间为:在不拖延整个工期的条件下,vi 的可 能的最晚发生时间。即 ltv(i) = etv(n) - cp(i, n) min:=et[j]-a[i,j]; if a[i,j]<>-1 then

NOIP 算法总结

38

山东省广饶一中 杨庆礼

et[i]:=min; end; for i:=1 to n-1 do if et[i]=eet[i] then //如果最早开始时间和最晚开始时间相同即认为是关键事件 write(i,'-->'); writeln(n); writeln(max); end. //默认为节点按顺序输入,即序号前面的结点会影响序号后面结点的活动

次短路 删边:每次删最短路上的一条边,用 Dijkstra+堆求单源最短路径,则每次求最短路径时间 复杂度为 O(N*log(N+M) + M),所以总的时间复杂度为 O(N*M*log(N+M) + M^2)。 次小生成树 {O(n^3)} 先求 MST 并记录选择的边 依次删掉这些边(n-1 次)做 MST 求出新的生成树的值 则这些值中最小的即为 the Second MST {O(n^2)} 在求 MST 的同时,对于新加入的节点,max[i][j]记录已加入的节点 i 到新加入节点 j 的路 径上边权最大的值。 求完后 mst 记录最小生成树的权值和,枚举每一条不在树中的边 u~v,必然与 MST 形成一个 圈,max[u][v]中存的就是圈中除了新加入的边外最大的边了。那么加入 u~v 后,生成树的 权值 min=mst+g[u][v]-max[u][v]; 最小的 min 就是次小生成树 匈牙利算法
var g:array[1..maxn,1..maxm]of boolean; y:array[1..maxm]of boolean; link:array[1..maxm]of longint; //图,g[i,j]:节点 i 到节点 j 是否有边 //访问标记,y[i]:节点 i 是否已被访问过 //与节点 i 匹配的点,link[i]=0 表示 i 没有被匹配

function find(v:longint):boolean; //从 v 出发找匹配 var i:longint; begin for i:=1 to m do //枚举与 v 相连的点 i

NOIP 算法总结

39

山东省广饶一中 杨庆礼

if g[v,i] and (not y[i]) then begin y[i]:=true; if (link[i]=0)or find(link[i]) then

//如果 i 与 v 相连且还未被访问过 //标记 i 已被访问过

//如果 i 无匹配或原来的匹配点 link[i]可以另找一个匹配 begin link[i]:=v; find:=true; exit; end; end; find:=false; end; begin //read the graph into array g[][] for i:=1 to n do begin fillchar(y,sizeof(y),0); if find(i) then inc(ans); end; //now then ans stores the max match end. // 匹配不成功 //让 v-i 与 i 匹配 //匹配成功并返回

博弈

取对称状态 Alice and Bob decide to play a funny game. At the beginning of the game they pick 6 n(1 <= n <= 10 ) coins in a circle, as Figure 1 shows. A move consists in removing one or two adjacent coins, leaving all other coins untouched. At least one coin must be removed. Players alternate moves with Alice starting. The player that removes the last coin wins. (The last player to move wins. If you can't move, you lose.) 如果 n<=2 那么先手的会获得胜利,当 n>=3 时,先手的走了一步以后,后手的可以把这个一 个大图分成两个完全相同的小图,每步都是如此,则在 n 步以后,先手的总会无棋可取,后 手的获得胜利。
var t,n,i:longint; begin while true do begin readln(n);

NOIP 算法总结

40

山东省广饶一中 杨庆礼

if n=0 then halt; if n<=2 then writeln('Alice') else writeln('Bob'); end; end.

取 NIM 值 Here is a simple game. In this game, there are several piles of matches and two players. The two player play in turn. In each turn, one can choose a pile and take away arbitrary number of matches from the pile (Of course the number of matches, which is taken away, cannot be zero and cannot be larger than the number of matches in the chosen pile). If after a player’s turn, there is no match left, the player is the winner. Suppose that the two players are all very clear. Your job is to tell whether the player who plays first can win the game or not. 随机博弈指的是这样的一个博弈游戏,目前有任意堆石子,每堆石子个数也是任意的, 双方轮流从中取出石子,规则如下:1)每一步应取走至少一枚石子;每一步只能从某一堆中 取走部分或全部石子;2)如果谁取到最后一枚石子就胜。也就是尼姆博弈(Nimm Game) 。 必败局面:也叫奇异局势。无论做出何出操作,最终结果都是输的局面。必败局面经过 2 次操作后,可以达到另一个必败局面。必胜局面:经过 1 次操作后可以达到必败局面。即当 前局面不是必败局面就是必胜局面,而必胜局面可以一步转变成必败局面。 最终状态: (1)最后剩下一堆石子; (必胜局面) (2)剩下两堆,每堆一个; (必败局面) (3)当石子剩下两堆,其中一堆只剩下 1 颗,另一堆剩下多于 n 颗石子时,当前取的 人只需将多于 1 颗的那一堆取出 n-1 颗,则局面变为刚才提到的必败局面。 (必胜局面) 判断当前局势是否为必胜(必败)局势: 1)把所有堆的石子数目用二进制数表示出来,当全部这些数按位异或结果为 0 时 当前局面为必败局面,否则为必胜局面; 2)在必胜局面下,因为所有数按位异或的结果 是大于零的,那么通过一次取,将这个(大于其它所有数按位异或的结果的)数下降到其它 所有数按位异或的结果,这时局面就变为必败局面了。 定理:一组自然数中必然存在一个数,它大于等于其它所有数按位异或的结果。 证明:原命题等价于,设 a1^a2^... ^an=p,p≠0 时,必存在 k,使得 ak^p<ak< span="">(当 p=0 时,对于任意的 k,有 ak^p=ak) 。 设 p 的最高位是第 q 位,则至少存在一个 k,使得 ak 的第 q 位也是 1,而 ak^p 的第 q 位为 0,所以 ak^p<ak 补缀一点, (a^b)^b=a^(b^b)=a^0=a,所以 ak^p 相当于“其它所有数按 位异或的结果”。
var x,y,n:int64;i:longint; procedure main; begin y:=0; NOIP 算法总结 41 山东省广饶一中 杨庆礼

read(n); for i:=1 to n do begin read(x); y:=y xor x; end; if y=0 then writeln('No') else writeln('Yes'); end; begin while not seekeof do main; end.

分治

二分法找最值
var n,m,a1,b1,a2,b2,i:longint; q:array[1..100]of longint; procedure fenzhi(a,b:longint;var max,min:longint); var d,max1,max2,min1,min2:longint; begin if a=b then begin max:=q[a]; min:=q[a]; end else if b-a=1 then begin if a>b then begin max:=q[a]; min:=q[b]; end else begin max:=q[b]; NOIP 算法总结 42 山东省广饶一中 杨庆礼

min:=q[a]; end; end else begin d:=(a+b) div 2; fenzhi(a,d,max1,min1); fenzhi(d+1,b,max2,min2); if max1>max2 then max:=max1 else max:=max2; if min1<min2 then min:=min1 else min:=min2; end; end; begin read(n); for i:=1 to n do read(q[i]); m:=n div 2; fenzhi(1,m,a1,b1); fenzhi(m+1,n,a2,b2); if b1<b2 then write(b1,' ') else write(b2,' '); if a1>a2 then write(a1,' ') else write(a2,' '); end.

回溯

N 皇后
procedure try(i:longint); var j:longint; begin if i=n+1 then begin print;exit;end; for j:=1 to n do if a and b[j+i] and c[j-i] then begin x:=j; a[j]:=false; b[j+i]:=false; c[j-i]:=false;

NOIP 算法总结

43

山东省广饶一中 杨庆礼

try(i+1); a[j]:=true; b[i+j]:=true; c[j-i]:=true; end; end;

Hanoi Tower {h(n)=2*h(n-1)+1 h(1)=1 初始铜片分布在 3 个柱上,给定目标柱 goal;h[1..3,0..n]存放三个柱的状态,now 与 nowp 存最大的不到位的铜片的柱号和编号,h[I,0]存第 I 个柱上的个数。
procedure hanoi(n,a,b,c:byte); {将第 n 块铜片从 a 柱通过 b 柱移到 c 柱上} begin if n=0 then exit; hanoi(n-1,a,c,b); {将上面的 n-1 块从 a 柱通过 c 柱移到 b 柱上} write(n,’moved from’,a,’to’,c); hanoi(n-1,b,a,c);{ 将 b 上的 n-1 块从 b 柱通过 a 柱移到 c 柱上} end;

高精度计算

高精度加法
var s1,s2:string; a,b:array[1..100] of longint; la,le,len,i:longint; begin readln(s1); readln(s2); la:=length(s1); for i:= 1 to la do a[i]:=ord(s1[la+1-i])-48; le:=length(s2); for i:=1 to le do b[i]:=ord(s2[le+1-i])-48; len:=la; if le>len then len:=le; for i:=1 to len do

NOIP 算法总结

44

山东省广饶一中 杨庆礼

begin a[i+1]:=a[i+1]+(a[i]+b[i]) div 10; a[i]:=(a[i]+b[i]) mod 10; end; if a[len+1]>0 then len:=len+1;{判断最高位} for i:=len downto 1 do write(a[i]); end.

高精度减法
const n=1000; type arr=array[0..n]of longint; var a,b:arr;s:string; function f:boolean; var i:longint=1; begin f:=true; while ((i<n)and(a[i]=b[i])) do inc(i); if a[i]<=b[i] then f:=false; end; procedure init(var p:arr); var m:char; k,i:longint; begin k:=1; read(m); while m in['0'..'9'] do begin p[k]:=ord(m)-48;k:=k+1;read(m);{使得能够不断读数} end; for i:=1 to k do begin p[n+i-k]:=p[i];p[i]:=0;{把最小位放在前面,便于顺次详见} end; end; procedure work;

NOIP 算法总结

45

山东省广饶一中 杨庆礼

var t,g:longint;i:longint; begin if f then write(''); if not f then begin s:='-'; {判断减数和被减数大小,如果被减数大于减数就填负号后交换位置} for i:=1 to n do begin t:=a[i];a[i]:=b[i];b[i]:=t; end; end; g:=0;{进位标志} for i:=n downto 1 do begin if a[i]>=b[i]+g then begin a[i]:=a[i]-b[i]-g;g:=0; end{不需要借位时} else begin a[i]:=10+a[i]-b[i]-g;g:=1; end; end; end; procedure output; var i:longint=1; begin while((a[i]=0)and(i<n))do inc(i); {当在范围限度内且为零时就不断不断向后移以寻找做完减法后的最高位} while i<n do begin write(a[i]);inc(i); end; end; begin NOIP 算法总结 46 山东省广饶一中 杨庆礼

fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0); init(a); readln; init(b);readln; work; write(s);output; end.

高精度乘法
const max=200; type arr=array[1..max]of longint; arrr=array[1..2*max] of longint; var a,b:arr;c:arrr;k,s1,s2,n:longint; procedure init(var p:arr); var s:string; i:longint; begin read(s);n:=length(s); if s='0' then begin write('0');halt; end; for i:=n downto 1 do p[n-i+1]:=ord(s[i])-48;{把小位数放在前面} end; procedure work; var i,j,x,l:longint; begin for i:=1 to s1 do for j:=1 to s2 do begin l:=a[i]*b[j]; c[i+j-1]:=c[i+j-1]+l; {解决错位相加问题,a、b 数组的值正好放在 c 数组【i+j-1】的位置上,就可以用这个位置原来的数 加上新乘出的数解决问题,在运算过程中,a、b 数组里面的值不能改变,所以必须要新开一个新数组} end; for i:=1 to k do begin NOIP 算法总结 47 山东省广饶一中 杨庆礼

c[i+j]:=c[i+j]+c[i+j-1] div 10; {这一步必须在前面否则下面一步就改变了 c 数组里面的值} c[i+j-1]:=c[i+j-1] mod 10; end; while c[k]=0 do dec(k);{寻找最高位} x:=c[k]; while x>0 do begin c[k]:=x mod 10; x:=x div 10; inc(k); end;{解决最高位问题} end; procedure output; var i:longint; begin for i:=k-1 downto 1 do write(c[i]); end; begin fillchar(a,sizeof(a),0); fillchar(b,sizeof(b),0);fillchar(c,sizeof(c),0); init(a);readln;s1:=n; init(b);readln; s2:=n; k:=s1+s2; {乘法得出结果后的最高位数为两个位数的因数之和} work;output; end.

高精度除法
type arr=array[0..10000]of longint; var a,b,c,d:arr;a1,b1,n,j,I,len:longint;s,s1,s2:string; procedure init; begin readln(s);len:=length(s); a1:=pos(' ',s);s1:=copy(s,1,a1-1);s2:=copy(s,a1+1,len-a1);a1:=length(s1); for i:=1 to a1 do a[i]:=ord(s1[a1-i+1])-48; b[0]:=length(s2);

NOIP 算法总结

48

山东省广饶一中 杨庆礼

for i:=1 to b[0] do b[i]:=ord(s2[b[0]-i+1])-48; end; function f:boolean; var i:longint; begin if d[0]>b[0] then exit(true); if d[0]<b[0] then exit(false); for i:=d[0] downto 1 do begin if d[i]>b[i] then exit(true) else if d[i]<b[i] then exit(false); end; exit(true); end; procedure change(x:longint); var i:longint; begin inc(d[0]); for i:=d[0] downto 2 do d[i]:=d[i-1]; d[1]:=x; end; function work:boolean; var i:longint; begin if f=false then exit(false); for i:=1 to d[0] do begin d[i+1]:=d[i+1]-1+(d[i]+10-b[i]) div 10; d[i]:=(d[i]+10-b[i])mod 10; end; while (d[d[0]]=0) and(d[0]>1) do dec(d[0]); exit(true); end; procedure output; var i:longint; begin NOIP 算法总结 49 山东省广饶一中 杨庆礼

while (c[a1]=0) and(a1>1) do dec(a1); for i:=a1 downto 1 do write(c[i]); writeln; end; begin fillchar(a,sizeof(a),0); fillchar(b,sizeof(b),0); fillchar(c,sizeof(c),0); fillchar(d,sizeof(d),0); init; if a1<b[0] then begin write('0...'); for j:=a1 downto 1 do write(a[j]); halt; end; for j:=a1 downto 1 do begin change(a[j]); while work do inc(c[j]); end; output; end.

高精度阶乘
{高精度乘单精度} const max=2000; var a:array[1..max] of longint;n,i,j,l,q:longint; begin readln(n); a[1]:=1;l:=1; {l 表示前面的数依次的阶乘} for i:=2 to n do begin for j:=1 to l do a[j]:=a[j]*i;{做乘法}

NOIP 算法总结

50

山东省广饶一中 杨庆礼

for j:=1 to l do begin a[j+1]:=a[j+1]+a[j] div 10; a[j]:=a[j] mod 10;{处理进位问题} while a[l+1]<>0 do begin l:=l+1; a[l+1]:=a[l+1]+a[l] div 10; a[l]:=a[l] mod 10; end; {处理最高位及数位问题} end; end; for i:=l downto 1 do write(a[i]); end.

高级数据结构

二叉树
//二叉树的先序遍历 type note=record father,lch,rch:longint;end; var a:array[1..100] of note;n,j,t,m:longint;s:longint; procedure duru; var i:longint;f,l,r:longint; begin read(n); for i:=1 to n do begin readln(f,l,r); a[f].lch:=l;{f 的左孩子为 l} a[f].rch:=r;{f 的右孩子为 r} if l<>0 then a[l].father:=f;{如果有左孩子那么左孩子的父亲是 f} if r<>0 then a[r].father:=f;{如果有右孩子那么右孩子的父亲是 f}

NOIP 算法总结

51

山东省广饶一中 杨庆礼

end; end;{输入的过程,第一个是父亲,后两个为左右孩子,0 表示空} function root:longint; var i:longint; begin for i:=1 to n do{i 表示结点} if a[i].father=0 then begin root:=i;exit;{如果这个结点的父亲为零,则这个结点就是根} end; end;{找根的程序} procedure xiangen(t:longint); begin if t<>0 then begin write(t,' ');{先根} xiangen(a[t].lch);{再对左子树先根遍历,左孩子当根} xiangen(a[t].rch);{再对右子树先根遍历,后孩子当根} end; end;{进行先序遍历并输出的程序} begin duru;m:=root; writeln(m);xiangen(m); end.

//二叉树的中序遍历 procedure zhonggen(t:longint); begin if t<>0 then begin write(t,' '); zhonggen(a[t].lch); zhonggen(a[t].rch); end; end; NOIP 算法总结 52 山东省广饶一中 杨庆礼

//二叉树的后序遍历 procedure hougen(t:longint); begin if t<>0 then begin hougen(a[t].lch); hougen(a[t].rch); write(t,' ') end; end;

//已知二叉树的前序遍历与中序遍历求后序遍历 var s1,s2:string; procedure work(s1,s2:string); var b,a:longint;{b,a 的值在不断改变,必须放在局部变量里} begin if s1<>'' then begin b:=length(s1); a:=pos(s1[1],s2); work(copy(s1,2,a-1),copy(s2,1,a-1)); work(copy(s1,a+1,b-a),copy(s2,a+1,b-a)); write(s1[1]); end; end; begin readln(s1);readln(s2); work(s1,s2); end.

NOIP 算法总结

53

山东省广饶一中 杨庆礼

并查集
{已按秩优化} a:array[1..max] of longint;//a[i]表示 i 的前驱 function find(i:longint):longint;//非递归算法找 i 的根 var j,k,t:longint; begin j:=i; while a[j]<>0 do j:=a[j]; // 顺着 i 向上找根 find:=j; k:=i; //从 i 开始对子树结点进行路径压缩 while a[k]<>0 do begin t:=k;k:=a[k];a[t]:=j;end; end; function root(i:longint):longint;//递归算法找 i 的根 var j,k,t:longint; begin if a[i]=0 then exit(i); //若 i 为根,返回本身结点序号 root:=root(a[i]); //否则继续向上找 a[i]:=root; end; procedure union(x,y:longint);//合并 begin if root[x]=root[y] then else f[y]:=x; end;

树状数组
{求 2^k 的代码:} function begin lowbit:=t and(t xor (t-1)); end; {当想要查询一个 SUM(n)(求 A[1]..A[n]的和),可以依据如下算法即可: step1:令 sum = 0,转第二步; step2:假如 n <= 0,算法结束,返回 sum 值,否则 sum = sum + Cn,转第三步; step3:令 n = n–lowbit(n),转第二步。} function getsum(k:integer):integer; var t:integer; begin t:=0; while k>0 do lowbit(t:longint):longint;

NOIP 算法总结

54

山东省广饶一中 杨庆礼

begin t:=t+c[k]; k:=k-lowbit(k); end; getsum:=t; end; {修改算法如下(给某个结点 i 加上 x): step1: 当 i > n 时,算法结束,否则转第二步; step2: Ci = Ci + x, i = i + lowbit(i)转第一步。 i = i +lowbit(i)这个过程实际上也只是一个把末尾 1 补为 0 的过程。} procedure add(i:longint;x:longint); begin while i<=n do begin c[i]:=C[i]+x; i:=i+lowbit(i); end; end;

线段树
type xtree=record a,b,left,right,cover:longint; end; //a,b 是区间左右端点,当 a=b 表示一个叶子节点;left,right 表示左右儿子,cover 表示是否被覆盖 var tree:array[1..1000] of xtree; c,d,number,tot:longint; //tot 为一共有多少个结点 procedure make(a,b:longint); var now:longint;//now 必须为局部变量,dfs 中枚举变量一样的道理 begin inc(tot); now:=tot; tree[now].a:=a; tree[now].b:=b; tree[now].cover:=0; if a+1<b then begin tree[now].left:=tot+1; make(a,(a+b)div 2); tree[now].right:=tot+1; NOIP 算法总结 55 山东省广饶一中 杨庆礼

//若 now 为全局变量,建左子树会修改 now 的值,导致此处建树不正确 make((a+b) div 2,b); end; end; //建树过程 procedure insert(num:longint); begin if (c<=tree[num].a)and(tree[num].b<=d) then inc(tree[num].cover) //若当前区间被[c,d]覆盖,则 cover+1 else begin if c<(tree[num].a+tree[num].b)div 2 then insert(tree[num].left); if d>(tree[num].a+tree[num].b)div 2 then insert(tree[num].right); end; //否则将区间[c,d]插到左右子树中 end; //插入线段[c,d](c,d 为全局变量)到线段树第 num 个节点区间 procedure delete(num:longint); begin if (c<=tree[num].a)and(tree[num].b<=d) then dec(tree[num].cover) //若当前区间被[c,d]覆盖,则 cover-1 else begin if c<(tree[num].a+tree[num].b)div 2 then delete(tree[num].left); if d>(tree[num].a+tree[num].b)div 2 then delete(tree[num].right); end; //否则将区间[c,d]在左右子树中删除 end; //在线段树第 num 个节点区间中删除线段[c,d] procedure count(num:longint); begin if tree[num].cover>0 then number:=number+(tree[num].b-tree[num].a) //若当前区间被完全覆盖,则累加到 number 全局变量中 else begin if tree[num].left>0 then count(tree[num].left); if tree[num].right>0 then count(tree[num].right); end;

NOIP 算法总结

56

山东省广饶一中 杨庆礼

//否则,若为部分覆盖,则累加左右子树的测度 end; //计算整个线段树的测度(被覆盖区间的总长度) begin readln(c,d); make(c,d); readln(c,d); insert(1);//插入线段[c,d]; readln(c,d); delete(1);//删除线段[c,d] count(1);//计算线段树的测度 writeln(number); end.

二叉搜索树
{treap 示范代码: 标准的代码缩进风格,优美的算法实现。 经典标程,完全掌握后水平会提高很多 不改变 bst 的性质(在 bst 所有子树中均满足:左子树的所有节点<=根<=右子树的所有节点) 通过旋转操作,使根的 hr 最小(即所有的 hr 构成堆的关系)} var //l[i],r[i],v[i]:i 号结点的左儿子、右儿子,关键值 //hr[i]:i 号节点的优先值(treap 所有子树中,根的 hr 必须是最小的) //s[i]:i 号节点为根的子树节点总数 l,r,hr,s,v:array[0..2000000]of longint; n,root,m:longint; procedure init;//初始化 begin readln(n); m:=0; //randomize; //考试要求程序每次运行结果必须一致,慎用。确实要用:randomize 100; fillchar(s,sizeof(s),0); fillchar(l,sizeof(l),0); fillchar(r,sizeof(r),0); root:=0; end; //旋转是平衡二叉树的精髓,它不会改变 bst 的性质(左子树<=根<=右子树) //左旋使树的左子树深度+1,右子树深度-1 //右旋使树的右子树深度+1,左子树深度-1 procedure l_rotate(var x:longint);inline;//左旋以 x 为根的子树(注意 var 参数及意义) NOIP 算法总结 57 山东省广饶一中 杨庆礼

var y:longint; begin y:=r[x]; l[y]:=x; //保存 x 的右儿子到 y 中 //x 作为 y 的左儿子 r[x]:=l[y]; //将 y 的左儿子作为 x 的右儿子 s[y]:=s[x]; //维护旋转后的子树大小 s[x]:=s[l[x]]+s[r[x]]+1; x:=y; end; procedure r_rotate(var x:longint);inline;//右旋以 x 为根的子树 var y:longint; begin y:=l[x]; l[x]:=r[y]; r[y]:=x; s[y]:=s[x]; s[x]:=s[l[x]]+s[r[x]]+1; x:=y; end; //插入(递归,if key<=root,则插入到左子树,否则到右子树,直到尽头再新建节点) procedure insert(var k,key:longint);inline; begin if k=0 then//已到尽头,新建节点并写入 key 及随机值 hr begin inc(m); v[m]:=key; s[m]:=1; hr[m]:=random(maxlongint); k:=m;//修改 k,使父节点指向当前节点(修改前从父节点指向 0) exit; end; inc(s[k]); if key<=v[k] then//若 key<=根则插入到左子树,否则到右子树 begin insert(l[k],key);//若 l[k]=0,到下层则新建节点并修改 l[k]=m if hr[l[k]]>hr[k] then r_rotate(k); exit; end; if key>v[k] then //旋转 //y 为根

NOIP 算法总结

58

山东省广饶一中 杨庆礼

begin insert(r[k],key); if hr[r[k]]>hr[k] then l_rotate(k); exit; end; end; {删除:在 k 号节点为根的子树中删除 key 基本方法:由于是静态结构,为了提高效率,并没真正删除 若找到则删除,若没找到,则删除查找尽头的节点 主程序中需判断返回值,若不等于 key,重新插入 key 即可 找到后的处理: 若为叶节点,直接删除,否则,将要删除的节点左子树的最右节点(思考:为什么?)代替它 } function delete(var k:longint;key:longint):longint;inline; begin dec(s[k]);//维护节点总数 //如果找到,或已到尽头 if (key=v[k])or(l[k]=0)and(key<=v[k])or(r[k]=0)and(key>v[k]) then begin delete:=v[k];//返回要删除的节点(不一定=key) if (l[k]=0)or(r[k]=0) then //若左右子树只有一个,则让儿子代替根即可 begin k:=l[k]+r[k];//用儿子替换当前要删除的节点 exit; end; v[k]:=delete(l[k],key+1);//k 左右子树都有,则用左子树的最右节点替换 k exit; end; if key<=v[k] then//若 k<=v[k],则在左子树中删,否则,在右子树中删 exit(delete(l[k],key)); if key>v[k] then exit(delete(r[k],key)); end; function find(var k,key:longint):boolean;inline;//查找 begin if k=0 then//递归边界 exit(false); if key>v[k] then find:=find(r[k],key) else

NOIP 算法总结

59

山东省广饶一中 杨庆礼

find:=(v[k]=key)or find(l[k],key); end; //key 的排名(key 排在第几,按从小到大的顺序) function rank(var t,key:longint):longint;inline; begin if t=0 then exit(1); if key<=v[t] then rank:=rank(l[t],key) else rank:=s[l[t]]+1+rank(r[t],key); end; function select(var t:longint;k:longint):longint;inline;// 选择排在第 k 位的数 begin if k=s[l[t]]+1 then//若找到第 k 位的节点,则返回节点 key 值 exit(v[t]); if k<=s[l[t]] then//递归 select:=select(l[t],k) else select:=select(r[t],k-1-s[l[t]]); end; function pred(var t,key:longint):longint;inline;//找 key 的前趋 begin if t=0 then exit(key); if key<=v[t] then//key<=根,原问题等价于在左子树中找 key pred:=pred(l[t],key) else begin //key>根,原问题等价于在右子树中找 key,但右儿子返回时,要判断你是不是 key 的前 趋 pred:=pred(r[t],key);//右子树的返回值 if pred=key then pred:=v[t]; end; end; function succ(var t,key:longint):longint;inline;//找 key 的后继 begin if t=0 then exit(key); if v[t]<=key then //如果右子树的返回值=key 说明在右子树中没找到 key 的前趋 //右子树没有 key 的前趋,那你就是了。

NOIP 算法总结

60

山东省广饶一中 杨庆礼

succ:=succ(r[t],key) else begin succ:=succ(l[t],key); if succ=key then succ:=v[t]; end; end; procedure order;inline;//操作解释和执行 var a,b:longint; begin readln(a,b); case a of 1:insert(root,b); 2:delete(root,b); 3:writeln(find(root,b)); 4:writeln(rank(root,b)); 5:writeln(select(root,b)); 6:writeln(pred(root,b)); 7:writeln(succ(root,b)); end; end; procedure main;inline;//主模块 var i:longint; begin init; for i:=1 to n do order; end; begin//主程序 main; end.

进制转换

1.将 m 进制数 n 转化成一个十进制数
{输入共一行表示 m 进制的 n 化成十进制的数。}

NOIP 算法总结

61

山东省广饶一中 杨庆礼

var s:string;sum,n,m,i,r,t,c:longint; begin readln(s); val(copy(s,pos(' ',s)+1,length(s)),m,c); delete(s,pos(' ',s),length(s)); {使整数 m 中放进制,字符串 s 中放需要的数} t:=1;n:=length(s);sum:=0; for i:=n downto 1 do begin case s[i] of '0'..'9':r:=ord(s[i])-48; 'A'..'Z':r:=ord(s[i])-55; end; sum:=sum+r*t; t:=t*m; end; write(sum); end.

2.将十进制数 n 转换成 m 进制数
{输入共一行表示 n 的 m 进制。} var a:char; i,n,m:integer; c:array[10..16]of char; var r:integer; begin if n=0 then exit; r:=n mod m; nm(n div m); end; begin a:='A'; for i:=10 to 16 do begin c[i]:=a; a:=succ('A') end; //后继函数,即前一个或后一个 ASCII 码代表的字符. 如:pred('b')='a',succ('b')='c'. readln(n,m); nm(n); end。 //输入 //引用过程,过程中包含输出。 //直到商等于 0 //求余数 //反向取余数 //存储 10~16 对应的 7 个字母 procedure nm(n:integer); //M 为全局变量,所以这里只要 N 就可以了

if r>=10 then write(c[r]) else write(r); //大于 10 的数特殊处理

NOIP 算法总结

62

山东省广饶一中 杨庆礼

后记

本文未涉及的内容包括但不限于: 哈希(HASH) 强连通分量 离散化 尺取法 网络流 计算几何(包括凸包) 2-SAT LCA 倍增法 KMP 算法 后缀数组 Grundy 数 trie 树 AC 自动机 FFT 快速傅里叶变换 斯坦纳树 单纯形法 矩阵 三分搜索 α -β 剪枝 离散对数 微积分 树链剖分 负进制转换 群论 ? 不过没有关系, 这些基本都属于 NOIP 涉及不到的范围, 学无止境, 把握好当下的才是关键!

NOIP 算法总结

63

山东省广饶一中 杨庆礼

参考文献 百度百科 《数学》第三册 苏州大学出版社 《动态规划学案》 山东省实验中学 王乃广 《PASCAL 省选模板》island 《NOIP2012 最终征途》亟隐 Slack 《自然数的因数》桃花岛主 《二分图的最大匹配、完美匹配和匈牙利算法》pi9nc 推荐文章&书籍&博客&网站 刘汝佳《算法竞赛入门经典 1&2》 啊哈磊《啊哈!算法》 Thomas H.Cormen 等 《算法导论》 编程之美小组《编程之美》 秋叶拓哉等《挑战程序设计竞赛》 Charles Petzold 《CODE》 顾森《思考的乐趣》 《NOI 导刊》 (一本杂志,已经停办,不过可以找来以前的看看) 《骗分导论》 《人品导论》 博客园 CSDN 社区 MATRIX67 HZWER 图灵社区 枫伶忆《大话二进制,八进制,十进制,十六进制之间的转换》 免费程序员图书下载 快速查询数列 在线学习:计蒜客 在线学习:萌码 在线学习:实验楼 使用技巧:PDF 自由转换 PS:其实在竞赛之路上帮助最大的还是大牛神犇们的博客,从中可以学到很多的东西。我 也养成了写博客的习惯,做完题写写博客加加注释,整理思路的同时还能助人为乐。写博客 推荐去博客园或是 CSDN 社区,这是专门面向程序猿的博客,支持自己设置板式,代码高 亮。因为有群体限制,所以交流起来也更方便。 PS:有关 NOIP 技巧整理和测评网站 OJ 整理的文章请移步本人技术博 联系我 技术博:川汉唐 邮箱:gryangqingli@163.com
NOIP 算法总结 64 山东省广饶一中 杨庆礼

QQ:1031304332 二零一五年七月 初稿 二零一五年十月 定稿

NOIP 算法总结

65

山东省广饶一中 杨庆礼


更多相关文档:

NOIP算法整理

NOIP算法整理_学科竞赛_高中教育_教育专区。2015NOIP算法总结PASCAL版 前言离 NOIP 还有一个星期,匆忙的把寒假整理的算法补充完善,看 着当时的整理觉得那时还年少。...

Noip常用算法大全

Noip 常用算法大全一、数论算法 1.求两数的最大公约数 function gcd(a,b:integer):integer; begin if b=0 then gcd:=a else gcd:=gcd (b.a mod b);...

Noip图论算法整理

N​o​i​p​图​论​算​法​整​理 暂无评价|0人阅读|0次下载|举报文档Edmonds-Karp var ans,i,j,k,s,t,tot,m,n,a,b,c:longint;...

NOIP算法总结

NOIP算法总结_电脑基础知识_IT/计算机_专业资料。NOIP 算法总结 BY.W.X 吃了、还得睡 (一)数论 1.最大公约数,最小公倍数 2.筛法求素数 3. mod 规律...

NOIP常用算法

NOIP常用算法_IT/计算机_专业资料。NOIP常用算法1.Dijkstra 1)适用条件&范围: a)单源最短路径(从源点 s 到其它所有顶点 v); b)有向图&无向图(无向图可以...

NOIP复赛必记常用算法

NOIP实用算法 33页 1财富值 NOIP复赛复习资料汇总 20页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...

noip算法总结2016

noip算法总结2016_学科竞赛_高中教育_教育专区。noip算法总结2016 算法总结一、 动态规划和递推 dp 一般的解题步骤: 分析问题, 弄清题意——从原问题中抽象出...

NOIP算法分类总结(C语言)

NOIP算法分类总结(C语言)_工学_高等教育_教育专区。模块目录 一、 排序 1. ...建设工程造价管理重点整理 工程造价计价与控制考前提分 2014造价工程师各科目冲刺...

基本算法NOIP

基本算法NOIP_计算机软件及应用_IT/计算机_专业资料。基本算法 c 语言版一、数论算法 1、求两个数的最大公约数 原理:欧几里德算法又称辗转相除法,用于计算两个...

NOIP算法总结 by Nap

NOIP 算法总结 BY.W.X 吃了、还得睡 (一)数论 1.最大公约数,最小公倍数 2.筛法求素数 3. mod 规律公式 4.排列组合数,错排 5.Catalan 数 6.康拓...
更多相关标签:
noip算法 | noip算法总结 | noip复赛算法 | noip提高组复赛算法 | noip算法模板 | noip算法大全 | noip提高组算法 | noip省选算法 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com