历届NOIP问题求解及答案

历届问题求解NOIP1998普及二、问题求解：（20%）已知一个数列U,U,U，…，U，…往往可以找到一个最小的K1值和K个数a,a,…，a使得数1 2 k列从某项开始都满足：U=aU+aU+ +aUN+K1N+K-1 2N+K-2 kN（A）例如对斐波拉契数列1，1，2,3,5，…可以发现：当K=2,a1=1,a2=1时，从第3项起（即N>=1）都满足U；=Un+1+U：。试对数列12,22,32,…，n2,…求K和a1,na2,"…，aK使得（A）式成立。{7%} 12 '某班有50名学生，每位学生发一张调查卡，上写a,b,c三本书的书名，将读过的书打，结果统计数字如下：只读a者8人；只读b者4人；只读c者3人；全部读过的有2人；读过a,b两本书的有4人；读过a,c两本书的有2人；读过b,c两本书的有3人；{6%}（1）读过a的人数是 （2）一本书也没有读过的人数是任给自然数n,k,1WKW9，按如下计算步骤求序列XX1……X0的步骤：{8%}JJt3j=0NOIP1999普及二、回答问题（10分）(2)如果N>=K则转第3步，否则转第7步(3)X=NMODK {div表示整数除法，结果取整数；(4)N =N DIV Kmod表示整除取余数}(5)j=j+1(6)回第2步(7)X=N(8)结束试求当：N=1998,K=3时，XX]……X。之值。TOC\o"1-5"\h\zNOIP1998提高 JJ-1 0二、问题求解：（21%）1、已知一个数列U,U,U，…U，…往往可以找到1 2 3 n一个最小的k值和k个数a,a，…，a，使得数列从某项开始都满足： 1 2ku=au+au +•••+au （A）n+k1n+k—12n+k—2 kn例如对斐波拉契数列1,1,2,3,5,…可以发现：当k=2,a1=1,a2=1时，从第3项起（即nN1）都满足u2=u1+uo试对数列13,23,33,…，n3,…求k和a,a，…，气使得（A）成立。 （8%） 1 2k2、给出一棵二叉树的中序遍历：DBGEACHFI与后序遍历：DGEBHIFCA画出此二叉树。（8%）在磁盘的目录结构中，我们将与某个子目录有关联的目录数称为度。例如下图该图表达了A盘的目录结构：D1,Dll,…，D2均表示子目录的名字。在这里，根目录的度为2,D1子目录的度为3,D11子目录的度为4,D12,D2,D111,D112,D113的度均为1。不考虑子目录的名字，则可简单的图示为如下所示的树结构：若知道一个磁盘的目录结构中，度为2的子目录有2个，度为3的子目录有1个，度为4的子目录有3个。试问：度为1的子目录有几个？三、公式推导（10分）根据Nocomachns定理，任何一个正整数n的立方一定可以表示成n个连续的奇数的和。例如：13=123=3+533=7+9+1143=13+15+17+19在这里，若将每一个式中的最小奇数称为X,那么当给出n之后，请写出X与n之间的关系表达式：NOIP1999提高二、回答问题（10分）将Ln定义为求在一个平面中用n条直线所能确定的最大区域数目。例如：当n=1时，L=2，进一步考虑，用n条折成角的直线（角度任意），放在平面上，能确定的最大区域数目Zn是多少？例如：当n=1时，Z1=2（如下图所示）/ 当给出n后，请写出以下的表达式：Ln= 2 Zn=

NOIP2000普及二、问题解答：（每题7分，共14分）已知，按中序遍历二叉树的结果为：abc问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。有2Xn的一个长方形方格，用一个1X2的骨牌铺满方格。例如n=3时，为2X3方格。此时用一个1X2的骨牌铺满方格，共有3种铺法：试对给出的任意一个n（n〉0），求出铺法总数的递推公式。NOIP2000提高二.问题求解：（6+6=12分）已知，按中序遍历二叉树的结果为：abc问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。设有一个共有n级的楼梯，某人每步可走1级，也可走2级，也可走3级，用递推公式给出某人从底层开始走完全部楼梯的走法。例如：当n=3时，共有4种走法，即1+1+1，1+2，2+1，3。NOIP2001普及在a,b,c,d,e,f六件物品中，按下面的条件能选出的物品是：（1） a,b两样至少有一样（2） a,d不能同时取NOIP2002普及二.问题求解：如下图，有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车厢。其中每个车厢可以向左行走，也可以进入栈S让后面的车厢通过。现已知第一个到达出口的是3号车厢，请写出所有可能的到达出口的车厢排列总数（不必给出每种排列）。将N个红球和M个黄球排成一行。例如:N=2,M=3可得到以下6种排法：红红黄黄黄红黄红黄黄红黄黄红黄黄红红黄黄黄红黄红黄黄黄黄红红问题：当N=4,M=3时有多少种不同排法？（不用列出每种排法）NOIP2003普及二.问题求解（每题5分，共10分）.现在市场上有一款汽车A很热销，售价是2万美元。汽车A每加仑汽油可以行驶20英里。普通汽车每年大约行（3） a,e,f中必须有2样（4） b,c要么都选，要么都不选（5） c,d两样中选一样（6） 若d不选，则e也不选平面上有三条平行直线，每条直线上分别有7,5,6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同三角形？NOIP2001提高二、问题求解（5+7=12分）已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：CBGEAFHDIJ与CGEBHFJIDA则该二叉树的先序遍历的顺序为：平面上有三条平行直线，每条直线上分别有7,5,6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形？驶12000英里。油价是每加仑1美元。不久我公司就要推出新款节油汽车B，汽车B每加仑汽油可以行驶30英里。现在我们要为B制定价格（它的价格略高于A）:我们预计如果用户能够在两年内通过节省油钱把B高出A的价钱弥补回来，则他们就会购买B，否则就不会购买B。那么B的最高价格应为万美元。无向图G有16条边，有3个4度顶点、4个3度顶点，其余顶点的度均小于3,则G至少有个顶点。NOIP2004普及一个家具公司生产桌子和椅子。现在有113个单位的木材。每张桌子要使用20个单位的木材，售价是30元；每张椅子要使用16个单位的木材，售价是20元。使用已有的木材生产桌椅（不一定要把木材用光），最多可以卖 元钱。75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700,可知有—名儿童没有玩过其中任何一种。NOIP2005普及将数组｛32,74,25,53,28,43,86,47中的元素按从小到大的顺序排列，每次可以交换任意两个元素，最少需要交换 次。2.2.有3个课外小组：物理组，化学组和生物组。今有张、王、李、赵、陈5名同学，已知张、王为物理组成员，张、李、赵为化学组成员，李、赵、陈为生物组成员。如果要在3个小组中分别选出3位组长，一位同学最多只能担任一个小组的组长，共有种选择方案。NOIP2006普及1.(寻找假币)现有80枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量都相同如果使用不带砝码的天平称重最少需要称几次就可以找出假币？你还要指出第1次的称重方法请写出你的结果 2.(取石子游戏)现有5堆石子石子数依次为3,5,7，19，50，甲乙两人轮流从任一堆中任取(每次只能取自一堆不能不取)，取最后一颗石子的一方获胜。甲先取问甲有没有获胜策略(即无论乙怎样取甲只要不失误都能获胜)？如果有，甲第一步应该在哪一堆里取多少？请写出你的结果 O城市51236702城市615125920NOIP2007普及二、问题求解(共2题，每题5分，共计10分)。1、 (子集划分)将n个数(1，2,…，n)划分成r个子集。每个数都恰好属于一个子集，任何两个不同的子集没有共同的数，也没有空集。将不同划分方法的总数记为S(n,r)。例如，S(4,2)=7，这7种不同的划分方法依次为｛(1),(234)｝，｛(2),(134)｝，｛(3),(124)｝，｛(4),(123)｝，｛(12),(34)｝，｛(13),(24)｝， ｛(14),(23)｝。当n=6，r=3时，S(6,3)=。(提示：先固定一个数，对于其余的5个数考虑S(5,3)与S(5,2)，再分这两种情况对原固定的数进行分析。)2、 (最短路线)某城市的街道是一个很规整的矩形网络(见下图)，有7条南北向的纵街，5条东西向的横街。现要从西南角的A走到东北角的B，最短的走法共有多少种？NOIP2008普及1.书架上有4本不同的书A、B、C、D。其中A和B是红皮的，C和D是黑皮的。把这4本书摆在书架上，满足所有黑皮的书都排在一起的摆法有种。满足A必须比C靠左，所有红皮的书要摆在一起，所有黑皮的书要摆放在一起，共有种摆法。2.有6个城市，任何两个城市之间都有一条道路连接，6个城市两两之间的距离如下表所示，则城市1到城市6的最短距离为。城市1城市2城市3城市4城市5城市6TOC\o"1-5"\h\z城市10 2 3 1 12 15城市22 0 2 5 3 12城市33 2 0 3 6 5城市41 5 3 0 7 9NOIP2009普及小陈现有2个任务A，B要完成，每个任务分别有若干步骤如下：A=a1->a2->a3，B=b1-〉b2-〉b3-〉b4-〉b5。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如……a2-〉b2-〉a3-〉b3 是合法的，而 a2-〉b3-〉a3-〉b2……是不合法的。小陈从B任务的b1步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务A，其他的都忘了。使计算小陈饭前已做的可能的任务步骤序列共有 种。有如下的一段程序：a:=1;b:=a;d:=-a;e:=a+d;c:=2*d;f:=b+e-d;g:=a*f+c;现在要把这段程序分配到若干台(数量充足)用电缆连接的PC上做并行执行。每台PC执行其中的某几个语句，并可随时通过电缆与其他PC通讯，交换一些中间结果。假设每台PC每单位时间可以执行一个语句，且通讯花费的时间不计。则这段程序最快可以在 单位时间内执行完毕。注意：任意中间结果只有在某台PC上已经得到，才可以被其他PC引用。例如若语句4和6被分别分配到两台PC上执行，则因为语句6需要引用语句4的计算结果，语句6必须在语句4之后执行。

答案：NOIP1998普及1.当K=_3 ,a,a，…，a为a=3,a=-3,a=1时，, 1 2 k1 2 3对数列 122232,…，n2,… (A)成立。{3%+3%)2.(1)读过a的人数是12人。(2)一本书也没读过的人数F(1)=1F(2)=2F(3)=4F(N)=F(N-3)+F(N-2)+F(N-1) (NN4)NOIP2001普及二、问题解答(5+7分，两题共12分)答：在a,b,c,d,e,f六件物品中，按条件能选出的物品是:a,b,c,f是30人。 {3%+4%}答：用这些点为顶点，能组成751个不同三角形••气之值为NOIP2003普及问题解答(每••气之值为NOIP2003普及问题解答(每题53.当n=1998,k=3时，xx.{7%} JJ-1NOIP1998提高二、问题求解：共20分当K=_4，a,a，…，a为a=4,a=6,a=4，a=-1对数列.一一 1,2ki2 3 4132333,…，n3,・"（A）成立。{3%+5%）.此二叉树为：{7%}/XD/E八.表示该无向H图的［邻接矩阵为{6%}0100000101100001010000110111000100100010010001110NOIP1999普及二、回答问题：(10分)NOIP2001提高二、问题解答(5+7分，两题共12分)答：该二叉树先序遍历的顺序为：ABCEGDFHIJ答：用这些点为顶点，能组成2250个不同四边形NOIP2002普及二、问题解答1、82、35分，共10分)答：2.04TOC\o"1-5"\h\z答：11NOIP2004普及二.问题解答(每题5分，共10分)答： 160答： 10NOIP2005普及二.问题解答(每题5分，共10分)答：52.答：11NOIP20