2022年常用数学知识

1、精选学习资料 - - - 欢迎下载细心整理欢迎下载常用数学学问重要定理和公式一.常见递推关系1. fibonacci 数列a1=1; a2=1; an=an-1 + an-2;2. catalan 数：前 16 个:1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 26744409694845 在处理数据的过程中应当用到高精度） 考虑具有 n 个结点不同形状的二叉树的个数hnh 0 = 1;h n = h 0 h n-1 + h 1 h n-2 + h 2 h n-3+ h n-2 h 1+ h n-1 h 0 ;通项公式为：h

2、 n = 1/ n+1 * c n、 2n可推导出：1长度为 n 的 0-1 串中最多含 k 个 1 的例 长度为 n n<=31 的 01 串中 1 的个数小于等于l 的串组成的集合中找出按大小排序后的第i 个 01 串；2 给定序列入栈出栈后可形成的情形总数为c2n、 n c2n、n+1.精品学习资料精选学习资料 - - - 欢迎下载细心整理欢迎下载例 fjoi2000在一个列车调度站中, 2 条轨道连接到 2 条侧轨处,形成2 个铁路转轨站,如下图所示；其中左边轨道为车皮入口,右边轨道为出口；编 号为 1,2, n 的 n 个车皮从入口依次进入转轨站,由调度室 安 排 车 皮 进

3、出 栈 次 序 , 并 对 车 皮 按 其 出 栈 次 序 重 新 编 序 a1、a2、an；给定正整数n（1<=n<=300）,编程运算右边轨道最多可以得到多少个不同的车皮编序方案；例如当 n=3 时,最多得到 5 组不同的编序方案；3. 其次类 stirling 数：sn、k表示含 n 个元素的集合划分为k 个集合的情形数a. 分类：集合 an存在,就有 sn-1、k-1;不存在就 an 和放入 k 个集合中的任意一个,共 k*sn-1、k 种；sn、k= sn-1、k-1+k*sn-1、k n>k>=1 *: 求一个集合总的划分数即为sigemak=1.n sn、

4、k . 4数字划分模型*noip2001 数的划分将整数 n 分成 k 份,且每份不能为空,任意两种分法不能相同不考虑次序 ；d0、0:=1;for p:=1 to n do精品学习资料精选学习资料 - - - 欢迎下载细心整理欢迎下载for i:=p to n dofor j:=k downto 1 do incdi、j、di-p、j-1; writelndn、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.m5错位排列d1 = 0; d2 = 1;dn = n

5、-1 * dn-1 + dn-2二.图论与运算几何1度边定理：sigema di = 2*e图中全部结点的度数之和等于边数的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=sqrtp*p-a*p-b*p-c;三.数论公式1模取幂ab mod n= .a mod b*a mod b*a. mod b;2 n 的约数的个数精品学习资料精选学习资料 - - - 欢迎下载细心整理欢迎下载如 n 满意 n=

6、a1n1 * a2n2 * a3n3 * . * amnm、 就 n 约数的个数为n1+1n2+1n3+1.nm+1例题： ap 数正整数n为无穷的,但其中有些数有奇妙的性质,我们给他个名字 ap 数；对于一个数字i 他为 ap 数的充要条件为全部比他小的数的 因数个数都没有i 的因数个数多；比如6 的因数为 1 236共计有 4个因数；他就为一个ap 数（ 1-5 的因数个数不为2 就为 3）；我们题目的任务就为找到一个最大的,且不超过n 的 ap 数；四.代数1 带权中位数我国蒙古大草原上有n（n为不大于100 的自然数）个牧民定居点 p1（x1 , y1 ）.p2（x2 , y2 ）.p

7、n（ 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精品学习资料精选学习资料 - - - 欢迎下载细心整理欢迎下载同时满意上述两式的点k 即为带

8、权中位数；带权中位数问题：我们都学过中位数问题,即给定了n 个数后,位于第 n/2 的数就为中位数；所谓带权中位数,就为给定的n个数都有一个权值,或者说相当于个数； 此时的中位数就不再为第n/2 个数了,而为第 di/2 个数；而在信息学竞赛中, 有这样一类题, 给出了如干个排列在一条直线上的点,每个点有一个权值,比如说货物量.人数什么的,然后让我们 找出访全部点的货物. 人集合到一个点的总代价最小的位置；我们将会发觉,这一类问题实际上就为带权中位数问题；1. 权值为 1 的各类例题士兵站队问题问题：在一个划分成网格的操场上,n 个士兵散乱地站在网格点上；网格点由整 数坐标 x、y表 示；士兵

9、们可以沿网格边上.下.左.右移动一步,但在同一时 刻任一网格点上只能有一名士兵；根据军官的命令, 士兵们要整齐地列成一个水平队列,即排列成 x、y、x+1、y、x+n-1、y；如何挑选 x 和 y 的值才能使士兵们以最少的总移动步数排成一列；由于 x.y 方向的移动为相对独立的,所以可以各自运算两个方向的移动方案y 方向上,由于最终都要集合到一个点,可以直接求各个士兵到中间那个人的位移,为 y 方向的最小移动步数；x 方向上,并非集合到一个点,而为最终排成一条线,所以不能直接看作求中位数；由于最终必需排作一条直线, 可以先把他们看成最终排到0,1,2,3,4,.等横坐标上设他们之前坐标为x1

10、x2 x3 x4.那么他们移动的步数为c1=|x1-0| c2=|x2-1| c3=|x3-2|.易知最优的方案肯定为某个士兵不动,其他人向他靠拢,假设我们固定士兵x、 那么其他人向他靠拢,排成一列所需的步数ans=|c1-cx|+|c2-cx|+|c3-cx|.这就又回到了中位数,选取移动步数为中位数的那个士兵固定就行了；2. 权值不为一的各类例题抗震救灾（ save）精品学习资料精选学习资料 - - - 欢迎下载细心整理欢迎下载输入文件： save.in输出文件： save.out【问题描述】这场灾难发生后,国家打算设立讨论所讨论灾后重建工作,由全国各地派技 术人员来参与；由于每个地区所派

11、的技术人员数目不同,出于节省经费的问题, 所以目前仍没有打算究竟有在哪个地区设置讨论所进行讨论；假设全部地区都在一条直线上, 现在只知道每个地区与汶川的距离和该地派出技术人员的数目（激射汶川在最左端） ；请你编程帮忙他们确定在哪个地区建立讨论所可以使全部技术人员集中到该地区的费用总和最小；【输入文件】输入文件每一行描述一个地区的信息（地区数<=5000）；对于每一行,第一为该地区派出的技术人员数目,紧跟着为这个地区相对于汶川的距离,最终为该地区的名称；（技术人员数 <=100、地区的相对距离 <=1031、地区名称长度 <=20、数据保证有唯独的解）；【输出文件】输出文

12、件只需一行,即讨论所设定的地区名称；【样例输入】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 qsortl、r:longint

13、; var i1、j1、t1:longint;t、mid:extended;begini1:=l; j1:=r; mid:=bl+rdiv 2 ; repeatwhile bi1<mid do inci1;while bj1>mid do decj1; if i1<=j1 thenbegint1:=ai1; ai1:=aj1; aj1:=t1;t:=bi1; bi1:=bj1; bj1:=t;精品学习资料精选学习资料 - - - 欢迎下载细心整理欢迎下载精品学习资料精选学习资料 - - - 欢迎下载end;s:=nai1; nai1:=naj1; naj1:=s; inci1; decj1;end; until i1>j1;if l<j1 then qsortl、j1; if i1<r then qsorti1、r;精品学习资料精选学习资料 - - - 欢迎下载beginassigninput、'save.in' assignoutput、'save.out' resetinput; rewriteoutput;n:=0;while not eof do beginincn;readan、bn; readlns;while s1=' ' do deletes、1、1; n