[NOIP2009 普及组] 分数线划定

一、急求NOIP2009普及组试题

NOIP2009普及组复赛试题

1．多项式输出

(poly.pas/c/cpp)

【问题描述】

一元 n次多项式可用如下的表达式表示：

1 0

1

1 f(x) a x a xn... a x a

n

n

n=+?+++

?，≠ 0 n a

其中，

i

i a x称为i次项， i a称为i次项的系数。给出一个一元多项式各项的次数和系

数，请按照如下规定的格式要求输出该多项式：

1.多项式中自变量为x，从左到右按照次数递减顺序给出多项式。

2.多项式中只包含系数不为0的项。

3.如果多项式n次项系数为正，则多项式开头不出现“+”号，如果多项式n次项系

数为负，则多项式以“-”号开头。

4.对于不是最高次的项，以“+”号或者“-”号连接此项与前一项，分别表示此项

系数为正或者系数为负。紧跟一个正整数，表示此项系数的绝对值（如果一个高于0次的项，

其系数的绝对值为1，则无需输出1）。如果x的指数大于1，则接下来紧跟的指数部分的形

式为“x^b”，其中b为x的指数；如果x的指数为1，则接下来紧跟的指数部分形式为“x”；

如果x的指数为0，则仅需输出系数即可。

5.多项式中，多项式的开头、结尾不含多余的空格。

【输入】

输入文件名为 poly.in，共有2行

第一行 1个整数，n，表示一元多项式的次数。

第二行有 n+1个整数，其中第i个整数表示第n-i+1次项的系数，每两个整数之间用空

格隔开。

【输出】

输出文件 poly.out共1行，按题目所述格式输出多项式。

【输入输出样例 1】

poly.in poly.out

5

100-1 1-3 0 10

100x^5-x^4+x^3-3x^2+10

【输入输出样例2】

poly.in poly.out

3

-50 0 0 1

-50x^3+1

【数据范围】

1≤ n≤ 100，多项式各次项系数的绝对值均不超过100。

全国信息学奥林匹克联赛（NOIP2009）复赛普及组

第 3页共 6页

2．分数线划定

(score.pas/c/cpp)

【问题描述】

世博会志愿者的选拔工作正在 A市如火如荼的进行。为了选拔最合适的人才，A市对

所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根

据计划录取人数的150%划定，即如果计划录取m名志愿者，则面试分数线为排名第m*150%

（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有

选手。

现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成

绩。

【输入】

输入文件名为 score.in。

第一行，两个整数n，m（5≤ n≤ 5000，3≤ m≤ n），中间用一个空格隔开，其

中n表示报名参加笔试的选手总数，m表示计划录取的志愿者人数。输入数据保证m*150%

向下取整后小于等于n。

第二行到第 n+1行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号k

（1000≤ k≤ 9999）和该选手的笔试成绩s（1≤ s≤ 100）。数据保证选手的报名号各

不相同。

【输出】

输出文件 score.out。

第一行，有两个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为

进入面试的选手的实际人数。

从第二行开始，每行包含两个整数，中间用一个空格隔开，分别表示进入面试的选手

的报名号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的

顺序输出。

【输入输出样例】

score.in score.out

6 3

1000 90

3239 88

2390 95

7231 84

1005 95

1001 88

88 5

1005 95

2390 95

1000 90

1001 88

3239 88

【样例说明】

m*150%= 3*150%= 4.5，向下取整后为4。保证4个人进入面试的分数线为88，但因为88

有重分，所以所有成绩大于等于88的选手都可以进入面试，故最终有5个人进入面试。

全国信息学奥林匹克联赛（NOIP2009）复赛普及组

第 4页共 6页

3．细胞分裂

(cell.pas/c/cpp)

【问题描述】

Hanks博士是BT(Bio-Tech，生物技术)领域的知名专家。现在，他正在为一个细胞实

验做准备工作：培养细胞样本。

Hanks博士手里现在有N种细胞，编号从1~N，一个第i种细胞经过1秒钟可以分裂为

Si个同种细胞（Si为正整数）。现在他需要选取某种细胞的一个放进培养皿，让其自由分裂，

进行培养。一段时间以后，再把培养皿中的所有细胞平均分入M个试管，形成M份样本，

用于实验。Hanks博士的试管数M很大，普通的计算机的基本数据类型无法存储这样大的

M值，但万幸的是，M总可以表示为m1的m2次方，即2

1

M= m m，其中m1，m2均为基本

数据类型可以存储的正整数。

注意，整个实验过程中不允许分割单个细胞，比如某个时刻若培养皿中有4个细胞，

Hanks博士可以把它们分入2个试管，每试管内2个，然后开始实验。但如果培养皿中有5

个细胞，博士就无法将它们均分入2个试管。此时，博士就只能等待一段时间，让细胞们继

续分裂，使得其个数可以均分，或是干脆改换另一种细胞培养。

为了能让实验尽早开始，Hanks博士在选定一种细胞开始培养后，总是在得到的细胞“刚

好可以平均分入M个试管”时停止细胞培养并开始实验。现在博士希望知道，选择哪种细

胞培养，可以使得实验的开始时间最早。

【输入】

输入文件名为 cell.in，共有三行。

第一行有一个正整数 N，代表细胞种数。

第二行有两个正整数 m1，m2，以一个空格隔开， 2

1

m m即表示试管的总数M。

第三行有 N个正整数，第i个数Si表示第i种细胞经过1秒钟可以分裂成同种细胞的个

数。

【输出】

输出文件 cell.out共一行，为一个整数，表示从开始培养细胞到实验能够开始所经过的

最少时间（单位为秒）。

如果无论 Hanks博士选择哪种细胞都不能满足要求，则输出整数-1。

【输入输出样例 1】

cell.in cell.out

1

2 1

3

-1

【输入输出样例1说明】

经过 1秒钟，细胞分裂成3个，经过2秒钟，细胞分裂成9个，……，可以看出无论怎么分

裂，细胞的个数都是奇数，因此永远不能分入2个试管。

全国信息学奥林匹克联赛（NOIP2009）复赛普及组

第 5页共 6页

【输入输出样例 2】

cell.in cell.out

2

24 1

30 12

2

【输入输出样例2说明】

第 1种细胞最早在3秒后才能均分入24个试管，而第2种最早在2秒后就可以均分（每

试管144/(241)=6个）。故实验最早可以在2秒后开始。

【数据范围】

对于 50%的数据，有2

1

m m≤ 30000。

对于所有的数据，有1≤N≤ 10000，1≤m1≤ 30000，1≤m2≤ 10000，1≤ Si≤ 2,000,000,000。

4．道路游戏

(game.pas/c/cpp)

【问题描述】

小新正在玩一个简单的电脑游戏。

游戏中有一条环形马路，马路上有n个机器人工厂，两个相邻机器人工厂之间由一小段

马路连接。小新以某个机器人工厂为起点，按顺时针顺序依次将这n个机器人工厂编号为

1~n，因为马路是环形的，所以第n个机器人工厂和第1个机器人工厂是由一段马路连接在

一起的。小新将连接机器人工厂的这n段马路也编号为1~n，并规定第i段马路连接第i个

机器人工厂和第i+1个机器人工厂（1≤ i≤ n-1），第n段马路连接第n个机器人工厂和第1

个机器人工厂。

游戏过程中，每个单位时间内，每段马路上都会出现一些金币，金币的数量会随着时间

发生变化，即不同单位时间内同一段马路上出现的金币数量可能是不同的。小新需要机器人

的帮助才能收集到马路上的金币。所需的机器人必须在机器人工厂用一些金币来购买，机器

人一旦被购买，便会沿着环形马路按顺时针方向一直行走，在每个单位时间内行走一次，即

从当前所在的机器人工厂到达相邻的下一个机器人工厂，并将经过的马路上的所有金币收集

给小新，例如，小新在i（1≤ i≤ n）号机器人工厂购买了一个机器人，这个机器人会从i号

机器人工厂开始，顺时针在马路上行走，第一次行走会经过i号马路，到达i+1号机器人工

厂（如果i=n，机器人会到达第1个机器人工厂），并将i号马路上的所有金币收集给小新。

游戏中，环形马路上不能同时存在2个或者2个以上的机器人，并且每个机器人最多能

够在环形马路上行走p次。小新购买机器人的同时，需要给这个机器人设定行走次数，行走

次数可以为1~p之间的任意整数。当马路上的机器人行走完规定的次数之后会自动消失，小

新必须立刻在任意一个机器人工厂中购买一个新的机器人，并给新的机器人设定新的行走次

数。

以下是游戏的一些补充说明：

1.游戏从小新第一次购买机器人开始计时。

2.购买机器人和设定机器人的行走次数是瞬间完成的，不需要花费时间。

3.购买机器人和机器人行走是两个独立的过程，机器人行走时不能购买机器人，购买

完机器人并且设定机器人行走次数之后机器人才能行走。

4.在同一个机器人工厂购买机器人的花费是相同的，但是在不同机器人工厂购买机器

人的花费不一定相同。

5.购买机器人花费的金币，在游戏结束时再从小新收集的金币中扣除，所以在游戏过

程中小新不用担心因金币不足，无法购买机器人而导致游戏无法进行。也因为如此，

游戏结束后，收集的金币数量可能为负。

现在已知每段马路上每个单位时间内出现的金币数量和在每个机器人工厂购买机器人

需要的花费，请你告诉小新，经过m个单位时间后，扣除购买机器人的花费，小新最多能

收集到多少金币。

【输入】

输入文件名为 game.in。

第一行 3个正整数，n，m，p，意义如题目所述。

接下来的 n行，每行有m个正整数，每两个整数之间用一个空格隔开，其中第i行描

述了i号马路上每个单位时间内出现的金币数量（1≤金币数量≤ 100），即第i行的第j

（1≤ j≤m）个数表示第j个单位时间内i号马路上出现的金币数量。

最后一行，有 n个整数，每两个整数之间用一个空格隔开，其中第i个数表示在i号机

器人工厂购买机器人需要花费的金币数量（1≤金币数量≤ 100）。

【输出】

输出文件 game.out共一行，包含1个整数，表示在m个单位时间内，扣除购买机器人

花费的金币之后，小新最多能收集到多少金币。

【输入输出样例】

game.in game.out

2 3 2

1 2 3

2 3 4

1 2

5

【数据范围】

对于 40%的数据，2≤ n≤ 40，1≤m≤ 40。

对于 90%的数据，2≤ n≤ 200，1≤m≤ 200。

对于 100%的数据，2≤ n≤ 1000，1≤m≤ 1000，1≤ p≤m

二、谁能告诉我noip2009普及组的细胞分裂的解题思路

总的来说就算是分解质因数

由于m1<=30000,m2<=10000，根本无法直接计算，所以需要

通过数学分析得出答案。如果一个数能够整除另一个数，那么这个数因数分解后一定有另一个数所有的元素，且每个元素个数均大于等于另一个数相同元素的个数。因此我们可以先对m1进行因数分解，并将对应元素的个数乘以m2。之后读入每个数，判断该数因数分解后是否有m1中所有的元素。如果有的话，则计算该细胞最大的分裂次数，即对应m1种元素个数/si中元素个数后向上取整。最后更新答案即可。

注意因数分解中1比较特殊，所以要单独判断一下。

三、求noip2009普及组初赛试卷

第十五届全国青少年信息学奥林匹克联赛初赛试题

（普及组 Pascal语言二小时完成）

●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●

一．单项选择题（共20题，每题1.5分，共计30分。每题有且仅有一个正确答案。）

1、关于图灵机下面的说法哪个是正确的：

A)图灵机是世界上最早的电子计算机。

B)由于大量使用磁带操作，图灵机运行速度很慢。

C)图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。

D)图灵机只是一个理论上的计算模型。

2、关于计算机内存下面的说法哪个是正确的：

A)随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定的。

B) 1MB内存通常是指1024*1024字节大小的内存。

C)计算机内存严格说来包括主存（memory）、高速缓存（cache）和寄存器（register）三个部分。

D)一般内存中的数据即使在断电的情况下也能保留2个小时以上。

3、关于BIOS下面说法哪个是正确的：

A) BIOS是计算机基本输入输出系统软件的简称。

B) BIOS里包含了键盘、鼠标、声卡、显卡、打印机等常用输入输出设备的驱动程序。

C) BIOS一般由操作系统厂商来开发完成。

D) BIOS能供提各种文件拷贝、**、删除以及目录维护等文件管理功能。

4、关于CPU下面哪个说法是正确的：

A) CPU全称为中央处理器（或中央处理单元）。

B) CPU可以直接运行汇编语言。

C)同样主频下，32位的CPU比16位的CPU运行速度快一倍。

D) CPU最早是由Intel公司发明的。

5、关于ASCII，下面哪个说法是正确的：

A) ASCII码就是键盘上所有键的唯一编码。

B)一个ASCII码使用一个字节的内存空间就能够存放。

C)最新扩展的ASCII编码方案包含了汉字和其他欧洲语言的编码。

D) ASCII码是英国人主持制定并推广使用的。

6、下列软件中不是计算机操作系统的是：

A) Windows B) Linux C) OS/2 D) WPS

7、关于互联网，下面的说法哪一个是正确的：

A)新一代互联网使用的IPv6标准是IPv5标准的升级与补充。

B)互联网的入网主机如果有了域名就不再需要IP地址。

C)互联网的基础协议为TCP/IP协议。

D)互联网上所有可下载的软件及数据资源都是可以合法****的。

8、关于HTML下面哪种说法是正确的：

A） HTML实现了文本、图形、声音乃至视频信息的统一编码。

B） HTML全称为超文本标记语言。

C）网上广泛使用的 Flas***都是由HTML编写的。

D） HTML也是一种高级程序设计语言。

9、关于程序设计语言，下面哪个说法是正确的：

A)加了注释的程序一般会比同样的没有加注释的程序运行速度慢。

B)高级语言开发的程序不能使用在低层次的硬件系统（如：自控机床）或低端手机上。

C)高级语言相对于低级语言更容易实现跨平台的移植。

D)以上说法都不对。

10、已知大写字母A的ASCII编码为65（十进制），则大写字母J的十进制ASCII编码为：

A) 71 B) 72 C) 73 D)以上都不是

11、十进制小数125.125对应的八进制数是

A) 100.1 B) 175.175 C) 175.1 D) 100.175

12、有六个元素FEDCBA从左至右依次顺序进栈，在进栈过程中会有元素被弹出栈。问下列哪一个不可能是合法的出栈序列？

A) EDCFAB B) DECABF C) CDFEBA D) BCDAEF

13、表达式a*(b+c)-d的后缀表达式是：

A) abcd*+- B) abc+*d- C) abc*+d- D)-+*abcd

14、一个包含n个分支结点（非叶结点）的非空二叉树，它的叶结点数目最多为：

A) 2n+ 1 B) 2n-1 C) n-1 D) n+1

15、快速排序最坏情况下的算法复杂度为：

A) O(log2n) B) O(n) C) O(nlog2n) D) O(n2)

16.有一个由4000个整数构成的顺序表，假定表中的元素已经按升序排列，采用二分查找定位一个元素。则最多需要几次比较就能确定是否存在所查找的元素：

A) 11次 B) 12次 C) 13次 D) 14次

17、排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪种排序算法是不稳定的：

A)冒泡排序 B)插入排序 C)归并排序 D)快速排序

18、已知n个顶点的有向图，若该图是强连通的（从所有顶点都存在路径到达其他顶点），则该图中最少有多少条有向边？

A) n B) n+1 C) n-1 D) n*(n-1)

19、全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资源，请问全国信息学奥林匹克官方网站的网址是：

A) http://www.noi.com/ B) http://www.noi.org/

C) http://www.noi.cn/ D) http://www.xinxixue.com/

20、在参加NOI系列竞赛过程中，下面哪一种行为是不被严格禁止的：

A)携带书写工具，手表和不具有通讯功能的电子词典进入赛场。

B)在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数。

C)通过互联网搜索取得解题思路。

D)在提交的程序中启动多个进程以提高程序的执行效率。

二．问题求解（共2题，每空5分，共计10分）

1．小陈现有2个任务A，B要完成，每个任务分别有若干步骤如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如……a2->b2->a3->b3……是合法的，而……a2->b3->a3->b2……是不合法的。小陈从B任务的b1步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务A，其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有种。

2．有如下的一段程序：

1. a:=1;

2. b:=a;

3. d:=-a;

4. e:=a+d;

5. c:=2*d;

6. f:=b+e-d;

7. g:=a*f+c;

现在要把这段程序分配到若干台（数量充足）用电缆连接的PC上做并行执行。每台PC执行其中的某几个语句，并可随时通过电缆与其他PC通讯，交换一些中间结果。假设每台PC每单位时间可以执行一个语句，且通讯花费的时间不计。则这段程序最快可以在单位时间内执行完毕。注意：任意中间结果只有在某台PC上已经得到，才可以被其他PC引用。例如若语句4和6被分别分配到两台PC上执行，则因为语句6需要引用语句4的计算结果，语句6必须在语句4之后执行。

三．阅读程序写结果（共4题，每题8分，共计32分）

1．

var

a, b: integer;

function work(a, b: integer): integer;

begin

if a mod b<> 0 then

work:= work(b, a mod b)

else

work:= b;

end;

begin

read(a, b);

writeln(work(a, b));

end.

输入：20 12

输出：_______

2．

var

a, b: array[0..2] of integer;

i, j, tmp: integer;

begin

for i:= 0 to 2 do

read(b[i]);

for i:= 0 to 2 do

begin

a[i]:= 0;

for j:= 0 to i do

begin

inc(a[i], b[j]);

inc(b[a[i] mod 3], a[j]);

end;

end;

tmp:= 1;

for i:= 0 to 2 do

begin

a[i]:= a[i] mod 10;

b[i]:= b[i] mod 10;

tmp:= tmp*(a[i]+ b[i]);

end;

writeln(tmp);

end.

输入：2 3 5

输出：_______

3．

const c= 2009;

var

n, p, s, i, j, t: integer;

begin

read(n, p);

s:= 0; t:= 1;

for i:= 1 to n do

begin

t:= t* p mod c;

for j:= 1 to i do

s:=(s+ t) mod c;

end;

writeln(s);

end.

输入：11 2

输出：

4．

var

a: string;

n: integer;

procedure getnext(var str: string);

var

l, i, j, k: integer;

temp: char;

begin

l:= length(str);

k:= l- 1;

while(k>=1) and(str[k]>str[k+1]) do

dec(k);

i:= k+ 1;

while(i<=l) and(str[i]>str[k]) do

inc(i);

temp:= str[k];

str[k]:= str[i-1];

str[i-1]:= temp;

for i:= l downto k+ 1 do

for j:= k+ 1 to i- 1 do

if str[j]> str[j+1] then

begin

temp:= str[j];

str[j]:= str[j+1];

str[j+1]:= temp;

end;

end;

begin

read(a);

read(n);

while n> 0 do

begin

getnext(a);

dec(n);

end;

write(a);

end.

输入：NOIP 3

输出：

四．完善程序(前8空，每空3分，后2空，每空2分，共28分)

1．（最大连续子段和）给出一个数列（元素个数不多于100），数列元素均为负整数、正整数、0。请找出数列中的一个连续子数列，使得这个子数列中包含的所有元素之和最大，在和最大的前提下还要求该子数列包含的元素个数最多，并输出这个最大和以及该连续子数列中元素的个数。例如数列为4，-5，3，2，4时，输出9和3；数列为1 2 3-5 0 7 8时，输出16和7。

var

a: array[1..100] of integer;

n, i, ans, len, tmp, beg: integer;

begin

read(n);

for i:= 1 to n do

read(a[i]);

tmp:= 0;

ans:= 0;

len:= 0;

beg:=①;

for i:= 1 to n do

begin

if tmp+ a[i]> ans then

begin

ans:= tmp+ a[i];

len:= i- beg;

end

else if(②) and(i- beg> len) then

len:= i- beg;

if tmp+ a[i]③ then

begin

beg:=④;

tmp:= 0;

end

else

⑤;

end;

writeln(ans,'', len);

end.

2.(国王放置)在n*m的棋盘上放置k个国王，要求k个国王互相不攻击，有多少种不同的放置方法。假设国王放置在第(x,y)格，国王的攻击的区域是:(x-1,y-1),(x-1,y),(x-1,y+1),(x,y-1),(x,y+1),(x+1,y-1),(x+1,y),(x+1,y+1)。读入三个数n,m,k，输出答案。题目利用回溯法求解。棋盘行标号为0~n-1，列标号为0~m-1。

var

n, m, k, ans: integer;

hash: array[0..4, 0..4] of integer;

procedure work(x, y, tot: integer);

var

i, j: integer;

begin

if tot= k then

begin

inc(ans);

exit;

end;

repeat

while hash[x, y]<> 0 do

begin

inc(y);

if y= m then

begin

inc(x);

y:=①;

end;

if x= n then

exit;

end;

for i:= x- 1 to x+ 1 do

if(i>= 0) and(i< n) then

for j:= y- 1 to y+ 1 do

if(j>= 0) and(j< m) then

②;

③;

for i:= x- 1 to x+ 1 do

if(i>= 0) and(i< n) then

for j:= y- 1 to y+ 1 do

if(j>= 0) and(j< m) then

④;

inc(y);

if y= m then

begin

inc(x);

y:= 0;

end;

if x= n then

exit;

until false;

end;

begin

read(n, m, k);

ans:= 0;

fillchar(hash, sizeof(hash), 0);

⑤;

writeln(ans);

end.

文章分享结束，[NOIP2009 普及组] 分数线划定和急求NOIP2009普及组试题的答案你都知道了吗？欢迎再次光临本站哦！