备战NOIP201提高组初赛复习问题求解篇

备战NOIP201提高组初赛复习——问题求解5101n2n=3f(3)=1n=9。把所有的硬币分成三组：A{1,2,3},B{4,5,6},C{7,8,9}。A组的硬币放在左边、B组放在右边。如果天平：1A2B3C1/3。之前我们已经研究过，31次就能称出来，故而1.1f(3n)=n证明：n=1,2n=kf(3k)=kn=k+1的情况。3k+1AB,C，使得|A|=|B|=|C|=3kAB1233kf(3k)=k，f(3k+1)=k+1。1.1成立。1.2f(n)=log3n1.1nmod3=0,1,2我们必须注意到log3n是可行的1/3log3n应该就是最优解了。为了更加严格的证明log3nn=9>比较>比较(1,2,3)与<比较(7)与<>比较比较(4)与>=>

比较(1)与<>< 比较(1)与<><12nnh优的

我们的结论是：有n（n≥3）的要重一些。给一架天平，至少称log3nh

练习：第12届全国青少年信息学奥林匹克联赛初赛题80一枚是假币，其重量稍重，所有真币的重量都相同，如果使用不带砝码的天平 答案：4次；第一步，分成三组：27，27，262游戏Ⅰ有若干堆任意数目的小石子{a1，a2，…，am}(m≥1)，≤min{a1，a2，…，am})am；k}(0≤ai′<ai)TTT11001011011)0111122，33，44，55，66，77，88，99，这样我们就199a(1≤a≤10)颗，己方取(11—a)1{a1a2，…amkai≡ai′(modk+1)(i=12，…，m)0≤ai′≤k，在{a1′，a2′，…，am′；k}中有取胜策略的一方在{a1，a2，…，am；k}中也有取胜策略。证明在{a1′，a2′，…，am′；k}中有获胜kai(i=1，2，…，mai≡ai′(modk+1)，a(1≤≤k)k+1-ak+1，也ai′游戏Ⅱ有若干堆任意数目的小石子{a1，a2，…，am}，两人轮流从中取石m组{a1，a2，…，am}中的每一个分量用二进位制数表示，ai(1≤i≤m)i记为{n1，n2，…，nj，…，nl}nj(1≤j≤l)均为偶数，我mnj(1≤j≤l)，中有一个数为奇数，则称之为非32 3 5 3{2，3，1}：2 3 1 TTTmm2 3 6 n1 nii=1，2，3，所以{2，3，6}为非偶数，我们可以判定：先取者甲{231}是偶数组，无论乙如只可能变成如下六种情形之一或{1，1}，3：12届全国青少年信息学奥林匹克联赛初赛题5 753 15323225≡7(mod6)，根据游戏Ⅰ的策略{25，25，25；5}中有获胜策略的一7}即相当于取石子游戏Ⅱ的{4，5，1}，由于{4，5，1}nnn+1【分析】1212121313131222【例243【分析与解333344233（袜子无左、右之分36＋2＋2=1034【分析与解】532104（同一颜色）10＋5=15418 6，18（1+2+3+4+5+6）×3=63（只）1131234n＋1n2n33A={0，1，2，3，……，9}，0，1，2，…9AA，BA∪B。A∪B={1，2，3，5，6，10}∩B={1，2}4、容斥原理（包含与排除原理（用|A|AA={1，2，3}，则第一步：先求出∣A∣+∣B∣（A，B第一步：先求∣A∪B∪C∣=∣A∣+∣B∣+∣C∣-∣A∩B∣-∣B∩C∣- 12023的倍数个数，即求∣A∪B∣B={3，6，9，…18}，6|B|=6A∩B={23}={6，12，18}，3所以∣A∪B∣=∣A∣+∣B∣-∣A∩B∣=10+6-3=13，A∪B132：3A∩BA∪BB={90A∪B9090∣A∩B∣，∣A∩B∣=∣A∣+∣B∣-∣A∪B∣=25+21-解A={打篮球的同学}；B={A∩B={既打篮球又跑步的同学}应用容斥原理∣A∪B∣=∣A∣+∣B∣-∣A∩B∣=39+37-25=51（人4某年级的课外学科小组分为数学、语文、外语三个小组，参加数学小组4752由题意知∣A∪B∪C∣=∣A∣+∣B∣+∣C∣-∣A∩B∣-∣A∩C|-=23+27+18-=54（人24-2=25-2=3（人）23-2-2-5=14（人）。同理可把区14+20+8+2+5+3+2=54（人52（但412又喜欢看球赛的人数为χ，7解得36-2A={喜欢看球赛的人}，B={喜欢看戏剧的人}，C={喜欢看电影的人}，依题目的条件有|A∪B∪C|=100，|A∩B|=6+12=18（12χ由容斥原理二：|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|得：100=58+38+52-解得∴36-14，22不同的方法，在第二类办法中有m2nmn

Nm1m2

mn分步计数原理nm1种不同的方法，做第二步有m2nmnNm1m2Lmn排列数的定义：从n个不同元素中，任取m（mn）n数叫做从n个元素中取出mAmn5．排列数公式：Amn(n1)(n5．排列数公式：

(nm1)（m,nN,mn6n!1n的连乘积，叫做n的阶乘规定0nn7．排列数的另一个计算公式Am(n8：一般地，从n个不同元素中取出mmn个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合n组合数的概念：从n个不同元素中取出mmn个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数．用符号Cm表示．n Cmn

n(n1)(n

(nmA组合数公式 AnCmn或

m!(nm(nmN且mCmCnm

C011组合数的性质1： ．规定：

C2：n1C

CCn+CCAa1a2a3,an}的n个元素中，每次取出r上，叫做一个圆排列（或叫环状排列Pr进行圆排列，圆排列数为nr

an}的n个元素中，每次取出r顺序那么第一、第二、…、第n位是的选取元素的方法都是m种，所以从m个不同的元素中，每次取出n个元素的可重复的排列数为mn．如果np1p2ps素相同（p1p2 psn），这n个元素全部取的排列叫做不尽相异的n ps从np个元素，允许所取的元素重复出现

,p组合叫从np定理：从npHpCr n(344C3这也就是方程abcd12例素与其他五人进行排列，并考虑甲乙二人的顺序，所以共有种。也可以作排列.共有种排法练习：533此题涉及到的是排队问题,对于女生有特殊的限制,因此,女生是特殊元素,并 因为女生要排在一起,所以可以将3个女生看成是一个人,与5个男生作 P6 种排法,其中女生内部也有 62．7排法总数应为：种中即可.若个人站成一排，其中个人不相邻，可用“插空”法解决，共有种排法。练习：128，4此题涉及到的是不相邻问题,并且是对老师有特殊的要求,因此老师是特殊 先排学生共有8种排法,然后把老师插入学生之间的空档，共有7个空档插,选其中的4个空档,共 7种选法.根据乘法原理,共有的不同坐法P887例3.正六边形的中心和顶点共7个点，以其中3个点为顶点的三角形共 3＝32练习435分析此题若是直接去考虑的话,就要将问题分成好几种情况,这样解题的话,容易C 43人中任抽5人的方法 43种,正副班长,团支部书记都不在内的抽法C5C401

C C 置上任选一个位置，有种，而其余学生的排法有种，所以共有72例5．乒乓球队的10名队员中有3名主力队员，派5名队员参加比赛，3名主 ＝252 解：增加的两个新节目，可分为相临与不相临两种情况：1.A62种；2.A22A61：A62+A22A61=42A。7．12人，则不同的分配方案共有 种 种 D．解：本试题属于均分组问题。则12名同学均分成3组共有种方法,分配到三个不同的路口的不同的分配方案共有：种，故选A。质的三块土地上，其中黄瓜必须种植，不同的种植方法共有（ 3 解C2A1·A2,故不同的种植方法共有A1·C2·A3 76128121178

C11CC7C 一、利用逻辑原理,1.ABADCCB C：是A获奖或B获奖D：是B获奖例5 每科满分为5分，其余等级依次是4、3、2、1分。今已知按总分由多到少排列着五名学生，A、B、C、D、E满足下列条件：（2）A24（3）C（4）E35（5）D4EA24B、C、D、E75－24=51E8E（还有三科）11稍加验算可知：B、C、D、E15、13、12、11（2）E811E142135A、EC31E3C133C、E1C、ED2显然，B421条件（7），4，B3，C2，D1，E（）A. B. C. D.12一 递推关系的定1……n0nn0,可以用等号(或大于号、小于号)将HnHn(0i<n)联系起来，二 递推关系的建Fibonacci数础的程序设计语言Logo语言中，就有很多这类的题目。而在较为复杂的FibonacciFibonacci1202提出的“兔子繁殖问题”(又称“FibonaccinxFxNxx-1Ox Ox=Fx-Nx=Ox-1=Fx-2x-2x Fx=Fx-1+Fx- 边界条件 F2=F1+F0=1，F3=F2+F1=2，F4=F3+F2=3，F5=F4+F3=5，……Hanoi塔问na1 nacc3h2=3a2)cn-1b柱上；总共移动hn-1+1+hn-1∴hn=2hn- 边界条件：hn-1 1 18 4726610319 75 ann条封闭曲线把平面分割成的区域个数。由图2可以看出：a2-a1=2；a3-a2=4；a4-a3=6an-an-1=2(n-1)。当然，上n-1an-1个的an-1个区域，一共有an-1+2(n-1)个区域。所以本题的递推关系是an=an-1+2(n-1)，边界条件是a1=1。CatalanCatalanEulernnnnhn，hnCatalan6-4)，h5=5nhn。一直线上的三点可以确定一个三角形”，只要在P2，P3，……，Pn-1点中找一Pk(1<k<n)P1、Pnn其中区域③必定是一个三角形k①③② ①③②

n-k+1Ck区域②的拆分方案数为Cn-k+1故包含△P1PkPnn边形的拆分方案数为CkCn-k+1PkP2，P3，……，Pn-1n

总数为CiCni1C2=11、在一个正六边形的六个区域中的每一个FAFABEDA、C、E同，问有多少种染色方法？”先求通项an或递推关系，再求a6。A、C、EA、C、E染一种色，则此时共有43331084A、C、EP32221924 染二种色，则此时共有P2C2322432种 108+192+432=732解法二：将问题抽象成一般问题：“将圆分为n(n2个扇形，每个扇形区染色方法总数为an，求a6”。由已知条件容易建立递推关系

4

(no由该递推关系易求出a3

a2a4

a5

a6732【评注】（1）解法一中若不按A、C、E染色情况进行分类可能比较复杂， ab可能路线数。 FibonacciprogramPro_1;{40000}Tarr=array[1..10000]ofbyte;Tnum=array[1..4]of^Tarr;Tlen=array[1..4]ofword;{len[i]num[i]的长度procedureDataInit;{数据初始化}fori:=1to3donum[i]^[1]:=1;len[i]:=1;procedureAdd;{高精度加法运算：num[3]=num[1]+num[2]}fori:=1tolen[2]donum[3]^[i]:=carrymod10;carry:=carrydiv10;ifcarry>0procedureWork;{求从出发点到目标点的路径总数}num[1]^[1]:=1;fori:=start+2tofinishdoprocedureOut;{输出结果}fori:=len[2]downto1doDataInit;数据初始化}