noip1999-2008试题大全2.docVIP

2001 数的计算 Time Limit: 1000MS Memory Limit: 65536K 题目描述 我们要求找出具有下列性质数的个数(包含输入的自然数n): 先输入一个自然数n(n=1000),然后对此自然数按照如下方法进行处理: ??? 1.不作任何处理; ??? 2.在它的左边加上一个自然数,但该自然数不能超过原数的一半; ??? 3.加上数后,继续按此规则进行处理,直到不能再加自然数为止. 输入描述 一个自然数n 输出描述 所求数的个数 样例输入 6 样例输出 6 提示 对于样例,满足条件的数为,6,16,26,126,36,136 最大公约数和最小公倍数问题 Time Limit: 1000MS Memory Limit: 65536K 题目描述 输入二个正整数x0,y0(2=x0100000,2=y0=1000000),求出满足下列条件的P,Q的个数 ??? 1.P,A是正整数 ??? 2.要求P,Q以x0为最大公约数,以y0为最小公倍数. 试求:满足条件的所有可能的两个正整数的个数. 输入描述 x0,y0 输出描述 满足条件的P,Q的个数 样例输入 3 60 样例输出 4 提示 对于样例,P与Q分别为: 3??? 60 15??? 12 12??? 15 60??? 3 装箱问题 Time Limit: 1000MS Memory Limit: 65536K 题目描述 有一个箱子容量为V（正整数，0=V=20000），同时有n个物品（0=n=30），每个物品有一个体积（正整数）。 要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。 输入描述 第一行为一个整数，表示箱子容量；第二行一个整数，表示有n个物品；接下来n行，分别表示这n个物品的各自体积 输出描述 一个整数，表示箱子剩余空间。 样例输入 24 6 8 3 12 7 9 7 样例输出 0 一元三次方程求解 Time Limit: 1000MS Memory Limit: 65536K 题目描述 有形如：ax3+bx2+cx+d=0?这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。 输入描述 a???b???c???d 输出描述 三个不同的实根 样例输入 1 -5 -4 20 样例输出 -2.00 2.00 5.00 数的划分 Time Limit: 1000MS Memory Limit: 65536K 题目描述 将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。 例如：n=7，k=3，下面三种分法被认为是相同的。 (1，1，5)；(1，5，1)；(5，1，1)； 问有多少种不同的分法。 输入描述 n，k(6n=200，2=k=6) 输出描述 一个整数，即不同的分法。 样例输入 7 3 样例输出 4 提示 对于样例，四种分法为：(1，1，5)；(1，2，4)；(1，3，3)；(2，2，3)； 统计单词个数 Time Limit: 1000MS Memory Limit: 65536K 题目描述 给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份(1k=40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可包含this和is，选用this之后就不能包含th)。 单词在给出的一个不超过6个单词的字典中。要求输出最大的个数。 输入描述 第一行为一个正整数(0n=5)表示有n组测试数据 每组的第一行有二个正整数(p，k) p表示字串的行数；k表示分为k个部分。 接下来的p行，每行均有20个字符。 再接下来有一个正整数s，表示字典中单词个数。(1=s=6) 接下来的s行，每行均有一个单词。 输出描述 每行一个整数，分别对应每组测试数据的相应结果。 样例输入 1 1 3 thisisabookyouareaoh 4 is a ok sab 样例输出 7 提示 样例说明：this/isabookyoua/reaoh Car的旅行路线(缺图) Time Limit: 1000MS Memory Limit: 65536K 题目描述 又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第I个城市中高速铁路了的