机器翻译P1540：用队列与标记数组模拟FIFO缓存淘汰

2010年的NOIP提高组考场上出现过一道非常朴素的题目名叫《机器翻译》现在洛谷编号P1540。我第一次见它的时候以为要处理什么分词、词库之类的东西读完题才发现它模拟的不过是一台内置了有限内存的翻译软件每个英文单词一旦不在内存中就必须查一次词典然后把它塞进内存要是内存满了就按进入顺序把最早的那一个挤出去。如今十几年过去这道题仍然是训练模拟题基本功的首选——算法不高级难的全在“把过程想清楚、把边界写对”。这篇文章就按我平时带新人的思路把题目拆开讲清楚队列为什么是题眼、数组模拟时那个经典的越界坑、以及怎么自己构造反例验证代码。1. 先把题面拆开翻译软件里的那台“内存”到底怎么工作1.1 真正的输入输出英文单词在内存里走了一圈题面给了一个很生活化的场景有一台机器翻译软件它的“内存”最多只能存M个单词。现在有一篇英文文章共N个单词软件从左到右逐个翻译。如果当前这个单词已经在内存里说明之前查过词典直接命中不产生新的查询如果不在就得去查一次词典查完之后把这个单词存入内存。关键约束在最后一句如果存入内存时发现内存已经装满了M个单词就要把“最早进入内存的那个单词”从内存中删掉腾出位置给新单词。注意这里的“最早进入”指的是进入内存的时间先后而不是最后一次被用到的时间。整个输出也只有一个数字翻译完整篇文章一共查了多少次词典。换句话说统计的是“不在内存中”的次数。搞明白这一点题目就从“翻译”变成了一个纯粹的缓存淘汰模拟。1.2 手推一遍样例把“查词典”变成三个动作我以洛谷样例为例M3N7文章单词序列是1 2 3 4 2 1 5手推一遍读入1内存空未命中。查词一次加入内存内存状态[1]读入2不在内存未命中。查词一次加入内存内存状态[1, 2]读入3不在内存未命中。查词一次加入内存内存状态[1, 2, 3]读入4不在内存未命中。此时内存已满淘汰最早进入的1加入4内存状态[2, 3, 4]读入2在内存中命中什么都不做读入1不在内存未命中。此时内存满淘汰最早进入的2加入1内存状态[3, 4, 1]读入5不在内存未命中。此时内存满淘汰最早进入的3加入5内存状态[4, 1, 5]查词典次数加起来正好是5和样例输出一致。推完这个流程你应该能感觉到在这道题里每个单词的处理过程中本质上只有三种动作查内存判断单词在不在如果不在查词典次数加一并把单词加入内存加入前检查内存是否满满了就把队头那个淘汰掉。这三个动作翻译成代码就是读入一个数、查标记、操作队列。这也是整个题目的全部骨架。2. 为什么选队列而不选别的FIFO规则才是题眼2.1 淘汰最早进入内存的不是最近最少使用的很多初学者看到“内存满了就把最老的挤出去”第一反应想到LRULeast Recently Used最近最少使用。这是被操作系统教材和缓存概念带偏了。LRU淘汰的是“最久没被访问”的页面而题目要淘汰的是“最早进入内存”的单词。两者的区别非常明显按LRU如果一个单词最开始进入内存但中间多次被命中它的“最近使用时间”会不断刷新哪怕它是最早进来的也不是优先淘汰对象按本题规则只要它是最早进入内存的单词不管中间被命中多少次只要新词需要空间先走的永远是它。举个例子M2序列是1 2 1 3。用LRU策略推导的话读入1和2后内存已满再读入1时1被命中此时1的“使用时间”刷新3到来时淘汰的反而是2。但按题目的FIFO规则1是最早进入内存的所以3到来时淘汰1内存变为[2, 3]。这两种结果在后面的命中情况上完全不一样答案也会差出一个数。所以读题时遇到“最早进入”这四个字就该立刻锁定数据结构先进先出也就是队列FIFO。2.2 为什么需要一个队列再加一个标记数组只用队列能不能做理论上可以但效率很差。每次判断当前单词是否在内存中都需要从头到尾扫描一遍队列复杂度是O(NM)。本题M≤100、N≤1000其实暴力扫描也能过但这道题放到更通用的场景里扫描法就太慢。只用标记数组能不能做也不行。标记数组能回答“某个单词在不在内存里”但它回答不了“如果满了谁是最该被淘汰的”。要维持“最早进入”这个顺序关系就必须有一个数据结构按时间顺序记住每个单词的入场顺序这是队列的核心职责。所以这个题最自然的结构是“队列 标记数组”的组合队列存单词编号按进入顺序排列队头就是要淘汰的那个标记数组记录某个编号当前是否在内存中用来O(1)判断命中。这两者缺一不可队列负责顺序标记数组负责查询。理解了这个分工代码思路就非常清晰不会写出又臭又长的扫描代码。3. 两种实现对比数组模拟队列时最容易翻的车3.1 写法A数组模拟队列容量到底开M还是开N先上我推荐的标准写法用数组模拟一个简单的队列#include bits/stdc.h using namespace std; const int MAXN 1005; int q[MAXN]; // 队列空间 bool inMem[MAXN]; // 标记单词是否在内存中 int head 0, tail 0; int main() { int m, n; cin m n; int ans 0; for (int i 0; i n; i) { int x; cin x; if (inMem[x]) continue; // 命中什么都不做 ans; // 未命中查词典 if (tail - head m) { // 内存已满 inMem[q[head]] false; head; // 队头出队 } q[tail] x; // 新单词入队 inMem[x] true; } cout ans endl; return 0; }注意我这里的队列数组开的是MAXN 1005也就是按N的最大值开的而不是M。这是数组模拟队列实现方式里最经典的一个坑。有些初学选手想当然地认为“内存最多存M个单词队列长度最多也就M个”于是把数组开成q[M 1]结果一旦数据范围超过容量就出问题。原因在于这里的数组模拟并不是循环队列head和tail是两个只增不减的指针每次入队tail每次淘汰head。当内存满后每处理一个新单词head和tail都会同时往后挪一位。所以tail的最终值取决于“总共入队了多少次”这个次数最坏情况下就是N而不是M。如果你只开M的空间tail很快就越界了。举个极端例子M3N10。前3个单词入队后tail3此时数组刚好用完。第4个单词到来时淘汰队头后head1再入队tail4已经越界。继续处理下去越界会越来越严重轻则读到未初始化的内存重则直接RE。所以数组模拟队列时安全做法是直接开到N5甚至更大不要省这一点空间。这道题的N上限是1000开1005完全足够。3.2 写法BSTL版本与暴力版本的取舍如果你不想管head和tail的细节直接用STL的queue会更省心#include bits/stdc.h using namespace std; bool inMem[1005]; int main() { int m, n; cin m n; queueint q; int ans 0; for (int i 0; i n; i) { int x; cin x; if (inMem[x]) continue; ans; if ((int)q.size() m) { inMem[q.front()] false; q.pop(); } q.push(x); inMem[x] true; } cout ans endl; return 0; }STL版本直接利用q.size()判断内存是否已满利用q.front()拿到最早进入的单词。逻辑上比数组模拟清晰很多也不存在越界问题。还有一种“纯暴力”写法也很常见用vectorint当内存每次用find在内存里查找当前单词找不到就push_back满了就erase(begin())。这种写法代码最短但每次查找是O(M)而且erase头部元素需要把后面元素全部前移复杂度略高。本题数据范围小也能AC但我不建议作为主学写法——因为它没有体现出“队列维护顺序”的核心思想写多了容易养成“什么都上vector扫一遍”的习惯。数组模拟和STL二选一的话我更推荐新手先写数组模拟。原因很简单你能看见head和tail怎么移动就真正理解了队列。等理解了再换STL就会觉得它是顺理成章的事。4. 边界条件与反例验证从样例到AC之间还隔着这些坑4.1 命中时也入队那个让我多花半小时的隐藏bug第一次独立写这题时模块搭好以后我样例过了但交上去就是WA。后来手工构造反例才定位到问题我在“命中”的时候也就是if (inMem[x])分支里错误地执行了入队操作。你可能会想命中时把单词再塞回队列里看起来“刷新”了它的位置好像没什么问题。但队列的语义是“按进入顺序淘汰”如果命中时也入队同一个单词会在队列里出现多份副本。而inMem只是一个布尔值它无法区分“队列里第一份1”和“队列里第二份1”。淘汰时一旦把inMem[1]置为false此时队列里可能还有另一份1后续再遇到单词1时会被误判为“不在内存”导致重复查词。我用这个反例验证M2序列1 2 1 3 2正确做法是1未命中内存[1]2未命中内存[1,2]1命中不操作3未命中淘汰1内存[2,3]2命中总查询次数3如果命中时也入队按“满就淘汰队头”的规则推一遍得到的结果会多出查询次数答案错误。这个bug的教训是在处理“命中”事件时什么操作都不做才是对的。如果题目真要求“命中后刷新顺序”那就得用LRU那种结构会复杂得多——但本题不是。4.2 容量为0、单词重复、编号上限越界的三种姿势样例过了之后强烈建议自己补几个边界测试记忆比看题解深刻得多。第一内存容量M和文章长度N可能出现极限值。如果某天出一个变种数据让M0按STL写法直接q.size()0成立然后q.front()就是未定义行为程序可能崩溃。这时候最好的做法是特判M为0时内存永远为空所有单词都未命中答案直接输出N。第二单词重复出现的模式要专门测。比如M1序列1 1 1 1输出应该是1因为第一次查词后单词1一直在内存里。如果代码在命中时做了多余操作这个极其简单的数据也能暴露问题。第三单词编号的上限。原题里单词编号不超过某个值但如果你用数组做标记一定要把数组开到编号可能的最大值以上而不是M以上。开小了会数组越界这种错误在NOIP风格的评测环境下通常会得到RE而不是WA很容易排查但怎么说都是白费一场惩罚性罚时。我的建议是每写完一道模拟题都要主动构造不少于3组手造数据分别覆盖“完全命中型”、“反复淘汰型”、“容量极小或极大”这三类场景。用不了两分钟但能把大多数隐藏bug提前炸出来。5. 从NOIP 2010的队列到NOIP 2016的状压模拟题的进阶路5.1 2010年的第一题和2016年的第二十题差了些什么有些人觉得P1540太简单AC之后就不再看第二眼。但如果你把这题放在整个NOIP提高组的脉络里就会发现它其实是“模拟题方法论”的绝佳样本。同样是提高组2016年有一道著名的P2831《愤怒的小鸟》难度高出一大截给定若干小猪坐标从原点发射飞鸟求覆盖所有小猪的最少飞鸟数量。它需要用状态压缩DP去枚举抛物线的覆盖集合。两道题看上去天差地别但解题起点是一样的先弄清楚系统里有哪些状态。机器翻译的状态是“当前内存里的单词集合 进入顺序”愤怒的小鸟的状态是“哪些小猪已经被打死”。状态定义清楚之后再谈用队列还是用状压DP。很多人面对P2831觉得无从下手恰恰是因为跳过了“状态设计”这一步总想直接套一个算法模板。所以我的建议永远是模拟题不要只求AC要在写代码之前逼自己回答三个问题——系统里有什么状态每个事件到达时做什么动作状态怎么迁移。这三个问题回答得越清晰代码越不容易写歪。P1540是练这个流程的最小规模题目练透了再上难度级别的状态压缩路会顺很多。5.2 把机器翻译的队列改成哈希链表就是LRU的雏形最后说一个我每次带新人都会提的延伸点P1540里的“队列 标记数组”在真实系统里并不只是一个竞赛梗。它本质上就是一个FIFO缓存淘汰器和CPU Cache、Redis内存淘汰、数据库缓冲池设计的底层逻辑一脉相承。FIFO是缓存策略里最简单的一种实现成本低但命中率一般。如果你把“队列”换成双向链表“标记数组”换成哈希表并且每次命中时把节点移到链表尾部就得到了经典的LRU缓存。LeetCode上那道146 LRU Cache核心结构就是这张图翻版。站在这个角度看P1540等于用最通俗的方式把一个缓存系统的骨架完完整整塞给了你——先记住队列版本再去看LRU版本会突然明白很多系统设计的套路。我现在带新生训练的时候还是会把P1540放在模拟专题的第一道题。它看着简单但能把“先设计状态再动手写代码”这件事讲得明明白白——写之前先想清楚队列里存什么、标记数组管什么、什么时候动它们这三句话想明白了比背十道模板题都值。如果你刚接触这类题目不妨按这个顺序走一遍先手推样例再用数组模拟实现接着自己构造几组反例验证最后想想如果M和N都放大到十万级别代码该怎么改。走完这一步你收获的就不仅是一道AC题而是一整套处理模拟问题的底子。