2022年常用数学知识

1、精心整理欢迎下载常用数学知识重要定理和公式一、常见递推关系1.fibonacci 数列a(1)=1; a(2)=1; a(n)=a(n-1) + a(n-2); 2.catalan数：前 16 个: 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 (在处理数据的过程中应该用到高精度）考虑具有 n 个结点不同形态的二叉树的个数h(n) h (0) = 1; h (n) = h (0) h (n-1) + h (1) h (n-2) + h (2) h (n-3) + h (n -2) h (1)

2、+ h (n-1) h (0) ; 通项公式为：h (n) = (1/ (n+1) * c (n, 2n) 可推导出：1长度为 n 的 0-1 串中最多含 k 个 1 的例 长度为 n (n=31)的 01 串中 1 的个数小于等于 l 的串组成的集合中找出按大小排序后的第i 个 01 串。2 给定序列入栈出栈后可形成的情况总数为c(2n, n) c(2n,n+1). 精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 1 页，共 7 页 - - - - - - - - -精心整理欢迎下载例 fjoi2000 在一个列车调度站中， 2 条轨道连接到 2

3、条侧轨处，形成 2 个铁路转轨站，如下图所示。其中左边轨道为车皮入口，右边轨道为出口。编号为 1，2， n 的 n 个车皮从入口依次进入转轨站，由调度室安 排 车 皮 进 出 栈 次 序 ， 并 对 车 皮 按 其 出 栈 次 序 重 新 编 序a1,a2, ,an。给定正整数n（1=nk=1) *:求一个集合总的划分数即为sigema(k=1.n) s(n,k) . 4数字划分模型*noip2001 数的划分将整数 n 分成 k 份，且每份不能为空，任意两种分法不能相同(不考虑顺序 )。d0,0:=1; for p:=1 to n do 精品学习资料 可选择p d f - - - - - -

4、 - - - - - - - - 第 2 页，共 7 页 - - - - - - - - -精心整理欢迎下载for i:=p to n do for j:=k downto 1 do inc(di,j,di-p,j-1); writeln(dn,k); *变形 1：考虑顺序d i, j : = d i-k, j-1 (k=1.i) *变形 2：若分解出来的每个数均有一个上限m d i, j : = d i-k, j-1 (k=1.m) 5错位排列d1 = 0; d2 = 1; dn = (n-1) * (dn-1 + dn-2) 二、图论与计算几何1度边定理：sigema di = 2*e 图

5、中所有结点的度数之和等于边数的2 倍任意一个图一定有偶数个奇点2三角形面积已知三点坐标求面积 ,s还要除以 2 |x1 y1 1| s=|x2 y2 1|=x1y2+x2y3+x3y1-x3y2-x2y1-x1y3 |x3 y3 1| *海伦公式：令 p=(a+b+c)/2, 则 s=sqrt(p*(p-a)*(p-b)*(p-c); 三、数论公式1模取幂ab mod n= (.(a mod b)*a) mod b)*a.) mod b; 2n 的约数的个数精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 3 页，共 7 页 - - - - - - -

6、 - -精心整理欢迎下载若 n 满足 n=a1n1 * a2n2 * a3n3 * . * amnm,则 n 约数的个数为(n1+1)(n2+1)(n3+1).(nm+1) 例题： ap 数正整数n 是无穷的，但其中有些数有神奇的性质，我们给他个名字ap 数。对于一个数字 i 他是 ap 数的充要条件是所有比他小的数的因数个数都没有 i 的因数个数多。比如6 的因数是 1 2 3 6 共计有 4个因数。他就是一个ap 数（1-5 的因数个数不是 2 就是 3） 。我们题目的任务就是找到一个最大的，且不超过n 的 ap 数。四、代数1 带权中位数我国蒙古大草原上有n（n 是不大于 100 的自然

7、数）个牧民定居点p1（x1，y1） 、p2（x2，y2） 、 pn（xn，yn） ，相应地有关权重为 wi，现在要求你在大草原上找一点p（xp，yp） ，使 p点到任 一点 pi 的距离 di 与 wi 之积之和为最小。即求 d=w1*d1+w2*d2+ +wi*di+ +wn*dn 有最小值结论：对 x 与 y 两个方向分别求解带权中位数，转化为一维。设最佳点 p 为点 k，则点 k 满足：令 w 为点 k 到其余各点的带权距离之和，则sigema( i=1 to k-1) wi*di = w/2 sigema( i=k+1 to n) wi*di = w/2 精品学习资料 可选择p d f

8、 - - - - - - - - - - - - - - 第 4 页，共 7 页 - - - - - - - - -精心整理欢迎下载同时满足上述两式的点k 即为带权中位数。带权中位数问题：我们都学过中位数问题，即给定了n 个数后，位于第 n/2 的数就是中位数。所谓带权中位数，就是给定的n 个数都有一个权值，或者说相当于个数。此时的中位数就不再是第n/2 个数了，而是第 di/2 个数。而在信息学竞赛中， 有这样一类题， 给出了若干个排列在一条直线上的点，每个点有一个权值，比如说货物量、人数什么的，然后让我们找出使所有点的货物、 人集合到一个点的总代价最小的位置。我们将会发现，这一类问题实际上

9、就是带权中位数问题。1、 权值为 1 的各类例题士兵站队问题问题：在一个划分成网格的操场上，n 个士兵散乱地站在网格点上。网格点由整数坐标 (x,y) 表 示。士兵们可以沿网格边上、下、左、右移动一步，但在同一时刻任一网格点上只能有一名士兵。按照军官的命令， 士兵们要整齐地列成一个水平队列，即排列成 (x,y),(x+1,y),(x+n-1,y)。如何选择 x 和 y 的值才能使士兵们以最少的总移动步数排成一列。由于 x、y 方向的移动是相对独立的，所以可以各自计算两个方向的移动方案y 方向上，由于最后都要聚集到一个点，可以直接求各个士兵到中间那个人的位移，为 y 方向的最小移动步数。x方向上

10、，并非聚集到一个点，而是最后排成一条线，所以不能直接看作求中位数。由于最终必须排作一条直线， 可以先把他们看成最终排到0， 1， 2， 3， 4， .等横坐标上设他们之前坐标为x1 x2 x3 x4 .那么他们移动的步数为c1=|x1-0| c2=|x2-1| c3=|x3-2| .易知最优的方案一定是某个士兵不动，其他人向他靠拢，假设我们固定士兵x, 那么其他人向他靠拢，排成一列所需的步数ans=|c1-cx|+|c2-cx|+|c3-cx| .这就又回到了中位数，选取移动步数为中位数的那个士兵固定就行了。2、 权值不为一的各类例题抗震救灾（ save ）精品学习资料 可选择p d f -

11、- - - - - - - - - - - - - 第 5 页，共 7 页 - - - - - - - - -精心整理欢迎下载输入文件： save.in输出文件： save.out【问题描述】这场灾难发生后，国家决定设立研究所研究灾后重建工作，由全国各地派技术人员来参加。因为每个地区所派的技术人员数目不同，出于节约经费的问题，所以目前还没有决定到底有在哪个地区设置研究所进行研究。假设所有地区都在一条直线上， 现在只知道每个地区与汶川的距离和该地派出技术人员的数目（激射汶川在最左端） 。请你编程帮助他们确定在哪个地区建立研究所可以使所有技术人员集中到该地区的费用总和最小。【输入文件】输入文件每一

12、行描述一个地区的信息（地区数=5000）。对于每一行，首先是该地区派出的技术人员数目，紧跟着是这个地区相对于汶川的距离，最后是该地区的名称。（技术人员数 =100,地区的相对距离 =1031,地区名称长度 =20,数据保证有唯一的解）；【输出文件】输出文件只需一行，即研究所设定的地区名称。【样例输入】7 9289 shengyan5 8523 beijing3 5184 guilin8 2213 chongqing10 0 wuhan【样例输出】chongqing首先将其按距离从左到右排序，把人数视为点的权值。找出中间那个人所在的城市就行了。program fdfgd;var n,i,j,x,tot:longint;a:array1.5000 of longint;b:array1.5000 of extended;na:array1.5000 of string;s:string;procedure qsort(l,r:longint);var i1,j1,t1:longint;t,mid:extended;begini1:=l; j1:=r; mid:=b(l+r)div 2 ;repeatwhile bi1mid do dec(j1);if i1j1;if lj1 then qsort(l,j1);if i1=(tot div 2) then