企业官网建设流程全解析

2010年的NOIP提高组考场上出现过一道非常朴素的题目，名叫《机器翻译》，现在洛谷编号P1540。我第一次见它的时候以为要处理什么分词、词库之类的东西，读完题才发现，它模拟的不过是一台内置了有限内存的翻译软件：每个英文单词一旦不在内存中，就必须查一次词典，然后把它塞进内存；要是内存满了，就按进入顺序把最早的那一个挤出去。如今十几年过去，这道题仍然是训练模拟题基本功的首选——算法不高级，难的全在“把过程想清楚、把边界写对”。这篇文章就按我平时带新人的思路，把题目拆开，讲清楚队列为什么是题眼、数组模拟时那个经典的越界坑、以及怎么自己构造反例验证代码。

1. 先把题面拆开：翻译软件里的那台“内存”到底怎么工作

1.1 真正的输入输出：英文单词在内存里走了一圈

题面给了一个很生活化的场景：有一台机器翻译软件，它的“内存”最多只能存M个单词。现在有一篇英文文章，共N个单词，软件从左到右逐个翻译。如果当前这个单词已经在内存里，说明之前查过词典，直接命中，不产生新的查询；如果不在，就得去查一次词典，查完之后把这个单词存入内存。

关键约束在最后一句：如果存入内存时发现内存已经装满了M个单词，就要把“最早进入内存的那个单词”从内存中删掉，腾出位置给新单词。注意这里的“最早进入”指的是进入内存的时间先后，而不是最后一次被用到的时间。

整个输出也只有一个数字：翻译完整篇文章一共查了多少次词典。换句话说，统计的是“不在内存中”的次数。搞明白这一点，题目就从“翻译”变成了一个纯粹的缓存淘汰模拟。

1.2 手推一遍样例，把“查词典”变成三个动作

我以洛谷样例为例，M=3，N=7，文章单词序列是：

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，和样例输出一致。

推完这个流程你应该能感觉到，在这道题里每个单词的处理过程中，本质上只有三种动作：

1. 查内存，判断单词在不在；
2. 如果不在，查词典次数加一，并把单词加入内存；
3. 加入前检查内存是否满，满了就把队头那个淘汰掉。

这三个动作翻译成代码，就是读入一个数、查标记、操作队列。这也是整个题目的全部骨架。

2. 为什么选队列而不选别的：FIFO规则才是题眼

2.1 淘汰最早进入内存的，不是最近最少使用的

很多初学者看到“内存满了就把最老的挤出去”，第一反应想到LRU（Least Recently Used，最近最少使用）。这是被操作系统教材和缓存概念带偏了。LRU淘汰的是“最久没被访问”的页面，而题目要淘汰的是“最早进入内存”的单词。两者的区别非常明显：

• 按LRU，如果一个单词最开始进入内存，但中间多次被命中，它的“最近使用时间”会不断刷新，哪怕它是最早进来的，也不是优先淘汰对象；
• 按本题规则，只要它是最早进入内存的单词，不管中间被命中多少次，只要新词需要空间，先走的永远是它。

举个例子，M=2，序列是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很快就越界了。

举个极端例子：M=3，N=10。前3个单词入队后tail=3，此时数组刚好用完。第4个单词到来时，淘汰队头后head=1，再入队tail=4，已经越界。继续处理下去越界会越来越严重，轻则读到未初始化的内存，重则直接RE。

所以数组模拟队列时，安全做法是直接开到N+5甚至更大，不要省这一点空间。这道题的N上限是1000，开1005完全足够。

3.2 写法B：STL版本与暴力版本的取舍

如果你不想管head和tail的细节，直接用STL的queue会更省心：

#include <bits/stdc++.h> using namespace std; bool inMem[1005]; int main() { int m, n; cin >> m >> n; queue<int> 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()拿到最早进入的单词。逻辑上比数组模拟清晰很多，也不存在越界问题。

还有一种“纯暴力”写法也很常见：用vector<int>当内存，每次用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时会被误判为“不在内存”，导致重复查词。

我用这个反例验证，M=2，序列：

1 2 1 3 2

正确做法是：

• 1未命中，内存[1]
• 2未命中，内存[1,2]
• 1命中，不操作
• 3未命中，淘汰1，内存[2,3]
• 2命中
• 总查询次数3

如果命中时也入队，按“满就淘汰队头”的规则推一遍，得到的结果会多出查询次数，答案错误。

这个bug的教训是：在处理“命中”事件时，什么操作都不做才是对的。如果题目真要求“命中后刷新顺序”，那就得用LRU那种结构，会复杂得多——但本题不是。

4.2 容量为0、单词重复、编号上限：越界的三种姿势

样例过了之后，强烈建议自己补几个边界测试，记忆比看题解深刻得多。

第一，内存容量M和文章长度N可能出现极限值。如果某天出一个变种数据让M=0，按STL写法直接q.size()==0成立，然后q.front()就是未定义行为，程序可能崩溃。这时候最好的做法是特判：M为0时，内存永远为空，所有单词都未命中，答案直接输出N。

第二，单词重复出现的模式要专门测。比如M=1，序列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题，而是一整套处理模拟问题的底子。