NOIP训练专题一(问题求解).docVIP

NOIP训练专题一 问题求解 NOIP2008 1．有6个城市，任何两个城市之间有一条道路连接，6个城市之间两两之间的距离如下表表示，则城市1到城市6的最短距离为______7______。 城市1 城市2 城市3 城市4 城市5 城市6 城市1 0 2 3 1 12 15 城市2 2 0 2 5 3 12 城市3 3 2 0 3 6 5 城市4 1 5 3 0 7 9 城市5 12 3 6 7 0 2 城市6 15 12 5 9 2 0 2．书架上有21本书，编号从1 到 21 从中选4 本，其中每两本的编号都不相邻的选法一共有_______3060____________种。 NOIP2007 1．给定n个有标号的球，标号依次为1，2，…，n。将这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=7，r=4时，S(7,4)= 。 ? 2．N个人在操场里围成一圈，将这N个人按顺时针方向从1到N编号，然后从第一个人起，每隔一个人让下一个人离开操场，显然，第一轮过后，具有偶数编号的人都离开了操场。依次做下去，直到操场只剩下一个人，记这个人的编号为J(N)，例如，J(5)=3，J(10)=5，等等。 则J(400)= 289 。 （提示：对N=2m+r进行分析，其中0≤r2m）。? NOIP2006 1．将 2006 个人分成若干不相交的子集，每个子集至少有 3 个人，并且： （1）在每个子集中，没有人认识该子集的所有人。 （2）同一子集的任何?3 个人中，至少有?2 个人互不认识。 （3）对同一子集中任何 2 个不相识的人，在该子集中恰好只有 1 个人认识这两个人。 则满足上述条件的子集最多能有 ???????401??????????????????????????????? 个？ ? ? 2．将边长为 n 的正三角形每边 n 等分，过每个分点分别做另外两边的平行线，得到若干个正三角形， 我们称为小三角形。正三角形的一条通路是一条连续的折线，起点是最上面的一个小三角形，终点是最 下面一行位于中间的小三角形。在通路中，只允许由一个小三角形走到另一个与其有公共边的且位于同 一行或下一行的小三角形，并且每个小三角形不能经过两次或两次以上（图中是 ?n=5 时一条通路的例 子）。设 n=10，则该正三角形的不同的通路的总数为_ ??9！?????? __。 ? ? NOIP2005 1. 将数组{32, 74, 25, 53, 28, 43, 86, 47}中的元素按从小到大的顺序排列，每次可以交换任 意两个元素，最少需要交换次。 解决 2. 取火柴游戏的规则如下：一堆火柴有N根，A、B两人轮流取出。每人每次可以取1 根或 2 根，最先没有火柴可取的人为败方，另一方为胜方。如果先取者有必胜策略则记为1， 先取者没有必胜策略记为0。当N 分别为100，200，300，400，500 时，先取者有无必 胜策略的标记顺序为（回答应为一个由0 和/或1 组成的字符串）。 11011 NOIP2004 75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700，可知有 10 名儿童没有玩过其中任何一种。 已知a, b, c, d, e, f, g七个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？如果可以，请以“a b”开头写出你的安排方案： abdfgec 。 NOIP2003 1. 无向图G有16条边，有3个4度顶点、4个3度顶点，其余顶点的度均小于3，则G至少_______个顶点。 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)≠ф，问至少安排_____天才能考完这6门课程。 2.平面上有三条平行直线，每条