这个叫做noip算法总结
- 格式：pdf
- 大小：3.02 MB
- 文档页数：96
川汉唐AFO NOIP算法总结前言离NOIP还有一个星期，匆忙的把寒假整理的算法补充完善，看着当时的整理觉得那时还年少。
第二页贴了几张从贴吧里找来的图片，看着就很热血的。
旁边的同学都劝我不要再放PASCAL啊什么的了，毕竟我们的下一级直接学C++。
即便我本人对C++也是赞赏有加，不过PASCAL作为梦的开始终究不能忘记。
不像机房中其余的OIERS，我以后并不想学计算机类的专业。
当年来学这个竞赛就是为了兴趣，感受计算机之美的。
经过时迁，计划赶不上变化，现在尚处于迷茫之中，也很难说当时做的决定是对是错。
然而我一直坚信迷茫的时候选择难走的路会看见更好的风景。
这篇文章简单的说了一下NOIP考试中会常用的算法，可能难度掌握的不是太好，有一部分内容不是NOIP考查范围，然而随着难度的增加，看一些更高级的算法也没有坏处。
还有一些非常非常基础的比如链表啊什么的就直接没有写上（别问我为什么整理了那么多的排序算法）。
最后祝大家在NOIP中取得理想的成绩！搜索DFS框架procedure dfs(x);varbeginif达到目标状态then输出结果并退出过程;if满足剪枝条件then exit;for i:=1to搜索宽度dobegin备份现场；（注意如果现场使用了全局变量，则需要使用局部变量备份）dfs(参数+增量)；恢复现场；end;优化（1）最优化剪枝：求最优值时，当前的状态无论如何不可能比最优值更优，则退出，可与展望结合剪枝（2）可行性剪枝：提前判断该状态是否能得到可行解，如不能则退出（3）记忆化搜索：对于已经搜索过的状态直接退出（4）改变搜索顺序：对于看起来希望更大的决策先进行搜索（5）优化搜索策略（6）预处理找到大体搜索翻译（7）改写成IDA*算法（8）卡时（注意现在联赛中禁止使用meml掐时）BFS框架初始化；把初始布局存入设首指针head=0；尾指针tail:=1；repeatinc(head)，取出队列首记录为当前被扩展结点；for i：=1to规则数do{r是规则编号}beginif新空格位置合法thenbeginif新布局与队列中原有记录不重复tail增1，并把新布局存入队尾；if达到目标then输出并退出；end；end；until head>=tail；{队列空}优化判重的优化：hash，二叉排序树双向广搜或启发式搜索改写成A*算法二分优化排序冒泡排序var a:array[1..100]of longint;t,n,i,j:longint;procedure sort;begin for i:=1to n-1do{与每个数都进行比较}for j:=1to n-i doif a[j]>a[j+1]thenbegint:=a[j];a[j]:=a[j+1];a[j+1]:=t;end;end;选择排序var a:array[1..100]of longint;t,n,i,j:longint;procedure sort;begin for i:=1to n-1dofor j:=1+i to n do{大数沉小数浮}if a[j]>a[i]thenbegint:=a[j];a[j]:=a[i];a[i]:=t;end;end;插入排序var a:array[0..100]of longint;n,i,j,t:longint;procedure sort;begin for i:=2to n dofor j:=1to(i-1)dobeginif(a[i]<a[j])thenbegint:=a[j];a[j]:=a[i];a[i]:=t;end;end;end;桶排序var a,b:array[0..100]of longint;r,i,j,t,k,n:longint;procedure sort;begin for i:=0to100do b[i]:=0;{为B数组清零，小桶内容清零}for i:=1to n do b[a[i]]:=b[a[i]]+1;{桶的序号就是那个要排序的东西；出现一次，桶里得旗数加一}for i:=0to100do{扫描所有的桶}beginif b[i]<>0then{桶里有旗}for j:=1to b[i]do write(i,'');{桶的序号就是那个数}end;end;快速排序var a:array[1..100]of longint;n,i,h,g:longint;procedure kp(l,r:longint);{变量不能与全局变量相同，否则会被抹去} var b,m,i,j,t:longint;begini:=l;j:=r;m:=a[(l+r)div2];{基准数最好从中间取}repeatwhile a[j]>m do dec(j);while a[i]<m do inc(i);{两侧的哨兵移动}if i<=j then{哨兵未碰面}{“=”利用repeat循环的性质，使repeat循环得以结束}begint:=a[j];a[j]:=a[ia[i]:=t;{交换两个哨兵的值}inc(j);dec(j);{哨兵继续运动}end;until i>j;if j>l then kp(l,j);if i<r then kp(i,r);{都是循环不结束后进行的动作}end;beginread(n);for i:=1to n do read(a[i]);kp(1,n);{“一”位置与“N”位置}for i:=1to n-1do write(a[i],'');write(a[n]);{防止多输出空格使程序结果出错}end.堆排序var a:array[1..100]of longint;n,i,b:longint;procedure jianshu(i:longint);beginwhile((a[i]>a[i*2])or(a[i]>a[i*2+1]))and(i<=n div2)do{当父亲数大于子女数时并且他有孩子时进行}beginif a[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;procedure tiao;beginwhile n<>0dobeginwrite(a[1]);a[1]:=a[n];n:=n-1;for i:=(n div2)downto1dojianshu(i);end;end;beginread(n);for i:=1to n doread(a[i]);for i:=(n div2)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的整数部分。
费马大定理∙费马大定理，又被称为“费马最后的定理”，由法国数学家费马提出。
它断言当整数n>2时，关于x,y,z的方程xn+yn=zn没有正整数解。
∙被提出后，经历多人猜想辩证，历经三百多年的历史，最终在1995年被英国数学家安德鲁·怀尔斯证明。
费马小定理假如a是一个整数，p是一个素数，那么ap≡a(mod p)。
如果a不是p的倍数，这个定理也可以写成ap-1≡1(mod p)。
----这个更加常用逆元由费马小定理：假如p是质数，且gcd(a,p)=1，那么ap-1≡1（mod p）逆元：如果ab≡1（mod p），那么在模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)欧拉函数，mod m 为同余关系。
欧拉定理实际上是费马小定理的推广。
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)种方法。
