noip2009提高组初赛

NOIP2009提高组解题报告

满意答案第二题(Hankson 的趣味题, son):

Gcd(x,a0)=a1, Gcd(x,b0)=xb0/b1

设f(a,b) 代表b这个质因子在a中有多少个.

对于a0的任意质因子t, 若f(a0,t)=f(a1,t) 则只需保证f(x,t)≥f(a1,t), 否则f(x,t)=f(a1,t)

对于b1的任意质因子t, 若f(b1,t)=f(b0,t) 则只需保证0≤f(x,t)≤f(b1,t), 否则f(x,t)=f(b1,t)

由于x的所有因子都是b1的子集, 所以我们只需对b1的质因子按如上方法逐个检查这个质因子在x里面的取值范围(若为空则说明无解), 并按照乘法原理统计即可.

关于分解质因子: 由于b1不会超过2*10^9, 大于50000的质因子不会超过1个, 所以我们只要打出50000以内的素数表即可, 若最后除剩的b1仍未除尽, 说明此时b1一定是一个大于50000的素数.

第三题(最优贸易, trade):

做法1:

设Low[i]为从1到i当前所有路径中最便宜的价格. Profit[i]为从1到i当前所有路径中最大获利. 初始时Low[1]=P[1], Low[2..n]=infinity, Profit

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

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

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

一． 单项选择题 （共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里包含了键盘、鼠标、声卡、显卡、打

NOIP提高组初赛试题汇编(2002-2009)noip考试者必备我也是马上要考了!!!

第八届全国青少年信息学奥林匹克联赛（第八届全国青少年信息学奥林匹克联赛（NOIP2002）初赛试题

（提高组PASCAL语言二小时完成）一．选择一个正确答案代码（A/B/C/D）填入每题的括号内（选择一个正确答案代码（A/B/C/D），填入每题的括号内（每题1.5分，多选无分，多选无分，

共30分）

1．微型计算机的问世是由于（）的出现。

A）中小规模集成电路B）晶体管电路C）（超）大规模集成电路D）电子管电路2．中央处理器（CPU）能访问的最大存储器容量取决于（）。

A）地址总线B）数据总线C）控制总线D）实际内存容量3．十进制书11/128可用二进制数码序列表示为：（）。

A）1011/1000000B）1011/100000000C）0.001011D）0.00010114．算式（2047）10－（3FF）16＋（2000）8的结果是（）。

A）（2048）10B）（2049）10C）（3746）8D）（1AF7）165．已知x=（0.1011010）2，则[x/2]补=（）2。

A）0.1011101B）11110110C）0.0101101D）0.1001106

ＮＯＩＰ初赛试题（提高组Ｃ语言） 第十届（2004） 三．问题求解（ 共 2 题，每题 5 分，共计 10 分 ） 1.75 名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中 20 人这三种东西都玩过， 55 人至少玩过其中的两种。若每样乘坐一次的费用是 5 元，游乐场总共收入 700 ，可知有 名儿童没有玩过其中任何一种。 分析与解：已知总人数为75，总金额是700，玩3项的人数是20，花费的金额是5*3*20=300，玩2项的人数是55-20=35，花费的金额是5*2*35=350，剩余金额是700-300-350=50，只能玩50/5=10项次，即玩1项的人数是10，所以玩0项的人数是：75-20-35-10=10 人数 金额 总共 75 700 玩3项 玩2项 玩1项 玩0项 20 300 35 350 ？ 0 2.已知 a, b, c, d, e, f, g 七个人中， a 会讲英语； b 会讲英语和汉语； c 会讲英语、意大利语和俄语； d 会讲汉语和日语； e 会讲意大利语和德语； f 会讲俄语、日语和法语； g 会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈

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

（ 提高组C 语言二小时完成）

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

一.单项选择题（共10题，每题1.5分，共计15分。每题有且仅有一个正确选项。）

1.与16进制数A1.2等值的10进制数是（ ）

A.101.2 B.111.4 C.161.125 D.177.25

2.一个字节（byte）由（ ）个二进制位组成。

A.8 B.16 C.32 D.以上都有可能

3.一下逻辑表达式的值恒为真的是（ ）

A.P∨（┐P∧Q)∨（┐P∧┐Q) B.Q∨（┐P∧Q)∨(P∨┐Q)

C.P∨Q∨(P∧┐Q)∨(┐P∧Q) D.P∨┐Q∨(P∧┐Q)∨(┐P∧┐Q)

4.Linux下可执行文件的默认扩展名为（ ）

A.exe B.com C.dll D.都不是

5.如果在某个进制下等式7*7=41成立，那么在该进制下等式12*12=（ ）也成立。

A.100 B.144 C.164 D

ＮＯＩＰ初赛试题（提高组Ｃ语言） 第十届（2004） 三．问题求解（ 共 2 题，每题 5 分，共计 10 分 ） 1.75 名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中 20 人这三种东西都玩过， 55 人至少玩过其中的两种。若每样乘坐一次的费用是 5 元，游乐场总共收入 700 ，可知有 名儿童没有玩过其中任何一种。 分析与解：已知总人数为75，总金额是700，玩3项的人数是20，花费的金额是5*3*20=300，玩2项的人数是55-20=35，花费的金额是5*2*35=350，剩余金额是700-300-350=50，只能玩50/5=10项次，即玩1项的人数是10，所以玩0项的人数是：75-20-35-10=10 人数 金额 总共 75 700 玩3项 玩2项 玩1项 玩0项 20 300 35 350 ？ 0 2.已知 a, b, c, d, e, f, g 七个人中， a 会讲英语； b 会讲英语和汉语； c 会讲英语、意大利语和俄语； d 会讲汉语和日语； e 会讲意大利语和德语； f 会讲俄语、日语和法语； g 会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈

NOIP初赛模拟试题 by OI Store （提高组 Pascal语言 二小时完成）

一、单项选择题（共10题，每题1.5分，共计15分。每题有且仅有一个正确答案。）

1. 建立了计算机最主要的结构原理的人是（ ）。

A. 图灵 B. 比尔·盖茨 C. 冯·诺伊曼 D. 克拉拉·丹 E. 哥德尔 2. 设a、b、c是三个布尔型(boolean)的变量，则表达式(a∨?b)∧(b∨?c)∧(c∨?a)∧(a∧?a)∧(b∧?b)的值（ ）。 A. 始终为true B. 始终为false

C. 当且仅当c为true时为false

D. 当且仅当a与b均为true时为true E. 依赖于a、b、c三者的值 3. 设a、b为两个浮点(float)型变量，下面的表达式中最有可能为真的是（ ）。 A. a=b

B. a*a+2*a*b+b*b=(a+b)*(a+b) C. (a+b)*(a-b)+b*b-a*a<0.0001 D. a/b=1/(b/a)

E. sqrt(a)*sqrt(b)=sqrt(a*b) 4. 下面的数据中，在编程中用长整型(longint)表示最恰当的是（ ）。 A. 宇宙中的原子数目

B. 一头大象的体重（用

第八届全国青少年信息学奥林匹克联赛（NOIP2002）初赛试题

（提高组 PASCAL语言 二小时完成）

审定：全国青少年信息学奥林匹克竞赛科学委员会 主管：中国科协、教育部 主办：中国计算机学会

承办：江苏省科协青少年科技中心

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

一． 选择一个正确答案代码（A/B/C/D），填入每题的括号内（每题1.5分，多选无分，

共30分）

1． 微型计算机的问世是由于（ ）的出现。

A）中小规模集成电路 B）晶体管电路 C）（超）大规模集成电路 D）电子管电路 2． 中央处理器（CPU）能访问的最大存储器容量取决于（ ）。

A）地址总线 B）数据总线 C）控制总线 D）实际内存容量 3． 十进制书11/128可用二进制数码序列表示为：（ ）。

A）1011/1000000 B）1011/100000000 C）0.001011 D）0.0001011 4． 算式（2047）10 －（3FF）16 ＋（2000）8的结果是（ ）。 A）（2048）10 B）（2049）10 C）（3746）8 D）（1AF7）16 5． 已知x =（0.1011010）2

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

（ 提高组C 语言二小时完成）

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

一.单项选择题（共10题，每题1.5分，共计15分。每题有且仅有一个正确选项。）

1.与16进制数A1.2等值的10进制数是（ ）

A.101.2 B.111.4 C.161.125 D.177.25

2.一个字节（byte）由（ ）个二进制位组成。

A.8 B.16 C.32 D.以上都有可能

3.一下逻辑表达式的值恒为真的是（ ）

A.P∨（┐P∧Q)∨（┐P∧┐Q) B.Q∨（┐P∧Q)∨(P∨┐Q)

C.P∨Q∨(P∧┐Q)∨(┐P∧Q) D.P∨┐Q∨(P∧┐Q)∨(┐P∧┐Q)

4.Linux下可执行文件的默认扩展名为（ ）

A.exe B.com C.dll D.都不是

5.如果在某个进制下等式7*7=41成立，那么在该进制下等式12*12=（ ）也成立。

A.100 B.144 C.164 D

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

（ 提高组C 语言二小时完成）

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

一.单项选择题（共10题，每题1.5分，共计15分。每题有且仅有一个正确选项。）

1.与16进制数A1.2等值的10进制数是（ ）

A.101.2 B.111.4 C.161.125 D.177.25

2.一个字节（byte）由（ ）个二进制位组成。

A.8 B.16 C.32 D.以上都有可能

3.一下逻辑表达式的值恒为真的是（ ）

A.P∨（┐P∧Q)∨（┐P∧┐Q) B.Q∨（┐P∧Q)∨(P∨┐Q)

C.P∨Q∨(P∧┐Q)∨(┐P∧Q) D.P∨┐Q∨(P∧┐Q)∨(┐P∧┐Q)

4.Linux下可执行文件的默认扩展名为（ ）

A.exe B.com C.dll D.都不是

5.如果在某个进制下等式7*7=41成立，那么在该进制下等式12*12=（ ）也成立。

A.100 B.144 C.164 D