logo资料库

noip(1998-2012)历年普及问题求解题解.doc

第1页 / 共8页
第2页 / 共8页
第3页 / 共8页
第4页 / 共8页
第5页 / 共8页
第6页 / 共8页
第7页 / 共8页
第8页 / 共8页
资料共8页,全文预览结束
普及历年问题求解答案及解题指导(98-02) 【普及组 1998】 1. 当 K= 3 ,a1,a2,…,ak 为 a1=3,a2=-3,a3=1 时, 对数列 122232,…,n2,…(A)成立。 解答:解方程,先设 K=2,列出方程组: a1*12+a2*22=32 a1*22+a2*32=42 以上方程组无整数解。再设 K=3,列出方程组: a1*02+a2*12+a3*22=32 a1*12+a2*22+a3*32=42 a1*22+a2*32+a3*42=52 以上方程的整数解为:a1=1,a2=-3,a3=3,此时 K=3。 2. 解答:(1)12 人 (2)30 人 方法:推理或集合表示如下: 下图中:a=8;b=4;c=3;abc=2;ab=4-abc=2;ac=2-abc=0;bc=3-abc=1; 读过 a 的人数为:a+ab+abc+ac=8+2+2+0=12 一本未读过的人:50-a-b-c-abc-ab-ac-bc=30 3.略 2202000 1/8
【普及组 1999】 1. 解答:一种方法是画图;另外,可以根据整棵树的入度=出度(因为任一根关联边连接 两 个 结 点 ) 这 一 性 质 推 导 , 除 根 结 点 外 的 每 个 结 点 入 度 都 是 1 , 所 以 总 的 入 度 =1*x+1*2+1*1+1*3-1;每个叶结点的出度为 0,分支结点的出度为度数-1,根结点的出度就 是它的度,所以总的出度=0*x+(2-1)*2+(3-1)*1+(4-1)*3+1;算出:x=9。 2. 根据 Nocomachns 定理,任何一个正整数 n 的立方一定可以表示成 n 个连续的奇数的和。 例如: 13=1 23=3+5 33=7+9+11 43=13+15+17+19 在这里,若将每一个式中的最小奇数称为 X,那么当给出 n 之后,请写出 X 与 n 之间的 关系表达式:__ X=n*(n-1)+1____。 【普及组 2000】 1. 解答:5 种,形态如下: 2. 解答:F(1)=1 F(2)=2 F(n)=F(n-2)+F(n-1)(n≥3) 【普及组 2001】 1. 解答:在 a,b,c,d,e,f 六件物品中,按条件能选出的物品是:a,b,c,f。 2. 解答:用这些点为顶点,能组成 751 个不同三角形。 假设三条直线是 ABC: (A:5 个点,B:6 个点,C:7 个点) 分两种情况 (1)3 个点在不同直线上 7*5*6=210 (2)两个点在一直线上,另一个点在其它直线上 则若 A 上有 2 点,是 C(5,2),B 或 C 上有一点,是 C(5,2)*(6+7)=130 同理若 B 上 2 点是 C(6,2)*(5+7)=180 若 C 上 2 点则 C(7,2)*(5+6)=231 所以一共 210+130+180+231=751 2/8
【普及组 2002】 1. 出口← ← 1 2 3 4 5 解答:8 种 分两种情况: (1)45 顺序走出,由于 2 必须在 1 前面共 5 种; (2)54 顺序走出,4 必需紧跟着 5 走出,共 3 种; S↓ 2. 解答:可以理解为 N 个 1 和 M 个 0 的二进制。就是 C(N+M,N)或 C(N+M,M) 本题为:C(7,4)= C(7,3)=35 【普及组 2003】 1. 解答:两年汽车行驶 24000 英里 24000/20-24000/30=1200-800=400 元 20000 元+400 元=2.04 万元 2. 解答:16 条边得出结点总数为 32 去除 3 个 4 度,4 个 3 度,还剩 8 因为题上说其余结点度数都小于 3,所以度数最大为 2 所以最少还有 4 个结点,每个结点度数都为 2 4+3+4=11 【普及组 2004】 1. 解答:设每单位木材 x 元。 则:每张桌子利润为 30-20x,每张椅子利润为 20-16x。 x>2.5 时,椅子利润较大,x<2.5 时,桌子利润较大. 由于:利润为负数不合题意, 所以:在木材尽量用光的情况下,所做桌子越多,所得越高. 经试验:当做桌子 4 张,椅子 2 张时,所得最多. 答:最多可卖 4×30+2×20=160 元. 2. 解答:3 种东西都玩过的共用去:3×5×20=300(元) 只玩过两种东西的共用去:2×5×(55-20)=350(元) 那么:只玩过一种东西的人数为:(700-300-350)÷5=10(人) 所以:什么也没有玩的人数为:75-55-10=10(人) 【普及组 2005】 1. 解答:略 交换 5 次 3/8
2. 解答:(加法原则)物理选张 4 种 物理选王;化学选张 3 种 化学选李或赵 4 共 4+3+4=11 【普及组 2006】 1. 解答:4 次 第一步:分成 3 组:27,27,26,将前 2 组放到天平上 2. 解答:这种情况最有意思,它与二进制有密切关系,我们用(a,b,c)表示某种局势,首 先(0,0,0)显然是奇异局势,无论谁面对奇异局势,都必然失败。第二种奇异局势是(0, n,n),只要与对手拿走一样多的物品,最后都将导致(0,0,0)。仔细分析一下,(1,2, 3)也是奇异局势,无论对手如何拿,接下来都可以变为(0,n,n)的情形。 计算机算法里面有一种叫做按位模 2 加,也叫做异或的运算,我们用符号(+)表示这种运 算。这种运算和一般加法不同的一点是 1+1=0。先看(1,2,3)的按位模 2 加的结果: 1 =二进制 01 2 =二进制 10 3 =二进制 11 (+) ——————— 0 =二进制 00 (注意不进位) 对于奇异局势(0,n,n)也一样,结果也是 0。 任何奇异局势(a,b,c)都有 a(+)b(+)c =0。 如果我们面对的是一个非奇异局势(a,b,c),要如何变为奇异局势呢?假设 a < b< c, 我们只要将 c 变为 a(+)b,即可,因为有如下的运算结果: a(+)b(+)(a(+)b)=(a(+) a)(+)(b(+)b)=0(+)0=0。要将 c 变为 a(+)b,只要从 c 中减去 c-(a(+)b)即 可。 对于本次普及组“取石子游戏”来说, 19 7 5 3 50 50-18=32 所以第 1 次只能在第 5 堆石子中取 32 粒,使出现奇异局势,即异或运算结果为 0。 0 1 0 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 1 1 1 1 0 0 1 0 (18)10 4/8
【普及组 2007】 1. (提示:先固定一个数,对于其余的 5 个数考虑 S(5,3)与 S(5,2),再分这两种情况对原 固定的数进 行分析)。 解答: 方法 1:排列组合分为三种情况:按各个子集中数字的数目划分:114、123、222 三种。 114 时:C(6,1)* C(5,1)/P(2,2)=15 种 123 时:C(6,1)* C(5,2)=60 种 222 时:C(6,2)* C(4,2)/P(3,3)一共 15 种! 所以,总的为 15+60+15=90 种! 方法 2:递推法 递推式为 s(n,r)=s(n-1,k-1)+k*s(n-1,k) 就是考虑新增元素是独立划分,还是在别的子集中两种情况用加法原理相加 2. A B 解答:从(1,1)点走到(N,M)点,无论如何走一共都要走(N-1)+(M-1)步,其中 N-1 步 向右走,M-1 步向下走,因为只有两种走法,不妨用二进制表示走路方式,1 表示向右走, 0 表示向下走。则可用一个长度为(N+M-2)的二进制串来表示走路方法,其中如果出现 了 N-1 个 1,则表示找到了一种路径。从而把题目转化为求长度为 N+M-2 的 2 进制串中 有 N-1 个 1 的个数,即求组合数学公式 C(N+M-2,N-1)的值。C(10,4)=210。 【普及组 2008】 1. 解答:1)所有黑皮的书都排在一起的摆法: 用捆绑法,把 CD 看成一本,再与另两共三本,可以任意排列,有 3!=6,另外 CD 可以颠倒, 所以共有:3!*2=12 2)同上道理,把红皮黑皮都捆绑,看成两本书,因为 A 要在 C 的左边,所以只能红皮在左 所以共有:2!*2!=4 2. 城市 1 城市 2 城市 3 城市 4 城市 5 城市 6 城市 1 城市 2 城市 3 城市 4 城市 5 城市 6 0 2 3 1 12 15 2 0 2 5 3 12 12 3 6 7 0 2 15 12 5 9 2 0 1 5 3 0 7 9 3 2 0 3 6 5 5/8
解答:人工 dijkstra 即可,Dijkstra 算法是一种求单源无负权最短路的算法,即从一个点 开始到所有其他点的最短路。其基本原理是:每次新扩展一个距离最短的点,更新与其相邻 的点的距离。1》2》5》6,最短距离为 7 【普及组 2009】 1. 解答:B 任务中的 b1 题目要求先做了。除了 b1 外, 只有 1 种。 第一类:完成 A 任务 有 C(4,1)=4 种。 第二类:完成 A 任务和 b2 第三类:完成 A 任务和 b2、b3 有 C(5,2)=10 种。 第四类:完成 A 任务和 b2、b3、b4 有 C(6,3)=20 种。 第五类:完成 A 任务和 b2、b3、b4、b5 有 C(7,4)=35 种。 加起来 1+4+10+20+35=70。 2. 解答:可以画出一个拓扑图 1——>2——>4——6——7 \——>3——/ / \——5—/ 第一时间 1,第二时间 2 和 3,第三时间 4 和 5,第四时间 6,第五时间 7 【普及组 2010】 1. 解答:问题的关键是破解 4、5、6 分别表示的是什么。根据题意可知,3 表示的是空格,如 果前面出现的不是 4,5,6 的话,前面出现的会被重新编码。 即第一个 3 前面的内容“2212”会被编码为 4,以此类推,可知: YYXY 4 XYX 6 得到:2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6 XX 5 2. 解答:第一个是"" 一位数一共有 6 个 然后两位数 1 1 到 1 6 共 6 个 2 1 到 2 5 共 5 个 3 1 到 3 4 共 4 个 4 1 到 4 3 共 3 个 5 1 到 5 2 共 2 个 6 1 到 6 1 共 1 个 最后三位数 1 开头 116 2 开头 215 同理可得 总共 6+5+。。+1=21 125 134 224 143 233 242 152 251 161 总共 1+。。+6=21 个 所以全部加起来总共 1+6+21+21=49 个 6/8
【普及组 2011】 1. 解答:C(8,0)+ C(8,2)+ C(8,4)+ C(8,6)+ C(8,8)=1+28+70+28+1=128 也就是最后的结果。 2. 解答:step1:ABCDECG; step2:BCDECG; step3:BADECG;共 3 步 【普及组 2012】 1. 解答:其实只要两个点横坐标和纵坐标都是相差偶数个点(0 也是偶数)他们的中点必是整 点。当 N=4 时,给每个点标号 1,2,3,4,每个点之间可以为横坐标差奇数个点(假设 1,2 点), 纵坐标差奇数个点(假设 1,3 点),横纵坐标都差奇数个点(假设 1,4 点),使得不能产生连 线的中点是整点(可证 2,3,4 点之间也有同样情况)。当 N=5 时,假设已有原 4 个点(1,2,3,4) 是无法产生连线的中点是整点的情况,那么最后一个点 5 无论是那个点都至少能找到一个点 产生连线的中点是整点。如果 5 点与 1 点横坐标相差奇数个点,那么 5 点与 2 点可成(可证 其他情况)。所以至少为 5 个点 2. 解答:先看成 5 对的圆排列(5-1)!剩下来的 5 个位子再有另 5 个队员排列 5! (5-1)!*5!=2880 种 7/8
8/8
分享到:
收藏