当前位置:首页 >> 学科竞赛 >> 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 ,