当前位置:首页 >> 学科竞赛 >>

day1数学方法noip培训


数学类问题
? 精度处理(高精度、实数处理 瓷片项链)
? 进制问题(特定二进制串的统计、二分查 找、利用二进制进行路径、状态描述、二 进制转换 k进制数) ? 递推与递归关系(递推关系式、通项公式、 数列、博弈问题 整数分划问题)

数学类问题
? 数位、数字、特定数值的查找、统计(数值 处理与质因子分解 反素数) ? 数学杂

题(回文数字、约瑟夫与反约瑟夫问 题 聪明的农民) ? 数学应用(无解判定、解线性方程组、矩阵 处理、限定搜索范围 Gauss消元) ? 组合数学问题(Fibonacci数列、卡特兰数、 POLYA原理、排列组合计数、加法原理与 乘法原理 极值问题 电子锁) ? 数学构造

数学类问题的思维过程
– 相关公式、定理、原理的应用 – 寻找规律、归纳整理递归与递推关系式 – 按照数学方法构造、二进制转化等技巧性处理 – 注意事项:
? 规律准确(小数据手工推算、搜索程序验证) ? 数据类型是否合理、数据范围是否超界(大数据处 理)

瓷片项链
? 给定泥土总体积V总和烧制时的损耗V0以及 瓷片直径D和体积V的关系,求能获得最长 项链的瓷片数。 ? D和V的关系是 ? D=0.3*SQR(V-V0) (V>V0) ? D=0 (V<=V0)

分析
? 完全按照题目的描述进行计算 ? repeat ? inc(i); ? each:=v/i; ? if v<=v0*i then break; ? d:=0.3*sqrt(each-v0)*i; ? until false;

? 判断时去掉开方运算,即同时平方。 ? repeat ? inc(i); ? each:=v/i; ? if v<=v0*i then break; ? d:=0.3*0.3*(each-v0)*i*i; ? until false;

? 判断时去掉开方运算和除法运算。 ? d=03*0.3*(v/I-v0)*I*I=0.3*0.3*I*(v-v0*I),0.3 为常数,判断时可以舍去。 ? repeat ? inc(i); ? if v<=v0*i then break; ? d:=0.3*0.3*i*(v-v0*i); ? until false;

K进制数(Number)
? 一个合法的n位K进制数定义如下: 它是一个首位不为0的K进制数。 它不包含连续的两个0。 ? 任务:对于输入的K,n。求出满足上述条件的K进制数个数。 ? 输入(number.in) ? 只有一行:N, K ? 输入(number.out) ? 输出文件只有一个数字,即满足条件的N位K进制数总个数 ? 数据说明 ? 2<=K<=50, 2<=n<=1800 ? 输入输出示例: ? Number.in ? 2 2 ? Number.out ? 2

分析
? ? ? ? 用f[i]表示i位(最高位是第i位)K进制数的总数,那么就有: f[i]=(f[i-1]+f[i-2])*(K-1) 怎么解释这个方程呢? f[i]也就是i位K进制数的总数应该等于:第i-1位为0与第i-1位不 为0的情况的和乘以第i位的情况数(1..k-1) ? >第i-1位为0的情况应该等于i-2位不为0的情况总数,即f[i-2] ? >第i-1位不为0的情况应该等于f[i-1] ? 所以f[i]=(f[i-1]+f[i-2])*(k-1)

整数划分问题(一)
最优分解方案 将一个整数n分成若干个互不相同的数的和 ,使得这些数的乘积最大。其中 1<=n<=1000。

分析
? 初看此题,最容易相到的算法是搜索,但 此题的n最大可以达到1000,搜索肯定会 超时,而本题所给的限制条件也不多,即 便是加上一些剪枝也起不到很好的效果。 一般遇到这种情况我们可以从简单的数据 分析起。

? 在解一些问题的时候(特别是用数学方法解的 问题),当我们无从解决时,可以从简单的数 据考虑起,以便发现其中的一些规律,这种作 法对解题是很有帮助的。 ? n 分解方案 MUL 5 2,3 6 ? 6 2,4 8 ? 7 3,4 12 ? 8 3,5 15 ? 9 2,3,4 24

? 观察这几组数据,不难发现所有的分解方案的数的个 数都等于n可以分出的最多个数,其实我们并不难想 到,要想使乘积最大,应尽量使分得的数多。 ? 另一方面,我们在初中数学中就已经证明过当数(正 数)的和相等时,数的差越小,数的积也就越大,因 此我们可以在分的数的个数最多的情况下使数之间的 差尽量小,这样得出来的方案必定是最优的。

整数分划(二)
例题2:若干个正整数之和为n,其中: n<2000,试求它们乘积的最大值以及该最大 值的位数k。

分析
根据数学规律可知,若要使和固定的数的乘积最大,必须使 这些数尽可能的多为3,于是可推得以下规律:

? ? ?

当N mod 3=1 时,N可分解为一个4和若干个3的和; 当N mod 3=2 时,N 可分解为一个2和若干个3的和; 当N mod 3=0 时,N 直接分解为若干个3的和。 按照这一分解方法,所有因数的乘积必定最大。

注意:因N 的最大值可达2000,乘积将超过长整型数据范围,
所以需用高精度运算。

整数分划的方案总数
? 把一个正整数N表示成如下表达式的一系列 正整数的和,叫做整数N的一个分划。某个 正整数N的不同表达式的个数称做整数N的分 划数。编程计算指定正整数的分划数。 ? N=n1+n2+…+nk Nj>=1,j=1,2,……, k,k>=1 1<=n1<=n2<=…<=nk ? 输入正整数N(N<=100),输出N的分划 数。

分析
? 在求解整数N的分划数时,设分解方案(表达 式)中最大可以分解的整数因子nj的值最大不 超过m,用F(N,m)记录N被划分成不超过 m的整数的方案总数,通过数学分析,容易得 到一个递归定义的递推关系式:

?

1

(m=1)

? F(N,m)= F(N-m,m)+F(N,m-1) (m>1,m<=N) ? F(N,N) (m>N) ? 初始(边界条件)为F(0,m)=1 (m>0) ? 目标状态为F(N,N)。

反素数
? 正整数 n是一个Antiprime数,如果这个数的约数个数超过 比n小的任何数的约数个数。例如:下列Antiprime数1,2, 4,6,12和24。编程求解不超过n的最大的Antiprime数。 【输入】: 在输入文件ANT.IN有一个整数n。1≤n≤2000000000 【输出】: 输出文件ANT.OUT应该有一个正整数:不超过n的最大 Antiprime数。

? ? ? ?

分析
? 见文档

极值问题(最高时限15s)
已知m、n为整数,且满足下列两个条件: ① m、n∈1,2,…,K?,(1≤K≤109) ② (n 2-mn-m2)2=1 编一程序,由键盘输入K,求一组满足上述两个条 件的m、n,并且使m2+n2的值最大。例如,若K= 1995,则m=987,n=1597,则m、n满足条件, 且可使m2+n2的值最大。

【分析】方法一 从初等数学的角度考虑: 由条件②(n 2-mn-m2)2=1得出: n 2-mn-m2 + 1 = 0 n 2-mn-m2-1 = 0 根据求根公式 N1,2=(m+△1,2)/2 n3,4=(m-△1,2)/2 其中: △1=sqrt(5*m2+4); △2=sqrt(5*m2-4);

【分析】再考虑条件①。由于n>1,因此排除了n3 和n4存在的可能性. 又由于n和m是整数,因此△1和△2应为整数。 由于m2+n2单调递增,从m=k出发,按递减方向将 m值代入n的求根公式。 只要△1(或△2)为整数、n1(或n2)为整数且小于 k,则得出的一组m和n一定使 m2+n2的值最大。

【算法描述】
m←k; while m≥i do begin 求△1 if △1为整数 then begin 求n1; if (n1为整数) and (n1≤k) Then begin 输出m和n1;halt; end end; {then} 求△2; if △2为整数 then begin 求n2; if(n2为整数)and(n2≤k) then begin 输出m和n2; halt; end end;{then} m←m-l; end;{while}

上述算法从数学意义上来说,是一定可以 出得出正确解的。但是该算法疏漏了一个 重要条件 ── 1≤k≤109 。如果K值超过105, 上述算法不可能在限定的15秒内出解。

【分析】方法二 分析小数据会发现:m,n是Fibonacci数列的相邻两项。 因为: (n 2-mn-m2)2 =1 故: ( m2 + mn- n 2 )2 =1 又: m 2+mn-n2=(m+n)2-mn-2n2 =(m+n)2-(m+n)n-n2 故: (m2+mn-n2)2=[(m+n)2-(m+n)n-n2]2 即: (n2-mn-m2)2=[(m+n)2-(m+n)n-n2]2

【分析】由上述数学变换式可以得出,如果m和n为 一组满足条件①和条件②的解,设n’=m+n,m ’=n 那么n’,m ’也是一组满足条件①和条件②的一组解。 将所有满足条件①和条件②的m和n 按递增顺序排成 一个Fibomacci数列 {1,1,2,3,5,8,……} 数列中小于k的最大两个相邻数即为试题所要求的一 组m和n。 算法:利用Fibomacci数列顺推m,n,求出在条件范围 内的m,n最大值,此时m2+n2的值最大。

Gauss消元示例
? 2x1+x2-x3=-1 ? X1+x2+x3=2 ? X1-x2+2x3=6

Kathy函数(HNCOI)
?Tiger非常喜欢数学,所以他参加了学校组织的数 学课外兴趣小组。在兴趣小组的学习当中,老师向 Tiger介绍了Kathy函数,Kathy函数是这样定义的: ?

f (1) ? 1

f (3) ? 3 f ( 2n ) ? f ( n ) f (4n ? 1) ? 2 f (2n ? 1) ? f (n) f (4n ? 3) ? 3 f (2n ? 1) ? 2 f (n)

Kathy函数(HNCOI)
? Tiger对Kathy函数产生了浓厚的兴趣,他通过 研究发现有很多的数n都满足f(n)=n,对于一个给定的 数m,他希望你求出所有的满足f(n)=n (n<=m)的自 然数n的个数,其中m<=10100。

组合计数

Catalan数
定义:一个凸n边形通过不相交于n边形内部 的对角线把n边形拆分成若干三角形的不同 拆分数。

分析
? 设Cn表示凸n边形的拆分方案总数。由题目中的要求可知一个 凸n边形的任意一条边都必然是一个三角形的一条边,边P1 Pn 也不例外,再根据“不在同一直线上的三点可以确定一个三 角形”,只要在P2,P3,……,Pn-1点中找一个点Pk(1<k<n), 与P1、Pn 共同构成一个三角形的三个顶点,就将n边形分成 了三个不相交的部分(如图3所示),我们分别称之为区域①、 区域②、区域③,其中区域③必定是一个三角形,区域①是 一个凸k边形,区域②是一个凸n-k+1边形。
P2 ① P1 ③ ② Pn 图3 Pn--1 Pk P3

分析
? 区域①的拆分方案总数是Ck,区域②的拆分方案数为Cn-k+1, 故包含△P1PkPn的n 边形的拆分方案数为CkCn-k+1种,而Pk可 以是P2,P3,……,Pnn-1 种任一点,根据加法原理,凸n边形 ?1 的三角拆分方案总数为 Ci Cn?i ?1 , 同时考虑到计算的方便, ? 约定边界条件C2=1。 i ?2
P2 ① P1 ③ ② Pn 图4 Pn--1 Pk P3

分析

?C C
i ?2 i

n ?1

=C( 2n , n ) / ( n + 1)
n ?i ?1

具体实现时,若直接用上述公式计算,对数字的精度要求较高。可将其化 为递推式

2 * (2n ? 1) f ( n) ? f (n ? 1) n ?1
再进行递推计算,并且注意类型的定义要用comp型。

Catalan数的应用(部分和序列)
? n个+1,n个-1构成2n项 ? a1,a2,a3,a4,,,,,,a2n 其部分和满足 a1+a2+......ak (k=1,2,3,...2n)>=0的数列个数。

Catalan数的应用(加括号)
序列a1a2..ak的元素顺序保持不变,按不同结 合方式插入合法圆括号对的方案数。 n=4 (a((bc)d)) (a(b(cd))) ((ab)(cd)) (((ab)c)d) ((a(bc))d)

Catalan数的应用(栈 NOIp2003)
一个操作数序列,从1,2,一直到n,栈A的深度大于n。现在可以进行两种操作:1 .将一个数,从操作数列的头端移至栈的头端(对应栈的push操作)2.将一个数,从栈 的头端移至输出序列的尾端(对应栈的pop操作)。使用这两种操作,由一个操作数序列 就可以得到一系列的输出序列,下表为由1 2 3 生成序列2 3 1 的过程。

步骤
操作数序 列 栈 输出序列

0
123

1
23 1

2
3 21

3
3 1 2

4

5

6

31 2

1 23 231

分析
任务: 你的程序将对给定的n,计算并输出由操作数序列1,2,……,n经过操作可 能得到的输出序列总数。

结合定义我们很容易能发现:如果进栈看成1,出栈看成0,在任何一位上累计的“0” 的个数不大于累计的“1”的个数,因为必须在栈里有数的情况下才能向外弹数。

原题转化为——n个1和n个0组成一个2n位的二进制数,要求从左到右扫描,“0”的 累计数不大于“1”的累计数,求满足条件的数有多少。

组合计数
错排问题(经典问题) n个数,分别为1~n,排成一个长度为n的排 列。若每一个数的位置都与数的本身不相等, 则称这个排列是一个错排。例如,n=3,则错 排有2 3 1、3 1 2。编写程序,求n的错排个数 。

分析
我们设k个元素的错位全排列的个数记做:W(k)。
四个元素的错位排列W(4)我们用穷举法可以找到 如下9个:

(4,3,2,1)(3,4,1,2)(2,1,4,3) (4,1,2,3)(3,4,2,1)(3,1,4,2) (4,3,1,2)(2,4,1,3)(2,3,4,1) 它们有什么规律呢?

分析
通过反复的试验,我们发现事实上有两种方式产生错位排列: A.将k与(1,2,?,k-1)的某一个数互换,其他k-2个数进行错排,这样可以得到 (k-1)×W(k-2)个错位排列。 B.另一部分是将前k-1个元素的每一个错位排列(有W(k-1)个)中的每一个数 与k互换,这样可以得到剩下的(k-1)×W(k-1) 个错位排列。

根据加法原理,我们得到求错位排列的递推公式W(k):

W(k) = (k–1) * [W(k–1)+W(k–2)]

构造法
? “构造法”解题,就是构造数学模型解 决问题。包括直接构造问题解答的模型, 图论模型,网络流模型以及组合数学模型。

构造法解题的思路或步骤

构造法解题的类型:

?直接构造问题解答。这只是构造法运用的一种简单类 型。它只能针对问题本身,探索其独有性质,不具备可 推广性。
?数学建模。通过沿用经典的数学思想建立起模型;或 者提取现实世界中的有效信息,用简明的方式表达其规 律,这种规律可以是一条代数公式、一幅几何图形,一 个物理原理、一个化学方程式,等等。

无论是直接构造问题解答还是构造数学模型,都要通 过算法实现。如何设计一个有较低编程复杂度和时空 复杂度且结构清晰的算法,十分重要。通常考虑的因 素有 ?选择的模型必须尽量多地体现问题的本质特征。但 这并不意味着模型越复杂越好,累赘的信息会影响算 法的效率。 ?模型的建立不是一个一蹴而就的过程,而是要经过 反复地检验、修改,在实践中不断完善。 ?数学模型通常有严格的格式,但程序编写形式可不 拘一格。

利用数学方法进行构造
例1:求Fibonacci数列

定 义 : f0=f1=1, fn=fn-1+fn-2(n>=2) 。 {fi} 称 为 Fibonacci数列。 输 入 n , 求 fn mod q 。 其 中 1<=q<=30000 。 n<=109 【解题分析】 简单的模拟显然不能满足题目的要求,我们考虑构 造解答。

定义矩阵 0

1 为A, 发现(x,y)×A=(y,x+y),恰好与

1 1 数列性质相似 。

于是有, 有(1,1)×A=(1,2), (Fi,Fi+1)×A=(Fi+1,Fi+Fi+1)=(Fi+1,Fi+2) ,
即(1,1)×An=(Fn,Fn+1) 在㏒(n)的时间内即可出解。

例题2: 毛毛虫是含N个节点的一棵树,它包含一条 主链,所有点要么在链上,要么和主链上 某点相邻。我们希望给毛毛虫的每个顶点 标号1,2,3,…,N,使得所有边的两端节点标 号差的绝对值恰好包含了1,2,3,…,N-1,每 个数正好一次(N<=10000)。

8

7 4

1
1 2

8 5 4 8

9
3 6 6 3

2

7

5

? 这个题目初看上去,似乎无从下手。由于题目中 所给的这种特殊的树以及顶点标号的约束条件都 是我们以前没有见到过的,再加上数据的规模很 大,最大可以达到N=10000。使得我们不得不朝 着贪心或者构造的方向去思考。 ? 首先观察样例,再进行了一些尝试后,我们找 到了对于样例的很多种合法的标号,其中有一种 引起了我们的注意,如下图所示:

1

8 7 2

9 6 3

5 4 8

4
3 7 2 6

1

5

? 很容易发现,图中边的权值,也就是边的 两端顶点标号差的绝对值,是从左向右依 次递减的。这个发现使我们不由得想到, 是不是对于所有的毛毛虫都存在一种这样 的合法标号方式。

例题分析
? 一序列(见文本)

利用图论模型进行构造
例题3:圆桌吃饭问题 n个人围着一张圆桌吃饭,每个人都不 愿意两天与同一人为邻,问最多能坐多少 天,并给出一种排列方案?

转化为图论模型
? 设G=(V,E)为一完全图,|V|=n。图中的每个 顶点代表一个人,连结顶点的边表示人之间的相 邻关系。因此,每种围绕圆桌的吃饭方案就成为 图中的一条哈密尔顿回路。设L=<v1,v2,…,vn>为 G中的一条哈密尔顿回路,其中所含的边的集合 记为e(L)。问题转化为: ? 求m与L1,L2,…,Lm,使得e(Li)∩e(Lj)=φ, ? 并且m达到最大值。

构造方法
? 作一圆,把圆周分成n-1等分,标上n-1个刻度, 将顶点1至n-1依次排列在圆周上,顶点n放在圆心。 先从圆心出发,向任意点连一条线,再从这点出 发,沿圆周向左右两个方向迂回连线,直到连完 圆周上所有的点,再连回圆心。这样就构造出一 条哈密尔顿回路。保持所有的顶点位置不变,把 所有连线围绕圆心逆时针方向旋转一个刻度,得 到一条新的哈密尔顿回路。这样连续旋转(n-1)div 2次,就得到了(n-1)div 2条回路。

? N=5
4 5 6 1 2
当n=5时

4
3

5

6

3

1

2

构造图象,充分展示各变量之间的关系

【例二】01串问题(NOI99) 给定N,L0,A0,B0,L1,A1,B1,设计一个长度为 N的01串,使得对于任何连续的长度为L0的 子串,0的个数大于等于A0,且小于等于B0, 对于任何连续的长度为L1的子串,1的个数 大于等于A1且小于B1。

【解题分析】 模式1 分析不等式

设 hi 为 01 子串 s0..si(1<=I<=n) 中 1 的个数,其中 s0=0,h0=0 。 显 然 , 由 hi 的定 义 可 以 得 出 不 等 式 0<=hi-1<=hi,hi<=hi-1+1, 移项即得:
0<=hi-hi-1

-1<=hi-1-hi

当 I>=L0 时,根据条件, Si-L0+1…Si 中 0 的个数 (L0-(hi-hi-L0))在a0~b0之间,即a0<=L0-(hi-hi-L0)<=b0
L0-b0<=hi-hi-l0

a0-L0<=hi-L0-hi 当I>=L1时,根据条件,Si-L1+1 … Si中1的个数(hi-hiL1)在a1~b1之间,即a1<=hi-hi-L1<=b1。
-b1<=hi-l1-hi
a1<=hi-hi-L1

一旦有了h序列,我们可以由左至右构造s串:如果hi1=hi ,则说明 si=0 ;否则 si=1(1<=I<=n) 。由此看来,问题的 关键是如何计算h序列。 仔细观察上述推论条件,发现有以下特点: (1) 除h0=0外,其余的条件都是由“<=”连接的不等式

(2) 每个不等式都是含两个h未知数、一个常数的一次 不等式;
可见,所有不等式都整理成了k<=hi-hj

它给我们启示,上述不等式类似于连接两点的一条有 向边。因此,我们联想到信息学解题中常用的图论知识。

模型2 构造有向图G
我们构造有向图G,如图: 其中vi代表s串中的第I位。若k<=vi-vj,则vi向vj引出一条权 为k的有向边<vi,vj>,表明si…sj中至少需增加k个1(k为正值) 或减少k个1(k为负值)。由此得出构造有向图G的方法: 0<=hi-hi-1 -1<=hi-1-hi a0-L0<=hi-L0-hi

L0-b0<=hi-hi-l0
a1<=hi-hi-L1

-b1<=hi-l1-hi

计算图G的最长路径: 我们已构造了一个有n+1个顶点的有向图G。
(1) 图G中无环 令D[I]表示从顶点0到顶点I的最长路径长度。 对于图中 每条从点I指向点J的权为C[I,J]的边,有性质 D[I]+C[I,J]<=D[J](注意:这与上述不等式的形式相似) 这样,令hi=D[I],h完全符合所有限制条件,即为原不 等式组的一组解 。 (2) G中含有环 可用反证法证明无解。 从s1出发,顺序确定每位二进制数。当hi=hi-1时,说明 s1…si-1中1的个数与s1…si中1的个数相同,即si为0;否则si 为1。


相关文章:
NOIP2015提高组day1第二题解题报告
NOIP2015提高组day1第二题解题报告_学科竞赛_高中教育_教育专区。NOIP2015提高组day1第二题的解题报告因为太简单所以写出来(误作者:蒟蒻zrw ...
NOIP2015提高组复赛试题Day1
全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组day1 (请选手务必仔细阅读本页内容)一.题目概况 中文题目...
NOIP培训讲义1
day1数学方法-曹立国-noip... 62页 免费 NOIP(普及组)初赛复习资料... 70页 免费 信息竞赛复习资料1--计算机... 11页 5财富值 培训讲义1 2页 免费 培训...
Noip 2013 Day1 解题报告
Noip 2013 Day1 解题报告 --By GreenCloudS 第一题:转圈游戏(快速幂)根据题目,答案明显是(x+10^km) mod n,化简一下,就成了(x + m (10^k mod n) ...
NOIP2014_day1-link自编答案
NOIP2014_day1-link自编答案_初中教育_教育专区。NOIP2014复赛;第二题联合权值link.cpp自编题 #include <cstdio> #include <cstring> #include <iostream> #...
NOIP2011提高组解题报告day1
NOIP2011提高组解题报告day1_学科竞赛_高中教育_教育专区。NOIP2011提高组解题报告day1NOIP2011 提高组解题报告 day1 (2011-12-13 09:29:54) 标签: 杂谈 铺地...
NOIP2015提高组解题报告
NOIP2015 提高组解题报告 T1 神奇的幻方【题目大意】 告诉你幻方的构造方法,给...NOIP2015提高组day1第二... 8页 免费 NOIP2015提高组参考答案 1页 免费 ©...
NOIP 2016 提高组 复赛 Day1
NOIP 2016 提高组 复赛 Day1_学科竞赛_高中教育_教育专区。第二十二届全国青少年信息学奥林匹克联赛 CCF-NOIP-2016 提高组(复赛) 第一试 ...
NOIP2011提高组复赛DAY1解题报告
NOIP2011提高组复赛DAY1解题报告_初一数学_数学_初中教育_教育专区。NOIP2011提高组复赛DAY1解题报告 NOIP2011DAY1 解题报告 By 北京一零一中学 张子威(c++) 首先...
noip 2011 day1
noip 2011 day1 隐藏>> 分享到: X 分享到: 使用一键分享,轻松赚取财富值, 了解详情 嵌入播放器: 普通尺寸(450*500pix) 较大尺寸(630*500pix) 预览复制...
更多相关标签:
noip2016提高组day1 | noip2016 day1 | noip2013day1 | noip2015day1 | noip2015提高组day1 | noip2012day1 | noip2014day1 | noip2016 day1 t2 |