【C++题解/洛谷】P1540 [NOIP2010 提高组] 机器翻译 |
您所在的位置:网站首页 › 在字典里查找的英文翻译 › 【C++题解/洛谷】P1540 [NOIP2010 提高组] 机器翻译 |
本题目来自
洛谷P11540 [NOIP2010 提高组] 机器翻译
题目背景
小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。 题目描述这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替换。对于每个英文单词,软件会先在内存中查找这个单词的中文含义,如果内存中有,软件就会用它进行翻译;如果内存中没有,软件就会在外存中的词典内查找,查出单词的中文含义然后翻译,并将这个单词和译义放入内存,以备后续的查找和翻译。 假设内存中有 假设一篇英语文章的长度为 共 第一行为两个正整数 第二行为 一个整数,为软件需要查词典的次数。 输入输出样例 样例输入 #1 3 7 1 2 1 5 4 4 1 样例输出 #1 5 提示 样例解释整个查字典过程如下:每行表示一个单词的翻译,冒号前为本次翻译后的内存状况: 1. 1:查找单词 1 并调入内存。 2. 1 2:查找单词 2 并调入内存。 3. 1 2:在内存中找到单词 1。 4. 1 2 5:查找单词 5 并调入内存。 5. 2 5 4:查找单词 4 并调入内存替代单词 1。 6. 2 5 4:在内存中找到单词 4。 7. 5 4 1:查找单词 1 并调入内存替代单词 2。 共计查了 • 对于 • 对于 题目描述中,“每当软件将一个新单词存入内存前,如果当前内存中已存入的单词数不超过 ,软件会将新单词存入一个未使用的内存单元;若内存中已存入 个单词,软件会清空最早进入内存的那个单词,腾出单元来,存放新单词。”由题意可知,我们需要一个可前后实现插入删除元素的数据结构。我们能够很容易地联想到C++STL标准模板库中的deque双向队列容器。 deque双向队列是queue队列的衍生数据结构。它弥补了队列仅能够实现FIFO(First In First Out,即先进先出)的缺陷,从队首和队尾都可以进行入队和出队(插入和删除)操作。 使用deque数据结构需要添加其相应头文件(该头文件已包含在万能头文件中,使用万能头文件则无需添加): #include本题中,我们使用以下有关deque的函数: deque dq; //定义deque数据结构,中数据类型为int类型,命名为dq dq.push_back(i); //在dq的队尾插入元素i(与类型对应,i为int类型) dq.pop_front(); //将dq的队首第一个元素删除另外,我们也可以使用下标法直接提取单个元素,如: int num = dq[i]; //将dq的第i个元素保存到num中回到题目中,我们可以模拟题目所述的过程:dep变量记录dq元素个数。当检查到新单词时,若deque中单词(队列元素)数量dep不超过 定义bool函数vis,初始化为false,新单词标记为false,已存单词标记为true。 bool vis[1010] = {false}; //定义bool函数vis,初始化为false这一部分非本题核心,故在此不做赘述。 代码实现(C++) #include using namespace std; deque dq; //定义deque数据结构,中数据类型为int类型,命名为dq bool vis[1010] = {false}; //定义bool数组vis,初始化为false int m, n, a, dep = 0, cnt = 0; //dep变量记录dq元素个数,cnt记录查找次数 int main() { cin >> m >> n; for (int i = 1; i > a; if (!vis[a]) { //判断是否为新单词 vis[a] = true; //是,标记为已存单词 cnt++; //查找次数增加1 if (dep == m) { //判断dep是否达到M vis[dq[0]] = false; //达到,标记队首单词为新单词 dq.pop_front(); //删除队首单词 dq.push_back(a); //在队尾插入新单词 } else { dep++; //未达到,dep增加1 dq.push_back(a); //队尾插入新单词 } } } cout |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |