NOIP2010复赛提高组题解加程序.docVIP

NOIP2010复赛提高组题解加程序 全国信息学奥林匹克联赛（NOIP2010）复赛 提高组 第 1 页 共 7 页 全国信息学奥林匹克联赛（NOIP2010）复赛 提高组 （请选手务必仔细阅读本页内容） 一．题目概况 中文题目名称 机器翻译 乌龟棋 关押罪犯 引水入城 英文题目与子目录名 translate tortoise prison flow 可执行文件名 translate tortoise prison flow 输入文件名 translate.in tortoise.in prison.in flow.in 输出文件名 translate.out tortoise.out prison.out flow.out 每个测试点时限 1秒 1秒 1秒 1秒 测试点数目 10 10 10 10 每个测试点分值 10 10 10 10 附加样例文件 有 有 有 有 结果比较方式 全文比较（过滤行末空格及文末回车） 题目类型 传统 传统 传统 传统 二．提交源程序文件名 对于pascal语言 translate.pas tortoise.pas prison.pas flow.pas 对于C语言 translate.c tortoise.c prison.c flow.c 对于C++语言 translate.cpp tortoise.cpp prison.cpp flow.cpp 三．编译命令（不包含任何优化开关） 对于pascal语言 fpc translate.pasfpc tortoise.pasfpc prison.pas fpc flow.pas 对于C语言 gcc -o translate translate.c -lm gcc -o tortoise tortoise.c -lm gcc -o prison prison.c -lm gcc -o flow flow.c -lm 对于C++语言 g++ -o translate translate.cpp -lm g++ -o tortoise tortoise.cpp -lm g++ -o prison prison.cpp -lm g++ -o flow flow.cpp -lm 四．运行内存限制 内存上限 128M 128M 128M 128M 注意事项： 1、文件名（程序名和输入输出文件名）必须使用英文小写。 2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为：CPU P4 3.0GHz，内存1G，上述时限以此配置为准。 各省在自测时可根据具体配置调整时限。 换页 全国信息学奥林匹克联赛（NOIP2010）复赛 提高组 第 2 页 共 7 页 1．机器翻译 (translate.pas/c/cpp) 【问题描述】 小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。 这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义 来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有， 软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中 文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。 假设内存中有M个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入 内存前，如果当前内存中已存入的单词数不超过M?1，软件会将新单词存入一个未使用的 内存单元；若内存中已存入M个单词，软件会清空最早进入内存的那个单词，腾出单元来， 存放新单词。 假设一篇英语文章的长度为N个单词。给定这篇待译文章，翻译软件需要去外存查找多 少次词典？假设在翻译开始前，内存中没有任何单词。 【输入】 输入文件名为translate.in，输入文件共2行。每行中两个数之间用一个空格隔开。 第一行为两个正整数M和N，代表内存容量和文章的长度。 第二行为N个非负整数，按照文章的顺序，每个数（大小不超过1000）代表一个英文 单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。 【输出】 输出文件translate.out共1行，包含一个整数，为软件需要查词典的次数。 【输入输出样例1】 translate.in translate.out 3 7 1 2 1 5 4 4 1 5 【输入输出样例1说明】 整个查字典过程如下：每行表示一个单词的翻译，冒号前为本次翻译后的内存状况： 空：内存初始状态为空。 1． 1：查找单词1并调入内存。 2． 1 2：查找单词2并调入内存。 3． 1 2：在内存中找到单词1。 4． 1 2 5：查找单词5并调入内存