这个叫做noip算法总结

川汉唐AFONOIP算法总结前言离NOIP还有一个星期，匆忙的把寒假整理的算法补充完善，看着当时的整理觉得那时还年少。第二页贴了几张从贴吧里找来的图片，看着就很热血的。旁边的同学都劝我不要再放PASCAL啊什么的了，毕竟我们的下一级直接学C++。即便我本人对C++也是赞赏有加，不过PASCAL作为梦的开始终究不能忘记。不像机房中其余的OIERS，我以后并不想学计算机类的专业。当年来学这个竞赛就是为了兴趣，感受计算机之美的。经过时迁，计划赶不上变化，现在尚处于迷茫之中，也很难说当时做的决定是对是错。然而我一直坚信迷茫的时候选择难走的路会看见更好的风景。这篇文章简单的说了一下NOIP考试中会常用的算法，可能难度掌握的不是太好，有一部分内容不是NOIP考查范围，然而随着难度的增加，看一些更高级的算法也没有坏处。还有一些非常非常基础的比如链表啊什么的就直接没有写上（别问我为什么整理了那么多的排序算法）。最后祝大家在NOIP中取得理想的成绩！搜索DFS框架proceduredfs(x);varbeginif达到目标状态then输出结果并退出过程;if满足剪枝条件thenexit;fori:=1to搜索宽度dobegin备份现场；（注意如果现场使用了全局变量，则需要使用局部变量备份）dfs(参数+增量)；恢复现场；end;优化（1）最优化剪枝：求最优值时，当前的状态无论如何不可能比最优值更优，则退出，可与展望结合剪枝（2）可行性剪枝：提前判断该状态是否能得到可行解，如不能则退出（3）记忆化搜索：对于已经搜索过的状态直接退出（4）改变搜索顺序：对于看起来希望更大的决策先进行搜索（5）优化搜索策略（6）预处理找到大体搜索翻译（7）改写成IDA*算法（8）卡时（注意现在联赛中禁止使用meml掐时）BFS框架初始化；把初始布局存入设首指针head=0；尾指针tail:=1；repeatinc(head)，取出队列首记录为当前被扩展结点；fori：=1to规则数do{r是规则编号}beginif新空格位置合法thenbeginif新布局与队列中原有记录不重复tail增1，并把新布局存入队尾；if达到目标then输出并退出；end；end；untilhead=tail；{队列空}优化判重的优化：hash，二叉排序树双向广搜或启发式搜索改写成A*算法二分优化排序冒泡排序vara:array[1..100]oflongint;t,n,i,j:longint;proceduresort;beginfori:=1ton-1do{与每个数都进行比较}forj:=1ton-idoifa[j]a[j+1]thenbegint:=a[j];a[j]:=a[j+1];a[j+1]:=t;end;end;选择排序vara:array[1..100]oflongint;t,n,i,j:longint;proceduresort;beginfori:=1ton-1doforj:=1+itondo{大数沉小数浮}ifa[j]a[i]thenbegint:=a[j];a[j]:=a[i];a[i]:=t;end;end;插入排序vara:array[0..100]oflongint;n,i,j,t:longint;proceduresort;beginfori:=2tondoforj:=1to(i-1)dobeginif(a[i]a[j])thenbegint:=a[j];a[j]:=a[i];a[i]:=t;end;end;end;桶排序vara,b:array[0..100]oflongint;r,i,j,t,k,n:longint;proceduresort;beginfori:=0to100dob[i]:=0;{为B数组清零，小桶内容清零}fori:=1tondob[a[i]]:=b[a[i]]+1;{桶的序号就是那个要排序的东西；出现一次，桶里得旗数加一}fori:=0to100do{扫描所有的桶}beginifb[i]0then{桶里有旗}forj:=1tob[i]dowrite(i,'');{桶的序号就是那个数}end;end;快速排序vara:array[1..100]oflongint;n,i,h,g:longint;procedurekp(l,r:longint);{变量不能与全局变量相同，否则会被抹去}varb,m,i,j,t:longint;begini:=l;j:=r;m:=a[(l+r)div2];{基准数最好从中间取}repeatwhilea[j]mdodec(j);whilea[i]mdoinc(i);{两侧的哨兵移动}ifi=jthen{哨兵未碰面}{“=”利用repeat循环的性质，使repeat循环得以结束}begint:=a[j];a[j]:=a[ia[i]:=t;{交换两个哨兵的值}inc(j);dec(j);{哨兵继续运动}end;untilij;ifjlthenkp(l,j);ifirthenkp(i,r);{都是循环不结束后进行的动作}end;beginread(n);fori:=1tondoread(a[i]);kp(1,n);{“一”位置与“N”位置}fori:=1ton-1dowrite(a[i],'');write(a[n]);{防止多输出空格使程序结果出错}end.堆排序vara:array[1..100]oflongint;n,i,b:longint;procedurejianshu(i:longint);beginwhile((a[i]a[i*2])or(a[i]a[i*2+1]))and(i=ndiv2)do{当父亲数大于子女数时并且他有孩子时进行}beginifa[i*2]=a[i*2+1]{左儿子小于右儿子}thenbeginb:=a[i*2];a[i*2]:=a[i];a[i]:=b;{左右儿子的值互换}jianshu(i*2);{继续为左儿子建树}endelsebeginb:=a[i*2+1];a[i*2+1]:=a[i];a[i]:=b;jianshu(i*2+1);{上同，不过是为右儿子建树}end;end;end;proceduretiao;beginwhilen0dobeginwrite(a[1]);a[1]:=a[n];n:=n-1;fori:=(ndiv2)downto1dojianshu(i);end;end;beginread(n);fori:=1tondoread(a[i]);fori:=(ndiv2)downto1dojianshu(i);tiao;end.数学定理中国剩余定理若有一些两两互质的整数m1,m2,…mn，则对任意的整数：a1,a2,...an，以下联立同余方程组对模数m1,m2,…mn有公解：康托展开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的整数部分。费马大定理费马大定理，又被称为“费马最后的定理”，由法国数学家费马提出。它断言当整数n2时，关于x,y,z的方程xn+yn=zn没有正整数解。被提出后，经历多人猜想辩证，历经三百多年的历史，最终在1995年被英国数学家安德鲁·怀尔斯证明。费马小定理假如a是一个整数，p是一个素数，那么ap≡a(modp)。如果a不是p的倍数，这个定理也可以写成ap-1≡1(modp)。----这个更加常用逆元由费马小定理：假如p是质数，且gcd(a,p)=1，那么ap-1≡1（modp）逆元：如果ab≡1（modp），那么在模p意义下，a、b互为逆元。所以，假如p是质数，且gcd(a,p)=1，那么a的逆元是ap-2逆元的作用：在模意义下进行除法。乘a的逆元等同于除以a。欧拉函数在数论中，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数、欧拉商数等。若m,a为正整数，且m,a互素，(gcd(a,m)=1)，则aφ(m)≡1，其中为φ(m)欧拉函数，modm为同余关系。欧拉定理实际上是费马小定理的推广。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=1s(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),1=k=p-1边界条件：S(p,p)=1,p=0S(p,0)=0,p=1递推关系的说明：考虑第p个物品，p可以单独构成一个非空集合，此时前p-1个物品构成k-1个非空的不可辨别的集合，方法数为S(p-1,k-1)；也可以前p-1种物品构成k个非空的不可辨别的集合，第p个物品放入任意一个中，这样有k*S(p-1,k)种方法。PS：第一类斯特林数和第二类斯特林数有相同的初始条件，但递推关系不同。Stirling'sapproximation快速求阶乘，不推荐用于竞赛。数论GCD&LCM//GCDfunctiongcd(a,b:longint):longint;beginifb=0thengcd:=aelsegcd:=gcd(b,amodb);end;//LCMfunctionlcm(a,b:longint):longint;beginifabthenswap(a,b);lcm:=a;whilelcmmodb0doinc(lcm,a);end;素数//单个判断functionprime(n:longint):boolean;varilongint;beginfori:=2totrunc(sqrt(n))doifnmodi=0thenexit(false)exit(true);end;//筛法打表proceduremain;vari,j:longint;beginfillchar(f,sizeof(f),true);f[0]:=false;f[1]:=false;fori:=2totrunc(sqrt(maxn))doiff[i]thenbeginj:=2*i;whilej=maxndobeginf[j]:=false;inc(j,i);end;end;end;快速幂{a^bmodn}functionf(a,b,n:int64):int64;vart,y:int64;begint:=1;y:=a;whileb0dobeginif(band1)=1thent:=t*ymodn;y:=y*ymodn;{这里用了一个很强大的技巧,y*y即求出了a^(2^(i-1))不知道这是什么的看原理}b:=bshr1;{去掉已经处理过的一位}end;exit