NOIP算法總結(jié) by Nap

《NOIP算法總結(jié) by Nap》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、NOIP算法總結(jié)BY.W.X吃了、還得睡（一）數(shù)論1.最大公約數(shù)，最小公倍數(shù)2.篩法求素?cái)?shù)3.mod規(guī)律公式4.排列組合數(shù)，錯(cuò)排5.Catalan數(shù)6.康拓展開7負(fù)進(jìn)制8.中位數(shù)的應(yīng)用9.位運(yùn)算（二）高精度算法1.樸素加法減法2.億進(jìn)制加法減法3.乘法4.除法5.億進(jìn)制讀入處理6.綜合應(yīng)用(三)排序算法1.冒泡2快排3堆排4歸并（四）DP1.概念2.解題步驟3.背包類DP4.線性DP5..區(qū)間動(dòng)態(tài)規(guī)劃6.坐標(biāo)型動(dòng)態(tài)規(guī)劃（規(guī)則類DP）7.資源分配型動(dòng)態(tài)規(guī)劃8.樹型動(dòng)態(tài)規(guī)劃9.狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃10

2、.動(dòng)態(tài)規(guī)劃的一般優(yōu)化方法（五）圖論1.Floyd-Warshall2.Bellman-ford3.SPFA4.dijkstra６９1.prim2.kruskal3.歐拉回路4.哈密頓環(huán)5.floodfill（求圖的強(qiáng)連通分量）6.最小環(huán)問題（基于floyd）7.Topologicalsort8.次短路9.次小生成樹（六）樹1.堆2.二叉排序樹3.最優(yōu)二叉樹（哈夫曼樹）4.求樹的后序遍歷5.并查集及應(yīng)用（七）分治1.二分查找2.二分逼近（注意精度問題）3．二分答案4．快排（見排序算法）5.歸并排序

3、（見排序算法）6.快速冪（八）貪心（九）搜索（十）其它1.離散化2.KMP3.字符串哈希4.常用字符串函數(shù)過程６９(一)數(shù)論1.最大公約數(shù)，最小公倍數(shù)functiongcd(a,b:longint):longint;beginifb=0thengcd:=aelsegcd:=gcd(b,amodb);end;functionjslcm(a,b:longint):longint;beginjslcm:=adivgcd(a,b)*b;(先div防215)end;2.篩法求素?cái)?shù)varf:array[1.

4、.10000000]ofboolean;su:array[1..100000]oflongint;sj,n,i,j:longint;beginreadln(sj);fillchar(f,sizeof(f),true);f[2]:=true;fori:=2tosjdoiff[i]thenbeginj:=i+i;whilej

5、3.mod規(guī)律公式結(jié)合律((a+b)modp+c)modp=(a+(b+c)modp)modp６９((a*b)modp*c)modp=(a*(b*c)modp)modp分配律((a+b)modp×c)modp=((a×c)modp+(b×c)modp)modp4.排列組合數(shù)，錯(cuò)排A(n,m)=n!/(n-m)!?C(n,m):=n!/m!(n-m)!錯(cuò)排通項(xiàng)f[n]:=n遞推式f[n]:=(n-1)*(f[n-

6、1]+f[n-2])(加法原理)5.Catalan數(shù)（1）公式　　?h(n)=C(2n,n)/(n+1)(n=1,2,3,...)【計(jì)算過程中可用質(zhì)因子表優(yōu)化】（2）應(yīng)用01串，出棧序列　　?對(duì)于一個(gè)二進(jìn)制的01串，共n+m位，滿足n個(gè)1，m個(gè)0，且0<=n-m<=1，該串還滿足從左向右1的個(gè)數(shù)永遠(yuǎn)大于0的個(gè)數(shù)。問：共有多少種排列方式？此題可理解為進(jìn)出棧問題，n個(gè)元素組成的隊(duì)列，共有多少種進(jìn)出棧的方式？答案是滿足卡特蘭數(shù)的，即n個(gè)元素的進(jìn)出站順序?yàn)閔（n）=c（2n，n）/（n+1）；為什么呢？

7、在2n位二進(jìn)制數(shù)中填入n個(gè)1的方案數(shù)為c(2n,n),不填1的其余n位自動(dòng)填0。從中減去不符合要求（由左而右掃描，0的累計(jì)數(shù)大于1的累計(jì)數(shù)）的方案數(shù)即為所求。h（n）=c（2n，n）-c（2n，n-1）=c（2n，n）/（n+1）；推廣：當(dāng)n<>m時(shí)，即1的個(gè)數(shù)為n，0的個(gè)數(shù)為m排列方式的總數(shù)為：c（n+m,m）-c(n+m,m-1)=c(n+m,n-1)*(n-m+1)/m;6.康拓展開functionktzk(s:string):longint;constjc:array[1..8]oflo

8、ngint=(1,2,6,24,120,720,5040,40320);vari,j,num,tem,l:longint;begin６９l:=length(s);num:=0;fori:=1tol-1dobegintem:=0;forj:=i+1toldoifs[i]>s[j]theninc(tem);num:=num+tem*jc[8-i];end;ktzk:=num;end;7.負(fù)進(jìn)制constch:array[0..19]ofchar=('0','1','2','3','4','5','6