搜索
1历届“问题求解”解析（2013竞赛辅导）问题求解是信息学竞赛初赛中常见题型，它共两题，每题5分，共10分，十六届增加了比重，有三题，占15分。诸如寻找假币、博弈原理、抽屉原理、容斥问题、排列组合、逻辑推理、递推关系等问题出现在问题求解中。（相关问题的具体讲解根据需要考虑发讲义）第一届（逻辑推理问题）1.有标号为A、B、C、D和1、2、3、4的8个球，每两个球装一盒，分装4盒。标号为字母的球与标号为数字的球有着某种一一对应的关系（称为匹配），并已知如下条件：①匹配的两个球不能在一个盒子内。②2号匹配的球与1号球在一个盒子里。③A号和2号球在一个盒子里。④B匹配的球和C号球在一个盒子里。⑤3号匹配的球与A号匹配的球在一个盒子里。⑥4号是A或B号球的匹配球。⑦D号与1号或2号球匹配。请写出这四对球匹配的情况。第四届（递推、树、图）1.已知一个数列U1，U2，U3，…，UN，…往往可以找到一个最小的K值和K个数a1，a2，…,an使得数列从某项开始都满足：UN+K=a1UN+K-1+a2UN+K-2+……+akUN(A)例如对斐波拉契数列1，1，2，3，5，…可以发现：当K=2，a1=1，a2=1时，从第3项起（即N=1）都满足Un+2=Un+1+Un。试对数列13，23，33，…，n3,…求K和a1,a2,…,aK使得（A）式成立。当K=4，a1,a2,…,ak为a1=4,a2=6,a3=4，a4=-1对数列132333,…,n3,…（A）成立。2．给出一棵二叉树的中序遍历：DBGEACHFI与后序遍历：DGEBHIFCA画出此二叉树。3．用邻接矩阵表示下面的无向图：表示该无向图的邻接矩阵为0100000101100001010000110111000100100010010001110第五届（递推）将Ln定义为求在一个平面中用n条直线所能确定的最大区域数目。例如：当n=1时，L1=2,进一步考虑，用n条折成角的直线（角度任意），放在平面上，能确定的最大区域数目Zn是多少？例如：当n=1时，Z1=2（如下图所示）当给出n后，请写出以下的表达式：Ln=______________2、Zn=_______________答案为：Ln=n(n+1)/2+1(n≥0)Zn=L2n-2n=2n2-n+1解析：本题实质是求直线或折线将一个平面分成的最大区域数，从两个方面考虑：（1）求在一个平面中用n条直线所能确定的最大区域数；n=1,L1=2,F(1)=2n=2,L2=4,F(2)=F(1)+2n=3,L3=7,F(3)=F(2)+3n=4,L4=11,F(4)=F(3)+4……所以，F(n)=F(n-1)+n把上面的n个等式左右相加，化简得出：F（n）=2+2+3+4+……+n即：L（n）=n*(n+1)/2+1ABCD4312ACBDEFGHI2（2）求在一个平面中用n条折线所能确定的最大区域数；n=1,Z1=2,F(1)=0+2n=2,Z2=7,F(2)=1*(2*2-1)+4n=3,Z3=16,F(3)=2*(2*3-1)+6n=4,Z4=29,F(4)=3*(2*4-1)+8……所以，F(n)=(n-1)*(2*n-1)+2*n即：Z（n）=(n-1)*(2*n-1)+2*n几何+归纳+组合数学！第六届（树与递推）1.已知，按中序遍历二叉树的结果为：abc问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。有5种不同形态的二叉树可以得到这一遍历结果;可画出的这些二叉树为:①a②b③a④c⑤c\/\\//baccab\/\/cbba2.设有一个共有n级的楼梯，某人每步可走1级，也可走2级，也可走3级，用递推公式给出某人从底层开始走完全部楼梯的走法。例如：当n=3时，共有4种走法，即1+1+1，1+2，2+1，3。答案：F(n)=f(n-1)+f(n-2)+f(n-3)n=4;F(1)=1;f(2)=2;f(3)=4;解析：两种方法，一是“猜”+“凑”，从具体的n=1,2,3……算起，只能算比较简单的，容易错；二是用组合数学和归纳法进行推导，一般先假设F（n）=a*F（n-1）+b*F（n-2）+c*F（n-3）+……，然后算a，b，c……直到某个系数=0就结束，再代入式子中。F（1）＝1F（2）＝2F（3）＝4F（N）＝F（N－3）＋F（N－2）＋F（N－1）（N≥4）推导：对于n级楼梯，可以有下面几种走法：1.最后走一级，则有f(n-1)种2.最后走两级，则有f(n-2)种3.最后走三级，则有f(n-3)种第七届（树与排列组合）1.已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：CBGEAFHDIJ与CGEBHFJIDA则该二叉树的先序遍历的顺序为：ABCEGDFHIJ2.平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形？C(7,2)*(5+6)+C(5,2)*(7+6)+C(6,2)*(7+5)+7*6*5=21*11+10*13+15*12+210=231+130+180+210=751第八届（排列与递推）1.在书架上放有编号为1，2，．．．，n的n本书。现将n本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。例如：n=3时：原来位置为：123放回去时只能为：312或231这两种问题：求当n=5时满足以上条件的放法共有多少种？（不用列出每种放法）解法一：c(5,0)*5!-c(5,1)*4!+c(5,2)*3!-c(5,3)*2!+c(5,4)*1!-c(5,5)*0!=60-20+5-1=44解法二：n封装入n个信封时全部装错的装法总数为!1)1(!21!111!nnn。3通常称为伯努利一欧拉错装信封问题，又称为乱序排列，即把n个元素的排列a1，a2，L，an重新排列，使每个元素都不在原来的位置上的排列问题。因此只要你代入公式就行2．设有一棵k叉树，其中只有度为0和k两种结点，设n0，nk，分别表示度为0和度为k的结点个数，试求出n0和nk之间的关系（n0=数学表达式，数学表达式仅含nk、k和数字）。n0和nk之间的关系为：n0=(k-1)nk+1。第九届（图与集合）1．无向图G有16条边，有3个4度顶点、4个3度顶点，其余顶点的度均小于3，则G至少11个顶点。2.某年级学生共选修6门课程，期末考试前，必须提前将这6门课程考完，每人每天只在下午至多考一门课程，设6门课程为C1，C2，C3，C4，C5，C6，S(Ci)为学习Ci的学生集合。已知S(Ci)∩S(C6)≠ф，i=1，2，...，5，S(Ci)∩S(Ci+1)≠ф，i=1，2，3，4，S(C5)∩S(C1)≠ф，问至少安排_4__天才能考完这6门课程。第十届(递推)1.75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700，可知有名儿童没有玩过其中任何一种。设a1,a2,a3分别是仅仅玩过一种游戏的人数，仅仅玩过2种游戏的人数，仅仅玩过三种的人数。因此有a2+a3=55,a3=20,a1+2*a2+3*a3=700/5;==a1=10所以结果就是75-a1-a2-a3=10名2.已知a,b,c,d,e,f,g七个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？如果可以，请以“ab”开头写出你的安排方案：abdfgec第十一届（排序与最火柴）1.将数组{32,74,25,53,28,43,86,47}中的元素按从小到大的顺序排列，每次可以交换任意两个元素，最少需要交换次。思路一：用直接选择排序实现：25,74,32,53,28,43,86,47第一次：32--2525,28,32,53,74,43,86,47第二次:28--7425,28,32,53,74,43,86,4725,28,32,43,74,53,86,47第三次：43--55325,28,32,43,47,53,86,74第五次：47--7425,28,32,43,47,53,86,7425,28,32,43,47,53,74,86第五次：74--86思路二：首先排序给每个数字标上序号{32，74，25，53，28，43，86，47}{3，7，1，6，2，4，8，5}再和标准序列{1，2，3，4，5，6，7，8}比较找出其中所有的环，这里的环就是指它们互相交换之后能成为标准序列的最小集合比如这里{1,3}是一个环,{7,2,5,8}是一个环。具体找法很简单首先确定一个不在已找出环中的数字。例如第一次从3开始,3对应标准序列的1再找1对应的标准序列33回到了开始的数字那么这个环就是{1，3}第二次从7开始，7-22-55-88-7所以第二个环是{7，2，5，8}第三个环是{6,4}这样所有的数字都在环中了交换的次数=（环中数字总数-环数）=8-3=52.一堆火柴有N根，A、B两人轮流取出。每人每次可以取1根或2根，最先没有火柴可取的人为败方，4另一方为胜方。如果先取者有必胜策略则记为1，先取者没有必胜策略记为0。当N分别为100，200，300，400，500时，先取者有无必胜策略的标记顺序为（回答应为一个由0和/或1组成的字符串）。答案：11011规律：每次可以取1..m根火柴(n为正整数，且1=mN)则N=k(m+1)后手胜，N！=k(m+1)先手胜(k为正整数)，N=3k后手胜和N！=3k先手胜(k为正整数)补：(取石子游戏)现有5堆石子,石子数依次为3,5,7,19,50,甲乙两人轮流从任一堆中任取(每次只能取自一堆,不能不取),取最后一颗石子的一方获胜.甲先取,问甲有没有获胜策略(即无论乙怎样取,甲只要不失误,都能获胜)如果有,甲第一步应该在哪一堆里取多少请写出你的结果。规律：将所有的堆的石子数化为二进制后，如果所有数位上的1的个数都是偶数（相加不考虑进位，为零）那么先取者必败；如果有些位上的1的个数是奇数，先取者能够将所有数位上的1的个数都变为偶数的话，那么先取者必胜。（也可以用or不考虑进位来解决）例：本题：可见，只有最高位的1是奇数个，其他位上都是偶数个。所以只需要将最高位的1取走即可必胜。二进制的100000就是10进制的32，所以要将50个石子的那堆取32个，取掉就变成偶数个数目。于是先取者必胜。以后无论对方怎么取，始终保证每一位上的1的个数是偶数即可（一种简单的方法是，他在一堆中取几个，你在另一堆中也取几个就可以）。第十二届（递推）1．将2006个人分成若干不相交的子集，每个子集至少有3个人，并且：（1）在每个子集中，没有人认识该子集的所有人。（2）同一子集的任何3个人中，至少有2个人互不认识。（3）对同一子集中任何2个不相识的人，在该子集中恰好只有1个人认识这两个人。则满足上述条件的子集最多能有个？显然集合的人数为3人以上。4人构造不出满足条件的情况，下面构造5人的情况：（存在边，表示两个人相互认识）故集合个数为2006div5=4012．将边长为n的正三角形每边n等分，过每个分点分别做另外两边的平行线，得到若干个正三角形，我们称为小三角形。正三角形的一条通路是一条连续的折线，起点是最上面的一个小三角形，终点是最下面一行位于中间的小三角形。在通路中，只允许由一个小三角形走到另一个与其有公共边的且位于同一行或下一行的小三角形，并且每个小三角形不能经过两次或两次以上（图中是n=5时一条通路的例子）。设n=10，则该正三角形的不同的通路的总数为_9！=362880_。解析：好的解题习惯是，通过人脑对小规模数据的求解，分析出问题的规律，从而得到解决问题的方法。本题n=10，而最后一层固定为中间的小三形，所