NOIP NOI知识点与部分标程.doc

目录Contents第一章 基本算法与数论GCD & 扩展欧几里德算法筛法求素数欧拉函数Gauss消元法 第二章 数据结构Trie树后缀数组并查集树状数组RMQ ST算法KMP算法、扩展KMP第三章 图论求无向图割顶和桥欧拉路拓扑排序最小生成树二分图匹配 匈牙利算法带上下界的网络流第四章 计算几何凸包第五章 经典算法+代码1.Nim（Nim取子问题）2. Tarjin（强连通分量）3. Euler Function（欧拉函数）4. Differential restraint system（约分差数系统）5. Simulated Annealing Algorithme（模拟退火算法）6. the Stable Marriage System (稳定婚姻系统)7. Burnside Theore、Polya Counting（Burnside定理，Polya计数法）8. Splay、SBT（二叉平衡树）9. Netflow+SAP+GAP+Muti-Augment（网络流+各种优化）10. KM Agorithem（KM最大权完美匹配）11. Costflow（费用流）第一章 基本算法与数论 1. GCD & 扩展欧几里德算法Function gcd(a,b:longint):longint; BeginIf a=0 then exit(b) Else exit(b mod a,a); End;扩展欧几里德算法：扩展欧几里德算法是用来在已知a, b求解一组x，y使得a*x+b*y=Gcd(a,b)(解一定存在，根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中。求a * x + b * y = n的整数解。1、先计算Gcd(a,b)，若n不能被Gcd(a,b)整除，则方程无整数解；否则，在方程两边同时除以Gcd(a,b)，得到新的不定方程a * x + b * y = n，此时Gcd(a,b)=1;2、利用下面所说的欧几里德算法求出方程a * x + b * y = 1的一组整数解x0,y0，则n * x0,n * y0是方程a * x + b * y = n的一组整数解；3、根据数论中的相关定理，可得方程a * x + b * y = n的所有整数解为： x = n * x0 + b * ty = n * y0 - a * t (t为整数)上面的解也就是a * x + b * y = n 的全部整数解。欧几里德算法推导：设 ab。1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；2，ab0 时 设 ax1+by1=gcd(a,b); bx2+(a mod b)y2=gcd(b,a mod b);根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);则:ax1+by1=bx2+(a mod b)y2;即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;根据恒等定理得：x1=y2; y1=x2-(a/b)*y2;这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。欧几里德算法代码：function gcd(a,b:int64):int64;var tmp:longint;begin if b=0 then begin x:=1; y:=0; gcd:=a; exit; end; gcd:=gcd(b,a mod b); tmp:=x; x:=y; y:=tmp-y*(a div b);end;2. 筛法求素数 begin fillchar(p,sizeof(p),true); /判断是否为素数的数组，maxn为要求判断的上界 p1:=false; for i:=1 to maxn do if pi then begin j:=i+i; while j=maxn do begin pj:=false; inc(j,i); end; end;end.3. 欧拉函数求不大于n的自然数中共有多少个和n互质。公式：设（其中,是互不相同的质数）。则：可使用求解代码：begin fillchar(pri,sizeof(pri),true); pri1:=false; /pri数组为判断是否为素数 for i:=2 to maxn do /maxn为上界 if prii then begin j:=i+i; while j=maxn do begin prij:=false; j:=j+i; end; end; for i:=1 to maxn do /eul数组表示不大于n的自然数中共有多少个和n互质 euli:=i; for i:=1 to maxn do if prii then begin j:=i; while jmatrixi,i then begin temp:=matrixi; matrixi:=matrixj; matrixj:=temp; end; for j:=i+1 to n do begin m:=matrixj,i/matrixi,i; matrixj,i:=0; for k:=i+1 to n+1 do matrixj,k:=matrixi,k*m-matrixj,k; end; end;xn:=matrixn,n+1/matrixn,n; / 回代过程 for i:=n-1 downto 1 do begin m:=0; for j:=i+1 to n do m:=m+matrixi,j*xj; xi:=(matrixi,n+1-m)/matrixi,i; end; for i:=1 to n do writeln(xi:0:2);end.第二章 数据结构1.Trie树 Trie树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。代码(建立trie树)：procedure make(l:string;);var j:longint;begin p:=0; for j:=1 to length(l) do begin if ap,ljn then begin t:=i-1; break; end; end; for j:=1 to t do for i:=1 to n do begin if fi,j-1fi+ej-1,j-1 then fi,j:=fi,j-1 else fi,j:=fi+ej-1,j-1; if gi,j-1fr-ek+1,k then max:=fl,k else max:=fr-ek+1,k; if gl,k1,则说明图中出度为0的点大于等于2，又由于缩点后的图中不可能存在环（与连通分支不符），故出度为0的点不可以互相到达，即图不连通，则输出0（没有牛被所有牛崇拜）,如果num=1,则说明图中只有一个出度为0的点，则该点（连通分支）所含顶点的个数即为输出结果（被所有牛崇拜的牛的个数）。 代码：program p2186;var i,j,n,m,top,time,sum,ans:longint; a,b,d:array0.50000of longint; dfn,low,que,s,h,ou:array0.10000of longint; pd:array1.10000of boolean;procedure kp(l,r:longint);var i,j,x,t:longint;begin i:=l;j:=r;x:=a(i+j)div 2; repeat while aix do dec(j); if i=j; if lj then kp(l,j); if ir then kp(i,r);end;procedure tarjan(u:longint);var i:longint;begin pdu:=true; inc(top); quetop:=u; inc(time); dfnu:=time; lowu:=time; for i:=du-1+1 to du do if dfnbi=0 then begin tarjan(bi); if lowbilowu then lowu:=lowbi; end else if(pdbi)and(dfnbilowu)then lowu:=dfnbi; if lowu=dfnu then begin inc(s0); while quetopu do begin hquetop:=s0; inc(ss0); pdquetop:=false; quetop:=0; dec(top); end; hquetop:=s0; inc(ss0); pdquetop:=false; quetop:=0; dec(top); end;end;begin assign(input,p2186.in);reset(input); assign(output,p2186.out);rewrite(output); readln(n,m); for i:=1 to m do readln(ai,bi); kp(1,m); for i:=2 to m do if aiai-1 then dai-1:=i-1; dam:=m; for i:=2 to n do if di=0 then di:=di-1; fillchar(pd,sizeof(pd),false); time:=0; top:=0; for i:=1 to n do if dfni=0 then tarjan(i); for i:=1 to m do if haihbi then inc(ouhai); for i:=1 to s0 do if oui=0 then begin inc(sum);ans:=si; end; if sum=1 then writeln(ans) else writeln(0); close(input);close(output);end.3. Euler Function（欧拉函数）讲解：习题：POJ2773 题目大意：给出n和k求出第k个与n互素的数 思路：若是知道欧几里德算法的话就应当知道gcd（bt+a，b）=gcd（a，b） （t为随便率性整数）则若是a与b互素，则bt+a与b也必然互素，若是a与b不互素，则bt+a与b也必然不互素，故与m互素的数对m取模具有周期性，则按照这个办法我们就可以很快的求出第k个与m互素的数。假设小于m的数且与m互素的数有k个，此中第i个是ai，则第mk+i与m互素的数是km+ai 代码：program p2773;const maxn=1000000;var i,j,n,m,k:longint; ans:int64; pri:array1.maxnof boolean; eul:array1.maxnof longint;procedure init;begin fillchar(pri,sizeof(pri),true); pri1:=false; for i:=2 to maxn do if prii then begin j:=i+i; while j=maxn do begin prij:=false; j:=j+i; end; end; for i:=1 to maxn do euli:=i; for i:=1 to maxn do if prii then begin j:=i; while j=maxn do begin eulj:=(eulj div i)*(i-1); j:=j+i; end; end;end;function gcd(a,b:longint):longint;begin if b=0 then exit(a) else exit(gcd(b,a mod b);end;procedure main;begin while not(eof) do begin readln(m,k); n:=k div eulm; k:=k mod eulm; if k=0 then begin dec(n);k:=eulm; end; for i:=1 to m do if gcd(m,i)=1 then begin dec(k); if k=0 then begin ans:=n*m+i; writeln(ans); /writeln(n*m+i); break; end; end; end;end;begin assign(input,p2773.in);reset(input); assign(output,p2773.out);rewrite(output); init; main; close(input);close(output);end.4. Differential restraint system（约分差数系统）讲解：习题：POJ3159 题目大意:给n个人派糖果，给出m组数据，每组数据包含A，B，c 三个数，意思是A的糖果数比B少的个数不多于c,即B的糖果数 - A的糖果数= c 。最后求n 比 1 最多多多少糖果。 思路：这是一题典型的差分约束题。不妨将糖果数当作距离，把相差的最大糖果数看成有向边AB的权值，我们得到 disB-disAdisA+w(A,B), disB=disA+w(A,B)。即是满足题中的条件disB-disA=w(A,B），由于要使disB 最大，所以这题可以转化为最短路来求。这题如果用SPFA 算法的话，则需要注意不能用spfa+queue 来求,会TLE ，而是用 spfa + stack。 代码：program p3159;var i,j,n,m:longint; a,b,c,d:array0.150000of longint; dist:array1.30000of int64;procedure kp(l,r:longint);var i,j,x,t:longint;begin i:=l; j:=r; x:=a(i+j)div 2; repeat while aix do dec(j); if i=j; if lj then kp(l,j); if i0 do begin /inc(t); x:=qtop; qtop:=0; dec(top); for i:=dx-1+1 to dx do if distbidistx+ci then begin distbi:=distx+ci; if not pdbi then begin inc(top); qtop:=bi; pdbi:=true; end; end; pdx:=false; end;end;begin assign(input,p3159.in);reset(input); assign(output,p3159.out);rewrite(output); readln(n,m); for i:=1 to m do readln(ai,bi,ci); kp(1,m); for i:=1 to m do if aiai-1 then dai-1:=i-1; dam:=m; for i:=1 to m do if ai=0 then ai:=ai-1; SPFA; writeln(distn); close(input);close(output);end.5. Simulated Annealing Algorithme（模拟退火算法）讲解：习题：POJ2420 题目大意： 思路：在坐标平面内寻找一点,使得它到所有给定定点的距离和最小,输出这个最小距离。 代码：使用模拟退火,从任意点(x,y)出发,上下左右分别走T的距离,更新最优解,不能更新时降温。program p2420;var i,j,n:longint; step,x1,y1,x2,y2,xt,yt,ans,t:real; p:boolean; x,y:array1.100of integer;function dist(i:longint):real;begin dist:=sqrt(sqr(x2-xi)+sqr(y2-yi);end;function all:real;var i:longint;begin all:=0; for i:=1 to n do all:=all+dist(i);end;begin assign(input,p2420.in);reset(input); assign(output,p2420.out);rewrite(output); readln(n); for i:=1 to n do readln(xi,yi); x1:=xn;y1:=yn; x2:=xn;x2:=yn; step:=100; ans:=all; while step0.1 do begin p:=true; while p do begin p:=false; xt:=x1; yt:=y1; x2:=x1+step; y2:=y1; t:=all; if tans then begin p:=true; ans:=t; xt:=x2; yt:=y2; end; x2:=x1; y2:=y1+step; t:=all; if tans then begin p:=true; ans:=t; xt:=x2; yt:=y2; end; x2:=x1-step; y2:=y1; t:=all; if tans then begin p:=true; ans:=t; xt:=x2; yt:=y2; end; x2:=x1; y2:=y1-step; t:=all; if t=ww; for i:=1 to n do bwpi:=i; for i:=1 to n do begin for ch:=a to z do if mach=i then begin write(ch, );break; end; for ch:=A to Z do if woch=bi then begin writeln(ch);break; end; end; if pv then writeln; end; close(input);close(output);end.7. Burnside Theore、Polya Counting（Burnside定理，Polya计数法）讲解：习题：POJ1286 题目大意：给你n颗珠子，将这n颗珠子围成一个圈形成一串项链，然后对每个珠子涂上红色、蓝色和绿色中的一种。如果两种涂色方法可以通过旋转项链得到。那么这两种涂色方法视为一种。如果两种涂色方法可以通过一个对称轴反映得到，那么这两种涂色方法也视为一种。问有多少种不同的涂色方法。 思路：polya计数。对于每一种旋转置换f，计算出C(f)(C(f) = gcd(n,i),i为置换f每次旋转的步数)。对于n种反射置换，则需要分两种情况，当n为偶数时着色方法为(3(n/2)+3(n/2 + 1)*(n/2)；当n为奇数时，着色方法为n*(3(n/2 + 1),将所有的方法数加起来/(2*n)即为结果。 代码:program p1286;var i,j:longint; n,ans,t,p:int64;function gcd(a,b:longint):longint;begin if a=0 then exit(b) else exit(gcd(b mod a,a);end;procedure main;begin ans:=0; if n=0 then exit; for i:=1 to n do begin t:=gcd(i,n); p:=1; for j:=1 to t do p:=p*3; ans:=ans+p; end; if n and 1=1 then begin p:=n; for i:=1 to (n shr 1)+1 do p:=p*3; inc(ans,p); en