noi2010笔试题

2010年阜阳市中学生信息学奥林匹克竞赛注意事项：1．务必看清题目，严格按照要求的格式输入、输出。

2．在调试程序时请先用题目中的样例数据，然后再自行设计多组测试数据进行调试。

3．文件的命名规则：程序文件的扩展名采用所用的语言环境的默认扩展名。

程序文件主文件名为每题题目后括号内的文件名，输入、输出文件名为每题输入、输出文件括号内的文件名。

4．选手在竞赛结束时D:盘上建立以自己参赛号命名的文件夹，参赛号中的字母是半角英文大写，并将所完成的各题的源程序拷贝到该文件夹中，特别注意的是不要．．在考号文件夹内再建立文件夹．．．．．．．．．．．．．。

一、星际游戏（game）随着人类对地球资源肆虐的挖掘，对自然环境疯狂的破坏，地球越来越不适合人类居住，无奈之下，只有派出一批探险队员在茫茫太空中寻觅一个适合人类生存的星球。

漫长的星际之旅让所有的探险队员感到越来越无聊，指挥官担心队员们会因长年无所事事而导致脑残，于是找出一些弱智的游戏让队员们动动脑子，两个数相减对哪些已经脑残的队员来说已经是个很难的问题了，更何况让他们在一秒内算出，有些人开始作弊。

请你写个程序帮助他们。

输入文件（game.in）一行，两个整数a，b。

输出文件（game.out）一行，a-b的结果。

样例输入：3 2样例输出：1数据范围：0≤a，b≤2100000000二、树的年龄（age）经过许多年的探索，探险队员们来到了一个神秘的行星——潘多拉星球，那里的美景简直无法用语言来形容，高达900英尺的参天巨树、星罗棋布飘浮在空中的群山、色彩斑斓充满奇特植物的茂密雨林、晚上各种动植物还会发出光，就如同梦中的奇幻花园。

在潘多拉星球上最神奇的莫过于树，它们也有年轮。

地球上的树每一年生长出一个年轮，但是潘多拉星球上的树长出第一个年轮需要1年，再过2年长出第二个年轮，再过4年长出第三个年轮，再过8年长出第四个年轮……再过2n-1年长出第n个年轮。

地球人在潘多拉星球上发现了一棵树有n个年轮，请你编写程序计算出这棵树至少存活了多少年。

航空管制【问题描述】世博期间，上海的航空客运量大大超过了平时，随之而来的航空管制也频频发生。

最近，小X就因为航空管制，连续两次在机场被延误超过了两小时。

对此，小X 表示很不满意。

在这次来烟台的路上，小X不幸又一次碰上了航空管制。

于是小X开始思考关于航空管制的问题。

假设目前被延误航班共有n个，编号为1至n。

机场只有一条起飞跑道，所有的航班需按某个顺序依次起飞（称这个顺序为起飞序列）。

定义一个航班的起飞序号为该航班在起飞序列中的位置，即是第几个起飞的航班。

起飞序列还存在两类限制条件：∙第一类（最晚起飞时间限制）：编号为i的航班起飞序号不得超过k i;∙第二类（相对起飞顺序限制）：存在一些相对起飞顺序限制(a, b)，表示航班a的起飞时间必须早于航班b，即航班a的起飞序号必须小于航班b的起飞序号。

小X思考的第一个问题是，若给定以上两类限制条件，是否可以计算出一个可行的起飞序列。

第二个问题则是，在考虑两类限制条件的情况下，如何求出每个航班在所有可行的起飞序列中的最小起飞序号。

【输入格式】输入文件plane.in第一行包含两个正整数n和m，n表示航班数目，m表示第二类限制条件（相对起飞顺序限制）的数目。

第二行包含n个正整数k1, k2, …, kn。

接下来m行，每行两个正整数a和b，表示一对相对起飞顺序限制(a, b)，其中1≤a,b≤n, 表示航班a必须先于航班b起飞。

【输出格式】输出文件plane.out由两行组成。

第一行包含n个整数，表示一个可行的起飞序列，相邻两个整数用空格分隔。

输入数据保证至少存在一个可行的起飞序列。

如果存在多个可行的方案，输出任意一个即可。

第二行包含n个整数t1, t2, …, tn，其中ti表示航班i可能的最小起飞序号，相邻两个整数用空格分隔。

【如何评分】如果你的输出文件格式与题目要求不符，则得0分。

即你的输出文件必须满足：第一行恰好包含n个整数，且第二行也恰好包含n个整数。

第一轮试题第一轮组队选拔赛共有四道题，分值依次为90、90、100、120分，共400分每题有十组测试数据，各组分值相同。

3 小时完成======================================================================公交运输系统【问题描述 】某城市的公交运输系统包括公交车与轻轨。

各线路间，无论是公交车或轻轨，彼此之间都可能有交会点，乘客可以藉此转乘公交车或轻轨。

各线路所经过的车站及车站间所需的行车时间为已知，假设转乘公交车的等待时间为5分钟，转乘轻轨的等待时间为10分钟（例如：公交车转乘轻轨需等待10分钟，轻轨转乘轻轨也需等待10分钟），试求从起站1号站到其它各站的最少费时(分钟)。

【输 入 】公交车代号以大写英文字母代表，轻轨代号以小写英文字母代表。

车站代号以数字代表(<=100)。

各线路分别有两行资料。

第一行：线路代号;第二行：有M 笔资料( M 代表经过的车站数目)，每笔资料包括车站代号与到下一站所需时间，中间以一个空隔隔开。

其中每笔资料所代表的均为单向行驶，而非双向行驶。

当到达下一站的时间为0时，表示当前车站已是终点站（一条线路中不会出现重复的车站）。

例如： X1 5 3 6 8 0表示：X 号公交车的行车路线，起站是1号站，经过5分钟到达3号站，再经过6分钟到8号站，也就是终点站。

【输 出 】起点站1号站分别达到其他各站的最少行车时间（车站号按由小到大顺序输出，如果不能到达某一个站点，则输出 -1），仅一行，数与数之间有一个空格，最后无空格。

【样 例 】 输入：a1 523 3 0 b4 85 0 c2 3 3 6 5 0 AB2 10 5 0输出：5 8 18 20货柜配置问题【问题描述】ABC 公司是一家计算机厂商，其贩卖的商品是整套系统，每一套系统包括一台主机和两台显示器，主机每台重 7 公斤，显示器每台重 10 公斤，并且不能分开贩售。

全国信息学奥林匹克联赛（NOIP2010）复赛普及组（请选手务必仔细阅读本页内容）一.题目概览中文题目名称数字统计接水问题导弹拦截三国游戏英文题目名称two water missile sanguo可执行文件名two water missile sanguo 输入文件名two.in water.in missile.in sanguo.in 输出文件名two.out water.out missile.out sanguo.out每个测试点时限1秒1秒1秒1秒测试点数目10 10 10 10每个测试点分值10 10 10 10 比较方式全文比较（过滤行末空格及文末回车）题目类型传统传统传统传统二.提交源程序文件名对于pascal语言two.pas water.pas missile.pas sanguo.pas 对于C语言two.c water.c missilel.c sanguo.c 对于C++语言two.cpp water.cpp missile.cpp sanguo.cpp 三.编译命令（不包含任何优化开关）对于pascal语言fpc two.pas fpc water.pas fpc missile.pas fpc sanguo.pas对于C语言gcc –o twoTwo.c -lm gcc –o waterwater.c -lmgcc –o missileball.c -lmgcc –o sanguosanguo.c -lm对于C++语言g++ –o twotwo.cpp -lmg++ –o seatwater.cpp -lmg++ –o missilemissile.cpp -lmg++ –o sanguosanguo.cpp -lm四.运行内存限制运行内存上限128M 128M 128M 128M注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。

2、C/C++中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。

NOIP2010（Pascal提高组）一、单项选择题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成立，那么在该进制下等式的工作速度慢的多，从而使得后者的效率受到影响。

而根据局部性原理，CPU所访问的存储单元通常都趋于一个较小的连续区域中。

于完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。

假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当存放在数组中的（）号位置。

A. 2k B. 2k+1 C. k/2下取整 D. (k+1)/2 10.以下竞赛活动中历史最悠久的是（）。

A. NOIPB.NOIC. IOID. APIO 二、不定项选择题1.元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。

如果第1个出栈的是R3，那么第5个出栈的可能是( )。

A.R1 B.R2 C.R4 D.R5 2. Pascal语言，C语言和C++语言都属于( )。

A.高级语言 B.自然语言 C.解释性语言 D.编译性语言 3. 原地排序是指在排序过程中(除了存储待排序元素以外的)辅助空间的大小与数据规模无关的排序算有负整数的编码最高位为1 B．在编码的位数确定后，所能表示的最小整数和最大整数的绝对值相同C．整数0只有一个唯一的编码D．两CBFEGDA，则根结点的左子树的结点个数可能是（）。

2010-7-3第1 页共4 页NOI2010湖南省组队选拔赛第一试试题第一题：合唱队（程序文件名：chorus.exe）100 分，运行时限：1s为了在即将到来的晚会上有更好的演出效果，作为AAA 合唱队负责人的小A 需要将合唱队的人根据他们的身高排出一个队形。

假定合唱队一共有 N 个人，第 i 个人的身高为 Hi 毫米(1000≤Hi≤2000)，并且已知任何两个人的身高都不同。

假定最终排出的队形是N 个人站成一排，为了简化问题，小A 想出了如下排队的方式：他让所有的人先按任意顺序站成一个初始队形，然后从左到右按以下原则依次将每个人插入最终排出的队形中：- 第一个人直接插入空的当前队形中。

- 对从第二个人开始的每个人，〒如果他比前面那个人高(H 较大)，那么将他插入当前队形的最右边。

〒如果他比前面那个人矮(H 较小)，那么将他插入当前队形的最左边。

当N 个人全部插入当前队形后便获得最终排出的队形。

例如，有6 个人站成一个初始队形，身高依次为1850、1900、1700、1650、1800 和1750，那么小A 会按以下步骤获得最终排出的队形：- 1850- 1850, 1900 因为 1900 > 1850- 1700, 1850, 1900 因为 1700 < 1900- 1650, 1700, 1850, 1900 因为 1650 < 1700- 1650, 1700, 1850, 1900, 1800 因为 1800 > 1650- 1750, 1650, 1700, 1850, 1900, 1800 因为 1750 < 1800因此，最终排出的队形是1750, 1650, 1700, 1850, 1900, 1800。

小A 心中有一个理想队形，他想知道从多少种初始队形出发能通过上述排队的方式获得他心中的理想队形作为最终排出的队形？【输入格式】（input.txt）从文件input.txt中读入数据，输入文件第一行是一个正整数N，表示总人数。

题目描述小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。

这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。

对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。

假设内存中有M 个单元，每单元能存放一个单词和译义。

每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过M−；；1，软件会将新单词存入一个未使用的内存单元；若内存中已存入M 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。

假设一篇英语文章的长度为N 个单词。

给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。

【数据范围】对于10%的数据有M=1，N≤ 5。

对于100%的数据有0<M≤ 100，0<N ≤ 1000。

输入格式in，输入文件共2 行。

每行中两个数之间用一个空格隔开。

第一行为两个正整数M 和N，代表内存容量和文章的长度。

第二行为N 个非负整数，按照文章的顺序，每个数（大小不超过1000）代表一个英文单词。

文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。

输出格式共1 行，包含一个整数，为软件需要查词典的次数。

【输入输出样例1】3 71 2 1 5 4 4 1【输入输出样例2】2 108 824 11 78 11 78 11 78 8 264【输入输出样例1】5【输入输出样例2】6题目:[NOIP2010]乌龟棋问题编号:599题目描述小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。

乌龟棋的棋盘是一行N 个格子，每个格子上一个分数（非负整数）。

棋盘第1 格是唯一的起点，第N 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

江苏省金湖中学08、09、10级信息学奥赛组NOIP2010初赛模拟练习(三)1、下面一段程序是用（）语言书写的。

int func1(int n){int i,sum=0;for(i=1;i<=n;i++)sum+=i*i;return sum;}A)FORTRAN B)PASCAL C)C D) PROLOG E)BASIC2、多媒体计算机是指()计算机。

A)专供家庭使用的B)装有CD-ROM的B)连接在网络上的高级D)具有处理文字、图形、声音、影像等信息的3、在WORD文档编辑中实现图文混合排版时,关于文本框的下列叙述正确的是()。

A)文本框中的图形没有办法和文档中输入文字叠加在一起,只能在文档的不同位置B)文本框中的图形不可以衬于文档中输入的文字的下方。

C)通过文本框,可以实现图形和文档中输入的文字的叠加,也可实现文字环绕。

D)将图形放入文本框后,文档中输入的文字不能环绕图形。

4、计算机软件保护法是用来保护软件()的。

A)编写权B)复制权C)使用权D)著作权5、64KB的存储器用十六进制表示，它的最大的地址码是()A)10000B)FFFF C)1FFFF D)EFFFF6、在外部设备中，绘图仪属于（）A.输入设备B.输出设备C.辅（外）存储器D.主（内）存储器7、某种计算机的内存容量是640K，这里的640K容量是指（）个字节A.640B.640*1000C.640*1024D.640*1024*10248、已知数组中A中，每个元素A（I，J）在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存贮分配的。

试问：A（5，8）的起始地址为（）A.SA+141B.SA+180C.SA+222D.SA+2259、电线上停着两种鸟（A，B），可以看出两只相邻的鸟就将电线分为了一个线段。

这些线段可分为两类；一类是两端的小鸟相同；另一类则是两端的小鸟不相同。