资源描述
NOIP算法总结 BY.W.X 吃了、还得睡（一）数论1.最大公约数，最小公倍数2.筛法求素数3. mod规律公式4.排列组合数，错排5.Catalan数6.康拓展开7负进制8.中位数的应用9.位运算（二）高精度算法1. 朴素加法减法2. 亿进制加法减法3. 乘法4. 除法5. 亿进制读入处理6. 综合应用(三)排序算法1. 冒泡2快排3堆排4归并（四）DP1. 概念2. 解题步骤3. 背包类DP4. 线性DP5. .区间动态规划6. 坐标型动态规划（规则类DP）7. 资源分配型动态规划8. 树型动态规划9. 状态压缩的动态规划10. 动态规划的一般优化方法（五）图论1. Floyd-Warshall2. Bellman-ford3. SPFA4. dijkstra5. prim6. kruskal7. 欧拉回路8. 哈密顿环9. flood fill（求图的强连通分量）10. 最小环问题（基于floyd）11. Topological sort12. 次短路13. 次小生成树（六）树1.堆2. 二叉排序树3. 最优二叉树（哈夫曼树）4.求树的后序遍历5.并查集及应用（七）分治1.二分查找2.二分逼近（注意精度问题）3二分答案4快排（见排序算法）5.归并排序（见排序算法）6.快速幂（八）贪心（九）搜索（十）其它1. 离散化2. KMP3. 字符串哈希4. 常用字符串函数过程(一)数论1. 最大公约数，最小公倍数function gcd(a,b:longint):longint; begin if b=0 then gcd:=a else gcd:=gcd(b,a mod b);end;function jslcm(a,b:longint):longint; begin jslcm:=a div gcd(a,b)*b;(先div防215) end;2.筛法求素数 varf:array1.10000000 of boolean;su:array1.100000 of longint;sj,n,i,j:longint;beginreadln(sj);fillchar(f,sizeof(f),true);f2:=true; for i:=2 to sj do if fi then begin j:=i+i; while jsj do begin fj:=false; j:=j+i; end; end; for i:=2 to sj do if fi then begin inc(n); sun:=i; end;end.3. mod规律公式结合律(a+b) mod p + c)mod p = (a + (b+c) mod p) mod p(a*b) mod p * c)mod p = (a * (b*c) mod p) mod p分配律(a +b)mod p c) mod p = (a c) mod p + (b c) mod p) mod p4.排列组合数，错排 A(n,m)=n!/(n-m)! C(n,m):=n!/m!(n-m)! 错排 通项 fn:=n!1-1/1!+1/2!-1/3!+(-1)n*1/n! (利用容斥原理证明)递推式 fn:=(n-1)*(fn-1+fn-2) (加法原理)5.Catalan数 （1）公式 h(n)=C(2n,n)/(n+1) (n=1,2,3,.) 【计算过程中可用质因子表优化】（2）应用 01串，出栈序列 对于一个二进制的01串，共n+m位，满足n个1，m个0，且0=n-m=1，该串还满足从左向右1的个数永远大于0的个数。问：共有多少种排列方式？此题可理解为进出栈问题，n个元素组成的队列，共有多少种进出栈的方式？答案是满足卡特兰数的，即n个元素的进出站顺序为h（n）=c（2n，n）/（n+1）；为什么呢？在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求（由左而右扫描，0的累计数大于1的累计数）的方案数即为所求。h（n）=c（2n，n）-c（2n，n-1）=c（2n，n）/（n+1）；推广：当nm时，即1的个数为n，0的个数为m排列方式的总数为：c（n+m,m）-c(n+m,m-1) =c(n+m,n-1)*(n-m+1)/m; 6.康拓展开 function ktzk(s:string):longint;const jc:array1.8 of longint=(1,2,6,24,120,720,5040,40320);var i,j,num,tem,l:longint;begin l:=length(s); num:=0; for i:=1 to l-1 do begin tem:=0; for j:=i+1 to l do if sisj then inc(tem); num:=num+tem*jc8-i; end; ktzk:=num;end;7.负进制 constch:array0.19ofchar=(0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,G,H,I,J);var n,r,x,y,z,nn,i:longint; ans:array1.2000of longint;begin readln(n,r); x:=0; nn:=n; repeat; inc(x); ansx:=n mod r; n:=n div r; if ansx0 then begin; ansx:=ansx-r; n:=n+1; end; until n=0; write(nn,=); for i:=x downto 1 do write(chansi); writeln(base,r,);end.8.中位数的应用(应用：士兵站队)varmin,i,j,n,h,mid:longint;x,y:array1.10000 of longint;procedure qs1(s,t:longint);procedure qs2(s,t:longint);begin readln(n); for i:=1 to n do read(xi,yi); qs1(1,n);（对y排序） min:=0; mid:=yn div 2+1; for i:=1 to n do min:=min+abs(yi-mid); qs2(1,n); （对x排序） for i:=1 to n do xi:=xi-i+1; qs2(1,n); （对x排序） mid:=xn div 2+1; for i:=1 to n do min:=min+abs(xi-mid); writeln(min);end.9.位运算（1） 基本操作andor 运算通常用于二进制特定位上的无条件赋值，例如一个数or 1的结果就是把二进制最末位强行变成1。如果需要把二进制最末位变成0，对这个数or 1之后再减一就可以了，其实际意义就是把这个数强行变成最接近的偶数。xor 0和1异或0都不变，异或1则取反。例：对01串 0101010之类，改变某一位上的值，只需xor 某一位，如：对有数第三位取反，只需xor 4； 对有数第三位和第二位同时取反，只需xor 6；not；not运算的定义是把内存中的0和1全部取反。.Shl 通常认为a shl 1比a * 2更快，因为前者是更底层一些的操作。因此程序中乘以2的操作请尽量用左移一位来代替。 shr;我们也经常用shr 1来代替div 2（2） 应用计算二进制中的1的个数同样假设x是一个32位整数。经过下面五次赋值后，x的值就是原数的二进制表示中数字1的个数。比如，初始时x为1314520那么最后x就变成了9，它表示1314520的二进制中有9个1。x := (x and $55555555) + (x shr 1) and $55555555); x := (x and $33333333) + (x shr 2) and $33333333); x := (x and $0F0F0F0F) + (x shr 4) and $0F0F0F0F); x := (x and $00FF00FF) + (x shr 8) and $00FF00FF); x := (x and $0000FFFF) + (x shr 16) and $0000FFFF); 为了便于解说，我们下面仅说明这个程序是如何对一个8位整数进行处理的。我们拿数字211来开刀。211的二进制为11010011。+-+-+-+-+-+-+-+-+| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | -原数+-+-+-+-+-+-+-+-+|1 0|0 1|0 0|1 0| -第一次运算后+-+-+-+-+|0 0 1 1|0 0 1 0| -第二次运算后+-+-+|0 0 0 0 0 1 0 1| -第三次运算后，得数为5+-+整个程序是一个分治的思想。第一次我们把每相邻的两位加起来，得到每两位里1的个数，比如前两位10就表示原数的前两位有2个1。第二次我们继续两两相加，10+01=11，00+10=10，得到的结果是00110010，它表示原数前4位有3个1，末4位有2个1。最后一次我们把0011和0010加起来，得到的就是整个二进制中1的个数。程序中巧妙地使用取位和右移，比如第二行中$33333333的二进制为00110011001100.，用它和x做and运算就相当于以2为单位间隔取数。shr的作用就是让加法运算的相同数位对齐。例题：玩欺诈的小杉 描述 Description 是这样的，在小杉的面前有一个N行M列的棋盘，棋盘上有N*M个有黑白棋的棋子（一面为黑，一面为白），一开始都是白面朝上。小杉可以对任意一个格子进行至多一次的操作（最多进行N*M个操作），该操作使得与该格同列的上下各2个格子以及与该格同列的左右各1个格子以及该格子本身翻面。例如，对于一个5*5的棋盘，仅对第三行第三列的格子进行该操作，得到如下棋盘（0表示白面向上，1表示黑面向上）。0010000100011100010000100对一个棋盘进行适当的操作，使得初始棋盘（都是白面朝上）变成已给出的目标棋盘的操作集合称作一个解法。小杉的任务是对给出的目标棋盘求出所有解法的总数。 输入格式 Input Format 每组测试数据的第一行有3个正整数，分别是N和M和T(1=N,M=20,1=T=5)接下来T个目标棋盘，每个目标棋盘N行，每行M个整数之前没有空格且非0即1，表示目标棋盘（0表示白面朝上，1表示黑面朝上）两个目标棋盘之间有一个空行。特别地，对于30%的数据，有1=N,Mlb then lc:=la else lc:=lb; jin:=0; for i:=1 to lc do begin x:=ai+bi+jin; ci:=x mod 10; jin:=x div 10; end; if jin0 then begin inc(lc);clc:=jin;end; for i:=lc downto 1 do write(ci); writeln; end;procedure jianfa; begin fillchar(c,sizeof(c),0); if lalb then lc:=la else lc:=lb; for i:=1 to lc do begin ci:=ci+ai-bi; if ci0) do dec(lc); for i:=lc downto 1 do write(ci); writeln; end;begin readln(s1); readln(s2); la:=length(s1); lb:=length(s2); for i:=1 to la do ai:=ord(s1la-i+1)-48; for i:=1 to lb do bi:=ord(s2lb-i+1)-48; jiafa; if (lbla)or(la=lb)and(s1lb then lc:=la else lc:=lb; for i:=1 to lc do begin x:=ai+bi+jin; ci:=x mod 100000000; jin:=x div 100000000; end; if jin0 then begin inc(lc);clc:=jin; end; gj1:=c; end;function gj2(a,b:arr;la:longint;var lc:longint):arr; var i,j,x:longint; begin for i:=1 to la do begin x:=ai-bi; if x0) do dec(la); lc:=la; gj2:=a; end;beginreadln(n); f01:=0;g01:=2; f11:=0;g11:=2; f21:=0;g21:=4; er1:=4; ler:=1; for i:=0 to 2 do begin lfi:=1;lgi:=1;end; for i:=3 to n do begin er:=gj1(er,er,ler,ler,ler); fi:=gj1(fi-1,fi-1,lfi-1,lfi-1,lfi); fi:=gj1(fi,gi-3,lfi,lgi-3,lfi); gi:=gj2(er,fi,ler,lgi); end; write(fnlfn); for i:=lfn-1 downto 1 do if fni=10000000 then write(fni) else if fni=1000000 then write(0,fni) else if fni=100000 then write(00,fni) else if fni=10000 then write(000,fni) else if fni=1000 then write(0000,fni) else if fni=100 then write(00000,fni) else if fni=10 then write(000000,fni) else write(0000000,fni);writeln; end.3.乘法procedure chengfa; var c:array1.200 of integer; i,j,lc,x:integer; cod:char; begin fillchar(c,sizeof(c),0); cod:=+; if cacb then cod:=-; for i:=1 to la do for j:=1 to lb do begin ci+j-1:=ci+j-1+ai*bj; ci+j:=ci+j+ci+j-1 div 10; ci+j-1:=ci+j-1 mod 10; end; lc:=la+lb; while (lc1)and(clc=0) do dec(lc); if cod=- then write(cod); for i:=lc downto 1 do write(ci); end;4.除法（1）计算A/B的精确值，设A，B是一般整数，计算机可接受的数，精确小数后20位。不考虑四舍五入。输入：两个数，n m输出：n/m的结果。Sample Input3 2Sample Output3/2=1.50000000000000000000var a,b,i,j,l:integer; c:array0.21 of integer;procedure prepare; begin l:=0; c0:=a div b; end;procedure gchu; begin while l20 do begin a:=(a-cl*b)*10; cl+1:=a div b; inc(l); end; end;begin readln(a,b); write(a,/,b,=); prepare; gchu; write(c0,.); for i:=1 to 20 do write(ci);end.（2）计算A/B的精确值，设A是高精度数（不超过100位），B是一般整数，计算机可接受的数，精确小数后100位。不考虑四舍五入。输入：第一行被除数n,第二行除数m输出：n/m的结果。Sample Input32Sample Output1.5var c:array1.1000 of longint; aa:string; a:array1.100 of longint; b,i,j,la,l,beg,en:longint; cho:boolean;begin cho:=false; readln(aa); readln(b); la:=length(aa); for i:=1 to la do ai:=ord(aai)-48; i:=1; while i=la do begin ci:=ai div b; ai+1:=ai+1+(ai-ci*b)*10; inc(i); end; dec(i); if ai+1=0 then cho:=true; l:=i+1; while (l-i0 do begin inc(p); ls:=copy(s,la-7,8); s:=copy(s,1,la-8); la:=length(s); val(ls,ap); end;6.应用红豆玲珑骰（mark.pas/c/cpp）【题目描述】红豆玲珑骰一共六面，每一面上有+、-、*其中之一的符号。每当骰子落下后，hh4742的两条卷轴就会自动打开，上面分别显示有一个整数。你所要做的工作，就是将这两个整数用骰子朝上的一面上显示的符号运算得出结果。【输入格式】第一行，骰子上显示的符号。第二行，一个整数a。第三行，一个整数b。（-1069=a,b1) do begin dec(la); delete(s1,1,1); end; for i:=la downto 1 do ala-i+1:=ord(s1i)-48; readln(s2); lb:=length(s2); cb:=true; if s21=- then begin cb:=false; dec(lb);delete(s2,1,1);end; while (s21=0)and(lb1) do begin dec(lb); delete(s2,1,1); end; for i:=lb downto 1 do blb-i+1:=ord(s2i)-48;end;procedure jiafa; var x,w,jin,i:integer; begin if lalb then w:=la else w:=lb; jin:=0; for i:=1 to w do begin x:=ai+bi+jin; ai:=x mod 10; jin:=x div 10; end; if jin0 then begin inc(w);aw:=jin; end; la:=w; if sign=- then write(sign); for i:=la downto 1 do write(ai); writeln; end;procedure jianfa; var jie,i,x,w:integer; cod:char; begin cod:=+; if (lalb)or(la=lb)and(s1s2) then cod:=-; if cod=- then begin h:=a;a:=b;b:=h;lh:=la;la:=lb;lb:=lh;end; jie:=0; for i:=1 to la do begin x:=jie+ai-bi; if x0 then begin jie:=-1;x:=x+10;end; ai:=x mod 10; end; if (la1)and(ala=0) then dec(la); if cod=- then write(cod); for i:=la downto 1 do write(ai); end;procedure chengfa; var c:array1.142 of integer; i,j,lc,x:integer; cod:char; begin fillchar(c,sizeof(c),0); cod:=+; if cacb then cod:=-; for i:=1 to la do for j:=1 to lb do begin ci+j-1:=ci+j-1+ai*bj; ci+j:=ci+j+ci+j-1 div 10; ci+j-1:=ci+j-1 mod 10; end; lc:=la+lb; while (lc1)and(clc=0) do dec(lc); if cod=- then write(cod); for i:=lc downto 1 do write(ci); end;beginint; sign:=+; if (fu=+)and(ca)and(cb) then jiafa; if (fu=+)and(not ca)and(not cb) then begin sign:=-;jiafa;end; if (fu=+)and(ca)and(not cb) then jianfa; if (fu=+)and(not ca)and(cb) then begin h:=a;a:=b;b:=h;lh:=la;la:=lb;lb:=lh;hs:=s1;s1:=s2;s2:=hs;jianfa; end; if (fu=-)and(ca)and(cb) then jianfa; if (fu=-)and(ca)and(not cb) then jiafa; if (fu=-)and(not ca)and(not cb) then begin h:=a;a:=b;b:=h;lh:=la;la:=lb;lb:=lh;jianfa;end; if (fu=-)and(not ca)and(cb) then begin sign:=-;jiafa;end; if fu=* then chengfa;end.（三）排序算法1. 冒泡var temp,i,j,k,n:integer; a:array1.1000of longint;begin ; readln(n); for i:=1 to n do read(ai); for i:=1 to n-1 do for j:=1 to n-i do if ajaj+1 then begin; temp:=aj; aj:=aj+1;aj+1:=temp; end;for i:=1 to n do write(ai, ); writeln;end.2. 快排（1） 不稳定procedure qs(s,t:longint); var x,i,j,h:longint; begin i:=s;j:=t; x:=a(i+j)div 2; repeat while aix do dec(j); if ij; if it then qs(i,t); if sj then qs(s,j); end;（2） 稳定procedure qs(s,t:longint); var i,j,sub:longint; x:int64; begin i:=s;j:=t; x:=a(i+j)div 2; sub:=b(i+j)div 2; repeat while (aix)or(x=ai)and(bix)or(aj=x)and(bjsub) do dec(j); if ij; if it then qs(i,t); if sj then qs(s,j); end;3堆排 背景：NOIP2004合并果子 var a:array1.10000 of longint; t,i,j,k,n,len,g1,g2:longint;procedure ins(k:longint); var s,h:longint; begin inc(len); alen:=k; s:=len; while (s1)and(as div 2as)do begin h:=as; as:=as div 2; as div 2:=h; s:=s div 2 end; end;function heap:longint; var h,fa,s:longint; sto:boolean; begin heap:=a1; a1:=alen; dec(len); fa:=1;sto:=false; while (fa*2=len) or (fa*2+1len)or(afa*2as then begin h:=afa;afa:=as;as:=h; fa:=s end else sto:=true; end; end;beginreadln(n); len:=0; t:=0; for i:=1 to n do begin read(k); ins(k); end; for i:=1 to n-1 do begin g1:=heap; g2:=heap; t:=t+g1+g2; ins(g1+g2); end;writeln(t);end. 4归并背景：求逆序对procedure msort(s,t:longint); var i,j,k,m:longint; begin if s=t then exit; m:=(s+t)div 2; msort(s,m); msort(m+1,t); i:=s;j:=m+1; k:=s; while (i=m)and(j=t) do if ai=aj then begin rk:=ai;inc(i);inc(k);end else begin inc(total,m-i+1); rk:=aj;inc(j);inc(k);end; while i=m do begin rk:=ai;inc(k);inc(i);end; while j=b then exit(a) else exit(b); end;begin readln(n,m); for i:=1 to n do readln(wi,ci); fillchar(f,sizeof(f),0); for i:=1 to n do for j:=m downto wi do fj:=max(fj-wi+ci,fj);writeln(fm);end.（2） 完全背包 var n,m,i,j:longint; w,c:array1.30 of longint; f:array0.100000 of longint;function max(a,b:longint):longint; begin if a=b then exit(a) else exit(b); end;begin readln(n,m); for i:=1 to n do readln(wi,ci); fillchar(f,sizeof(f),0); for i:=1 to n do for j:=wi to m do fj:=max(fj-wi+ci,fj);writeln(fm);end.(3)二维费用背包 背景：潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸：一个为氧气，一个为氮气。让潜水员下潜的深度需要各种的数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少？例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：3 36 12010 25 1295 50 2501 45 1304 20 119如果潜水员需要5升的氧和60升的氮则总重最小为249 （1，2或者4，5号气缸）。你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。【输入格式】第一行有2整数t，a（1=t=21，1=a=79）。它们表示氧，氮各自需要的量。第二行为整数n （1=n=1000）表示气缸的个数。此后的n行，每行包括ti，ai，wi（1=ti=21，1=ai=79，1=wi=800）3整数。这些各自是：第i个气缸里的氧和氮的容量及汽缸重量。【输出格式】仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值var f:array0.21,0.79 of longint; i,j,k,n,t,a,j1,k1:longint; ti,ai,w:array1.1000 of longint;function min(a,b:longint):longint; begin if at then j1:=t else j1:=j+tii; if k+aiia then k1:=a else k1:=k+aii; fj1,k1:=min(fj,k+wi,fj1,k1); end;writeln(ft,a);end.(4)多重背包及优化（二进制，单调队列） 若有n种物品，背包容量为m，物品体积、价值、最大使用次数为v,w,c，则朴素的动规方程为：fi=maxfi-v*k+w*k (1=k=c)。我们把所有可能达到的体积按照除以当前物品体积v的余数划分为0v-1，则当余数为k(k0,v-1)时又可以划分为k,k+v,k+2*vk+j*v（1=j=(m-k)div v）这几种具体的体积，由于对于余数为k时的转移只会发生在以上列举出的几个体积上，所以可以建立关于以上几个体积的单调队列，以便于快速地找到最优决策。但是这里要注意一点，由于这几个决策的体积和价值都不相同，直接没有可比性，所以我们把这些决策的体积统一到为k时比较，统一方法只需要利用体积为k+j*v这一特点，把需要插入队中的fk+j*v的价值减去j*w，就是当体积为k时的一个可以用于比较的“参考”价值。可以很容易想到：由于转移时，使用当前物品贡献的那一部分是二者之差，所以这与减掉j*w之前是等效的。这样，每次求fk+j*v时，只需要在队列中找到一个最优的决策fk+j*v，使得j-j=c即可，剩下的工作就只有维护单调队列了。procedure insert(x,y:longint);/插入到一个价值单调递减，使用次数单调递增的队列中 begin while (l=r)and(br=y) do dec(r); inc(r);ar:=x;br:=y; end;begin readln(n,m); /n为物品个数、m为背包容量 for i:=1 to n do beginread(v,w,c); /读
展开阅读全文