湖南省长沙市第一中学-冲刺noip2010模拟试题

《湖南省长沙市第一中学-冲刺noip2010模拟试题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、冲刺NOIP2010模拟试题与解析（普及组复赛）湖南省长沙市第一中学周祖松试题名称数数分数树兔八哥与猎人运动会目录countfractionrabbit group输入文件名count.infraction.inrabbit.in group.in输出文件名count.outfraction.outrabbit.out group.out时限1秒1秒1秒1秒一、数数(count.pas/c/cpp)【问题描述】小可可正在学习怎么用手指数数。当爸爸问她“n(1≤n≤10)是多少”，小可可的回答就是竖起n个手指头。为了让问题简单一些，爸爸告诉她正确的手指表示方式：(

2、1)这个数可以用一只手或两只手表示；(2)如果这个数用两只手表示，大的数会先给出。比如爸爸问她“4是多少”，小可可有3种表示方法：(1)一只手竖起出4个手指头；（可以是左手也可是右手，只算一种）(2)一只手竖起出3个手指头，另一只手竖起出1个手指头；(3)一只手竖起出2个手指头，另一只手竖起出2个手指头；你的任务是，对于爸爸的提问，确认小可可有几种正确的回答方法。【输入】输入文件count.in共一行为一个1到10之间的整数。【输出】输出文件count.out共一行为一个整数，表示方法总数。【样例输入】4【样例输出】3二、分数树(fraction.pas/c/c

3、pp)【问题描述】十九世纪的时候，MorizStern(1858)与AchilleBrocot(1860)发明了“一棵树”。据说，经由一些简单的规则而产生的这一棵树上，可以包含零以上所有的有理数。这棵树看起来大致这样：你观察出规则了吗？首先,他们在第一列放两个“分数”，第一个是0/1，代表0；第二个是1/0，代表无穷大。接着他们一列一列地产生这棵树,当他们要产生第k+1列的时候,就先把前k列所有的分数按照大小排成一列（假设有n个），在这些数之间会有n-1个间隔，那么第k+1列就准备产生n-1个数，其值的分子恰好是左右两个数的分子的和、分母是左右两个数的分母的和。

4、例如，2/3，而它的2就是左边1/2的1和右边1/1的分子1相加的结果；而2/3的3，则是1/2的2加上1/1的分母1而得。从这棵树中，我们可以看出，每个正的最简分数在这棵树中恰好出现一次，我们用字母“L”和“R”分别表示从树根(1/1)开始的一步“往左走”和“往右走”，则每一个数都可以由L和R组成的序列表示。例如，LRRL表示从1/1开始往左走一步到1/2，然后往右走到2/3，再往右走到3/4，最后往左走到5/7。我们可以把LRRL看作5/7的一种表示法。几乎每个正分数均有唯一的方法表示成一个由L和R组成的序列。给定一个分数，输出它的LR表示法。【输入】输入文

5、件fraction.in有两个互素的正整数m和n(1≤n，m≤1000)。【输出】输出文件fraction.out为对应的LR表示法。【输入】57【输出】LRRL三、兔八哥与猎人(rabbit.pas/c/cpp)【问题描述】兔八哥躲藏在树林旁边的果园里。果园有M×N棵树，组成一个M行N列的矩阵，水平或垂直相邻的两棵树的距离为1。兔八哥在一棵果树下。猎人背着猎枪走进了果园，他爬上一棵果树，准备杀死兔八哥。如果猎人与兔八哥之间没有其它的果树，猎人就可以看到兔八哥。现己知猎人和兔八哥的位置，编写程序判断兔子所在的位置是否安全【输入文件】输入文件rabbit.in第一

6、行为n，表示有n(n≤100,000)组数据，每组数据的第一行为两个正整数ax和ay，表示猎人的位置，第二行为两个正整数bx和by，表示兔八哥的位置(1≤ax,ay,bx,by≤100,000,000)。【输出文件】输出文件rabbit.out共有n行，每行为“yes”或“no”表示兔八哥的位置是否安全。【输入1】11112【输出1】no【输入2】11113【输出2】yes四、运动会(group.pas/c/cpp)【问题描述】在一次运会上，有一个比赛项目，共有N个人参加比赛，要将这N个人分组，每组人数不少于K个，问有多少种分组方式？比如有16个运动员，每组人数

7、不少于5个，共有6种分组方式：(1)分一组，为16人；(2)分二组，分别为11人、5人；(3)分二组，分别为10人、6人；(4)分二组，分别为9人、7人；(5)分二组，分别为8人、8人；(6)分三组，分别为6人、5人、5人。注意：6+5+5，5+6+5，5+5+6为同一种，只算一种分组方式；【输入文件】输入文件group.in共一行为两个整数N,K。表示有N个运动员分组，每组不少于K个人(1≤K≤N≤500)。【输出文件】输出文件group.out共一行为一个整数，表示分组数。【输入】165【输出】6