文档介绍：、还得睡(一),,(二)高精度算法朴素加法减法亿进制加法减法乘法除法亿进制读入处理综合应用(三)(四)(规则类DP)资源分配型动态规划树型动态规划状态压缩的动态规划动态规划的一般优化方法(五)图论Floyd-WarshallBellman-fordSPFAdijkstraprimkruskal欧拉回路哈密顿环floodfill(求图的强连通分量)最小环问题(基于floyd)Topologicalsort次短路次小生成树(六)(哈夫曼树)(七)(注意精度问题)(见排序算法)(见排序算法)(八)贪心(九)搜索(十)其它离散化KMP字符串哈希常用字符串函数过程(一)数论最大公约数,最小公倍数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;:array[1..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<sjdobeginf[j]:=false;j:=j+i;end;end;fori:=2tosjdoiff[i]thenbegininc(n);su[n]:=i;end; ((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)modp资料个人收集整理,,错排A(n,m)=n!/(n-m)! C(n,m):=n!/m!(n-m)!错排通项f[n]:=n递推式f[n]:=(n-1)*(f[n-1]+f[n-2])(加法原理)(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);推广:当n<>m时,即1的个数为n,0的个数为m排列方式的总数为:c(n+m,m)-c(n+m,m-1)=c(n+m,n-1)*(n-m+1)/m;资料个人收集整理,(s:string):longint;constjc:array[1..8]oflongint=(1,2,6,24,120,720,5040,40320);资料个人收集整理,勿做商业用途vari,j,num,tem,l:longint;beginl:=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;:array[0..19]ofchar=('0','1','2','3','4','5','6','7','8','9','A','