CCF CSP门禁系统题解：数组越界与哈希表选型实战

我参加CCF CSP认证的次数不算少，每次考完都有个感觉：第一题就是专门用来筛粗心人的。201412-1门禁系统，题目描述看着像某单位访客登记，实际上是一个典型的序列处理问题——按顺序统计每个编号已经出现过几次。这道题拿到满分很容易，但每年都有人因为各种细节在它上面翻车。这篇就把题意拆解、代码实现、常见坑和延伸思路都串起来讲一遍，准备认证的同学可以直接拿去当模板。

1. 先读题：门禁系统到底要我们算什么

1.1 把场景翻译成算法语言

门禁系统的故事是这样的：每次有人进出，系统会记录一个访客编号。现在给出一串编号，要求逐个输出每个编号在当前位置已经出现的次数，包括当前这一次。

举个简单的例子，输入是：

5 1 2 1 1 3

输出是：

1 1 2 3 1

我把过程展开写一下。读到第1个编号1，它是1号第一次出现，输出1。读到第2个编号2，2号第一次出现，输出1。读到第3个编号1，1号已经出现过一次，这次是第二次，输出2。读到第4个编号1，1号第三次出现，输出3。读到第5个编号3，3号第一次出现，输出1。

所以算法本质是：维护一个"计数器集合"，每次拿到一个编号x，先给x的计数加1，再把加完的值输出。

1.2 这个"序列处理"到底在处理什么

很多初学者第一次看到"序列处理"这四个字会懵，其实它强调的是：输出结果依赖数据的原始顺序，你不能排序、不能重排，只能按输入的顺序逐个处理。

这一点很关键。我见过有人看到题目里有统计次数，上来就把序列排序了，然后用某种方式去重输出，结果顺序全乱了。这种思路是把简单问题做复杂。门禁系统是一个在线过程，每读入一个编号，马上要给出针对它的答案，不允许你等全部读完之后再统一整理——虽然全部读完之后也能模拟出来，但为什么要绕远路呢？

1.3 数据范围是选解法的第一依据

做题第一步永远是盯数据范围。

这道题的n指记录条数，总数不大，属于典型的入门规模。编号的范围我记得题目里给得比较温和，直接用定长数组也能过。但问题是，考场上你可能记不住这个范围，或者说题目在某些改编版里放大了编号上限。这时候如果你写死int cnt[1005]，一旦编号超过1005就会数组越界，轻则答案错乱，重则运行时崩溃。

我的建议是：除非你对数据范围极其确定，否则这种统计题直接用map或者字典，别赌数组范围。后面第三节会给具体的满分代码，两种做法都贴出来，你可以对比一下。

2. 三种常用实现：数组、map和哈希表到底怎么选

2.1 定长数组：最快但它有使用前提

用定长数组实现的门禁系统代码非常短：

#include <iostream> using namespace std; const int MAX_ID = 100000; // 根据题目编号上限调整 int cnt[MAX_ID + 1]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 0; i < n; ++i) { int x; cin >> x; ++cnt[x]; cout << cnt[x]; if (i != n - 1) { cout << ' '; } } cout << '\n'; return 0; }

这段代码的核心逻辑只有一句话：++cnt[x]，先自增再输出。数组是定长的，访问时间复杂度是O(1)，常数极小，在整个CSP认证的题目里都属于性能最好的那一档。

使用前提是：你必须确认所有编号都在[0, MAX_ID]范围内，而且内存够用。万一编号是1000000007这种大数，你总不能开一个十亿级的数组吧？所以这个方案适合"范围已知且可控"的场景。

2.2 map容器：不会越界的保底方案

如果你不想纠结编号上限，直接用map<int, int>：

#include <iostream> #include <map> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; map<int, int> cnt; for (int i = 0; i < n; ++i) { int x; cin >> x; ++cnt[x]; cout << cnt[x]; if (i != n - 1) { cout << ' '; } } cout << '\n'; return 0; }

map在C++里是红黑树实现的关联容器，每个操作的时间复杂度是O(logn)。这道题的n不算大，用它完全没问题，而且有两大好处：第一，编号无论多大都能存，因为键的类型是int，值由树结构动态分配；第二，cnt[x]在键不存在时会自动插入并把值初始化为0，所以++cnt[x]直接就能得到正确答案。

这里我解释一下cnt[x]自动初始化的机制。在C++里，map用下标运算符访问一个不存在的键时，会执行插入动作，调用int的默认构造函数，也就是把值置为0。所以第一次遇到编号x时，++cnt[x]等价于把0变成1。这个特性让代码变得非常简洁。

2.3 unordered_map和Python字典的均摊O(1)

在C++里如果进一步追求性能，可以用unordered_map替换map，它是哈希表实现，均摊访问时间O(1)。

#include <iostream> #include <unordered_map> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; unordered_map<int, int> cnt; for (int i = 0; i < n; ++i) { int x; cin >> x; ++cnt[x]; cout << cnt[x]; if (i != n - 1) cout << ' '; } cout << '\n'; return 0; }

Python选手更简单，字典天然就是哈希表：

import sys def main(): data = list(map(int, sys.stdin.read().split())) if not data: return n = data[0] lst = data[1:1 + n] cnt = {} res = [] for x in lst: cnt[x] = cnt.get(x, 0) + 1 res.append(str(cnt[x])) print(' '.join(res)) if __name__ == '__main__': main()

cnt.get(x, 0)的意思是：如果x在字典里，取它的当前值；如果不在，取0。拿到之后加1再写回字典，和C++里++cnt[x]的效果一模一样。

2.4 选型口诀

我个人总结了这样一个选择顺序：

• 明确知道编号上限且内存允许，优先定长数组，代码最直观。
• 任何情况下不想冒险，选map。
• n的规模较大、或频繁查找，选unordered_map。
• 写Python，直接用字典。

如果你在考场上看到一个题目里面是"统计每个元素出现次数"这类字眼，条件反射应该就是哈希表/字典。这一个反应练熟了，后面遇到更复杂的序列处理题也能很快上手。

3. 满分代码实战：从提交到AC的完整细节链

3.1 C++满分代码的逐行说明

用map实现那一版，每一行都有它的意义。ios::sync_with_stdio(false)和cin.tie(nullptr)这两行是解除C++标准输入输出与C标准库的同步，让cin变快。很多初学的人会忽略，但这是C++做题的标配操作。输入量不大的时候不写也能过，可养成习惯之后，遇到大数据集就不会因为IO拖后腿。

输出部分我单独说明一下。题目要求的输出是"一行内输出n个数，之间用空格分隔"。有些OJ不检查行末空格，但严格模式会判格式错误（Presentation Error）。所以我写了个条件判断：当不是最后一个元素时输出空格，最后一个元素后输出换行。这样百分百符合规范。

if (i != n - 1) { cout << ' '; }

这段逻辑虽然只有三行，但它代表了一个细节意识：不能只在本地自测通过就提交，要主动把输出格式做到最严格。

3.2 Python版本要注意的读取方式

Python版里我用了sys.stdin.read().split()一次性读取全部数据，而不是用input()逐行读。原因有两个：第一，一次读取快；第二，避免行尾有额外空行或行内有多个空格导致解析出错。

data = list(map(int, sys.stdin.read().split()))会把整块输入切分成字符串列表，然后逐个转成int。第一项是n，后面的项就是编号序列。注意我写了if not data: return，这是为了处理极端空输入，防止程序直接报错。这类防御性代码在正式比赛里不一定需要，但写上是好习惯。

3.3 容易被忽略的边界测试

一个简单题能不能拿满分，往往取决于你想没想到边界情况。我给这套逻辑准备了三组测试：

• n=1，只有一个数，比如输入1 7，输出1。这验证了输出末尾没有多余空格。
• 所有编号都相同，比如5 2 2 2 2 2，输出1 2 3 4 5。这验证了连续自增逻辑。
• 所有编号都不同，比如4 9 8 7 6，输出1 1 1 1 1。这验证了新键插入逻辑。

这三组数据跑完，基本能把代码里最常见的错误都暴露出来。考试时间再紧，这三组测试也值得花三十秒手动过一遍。

4. 踩坑实录：从本地正确到提交出错的全排查过程

4.1 数组越界是怎么发生的

我帮某位同学看过一次提交记录，思路完全正确，但一直报Runtime Error。他的代码是开了一个int cnt[1005]，然后直接用编号做下标。问题来了：他找的题目范围写的是编号不超过1000，而实际测试数据里混进了一个1005，数组越界了。

越界不一定会立刻崩溃，它会覆盖内存中相邻变量，导致计数结果神秘错乱。这种Bug最讨厌的地方在于：本地跑小数据一切正常，一提交就挂。解决办法就是把数组开大一个量级，或者干脆换map。从那以后我自己做这类题，只要数据范围不是死死写在眼前，一律用map。

4.2 全局数组与局部数组的初始化差异

C++里定义一个局部数组int cnt[1005];写在main函数里，它的初值是不确定的。也就是说，如果忘给数组清零，计数一开始就可能是个随机大数，加1之后输出的结果完全离谱。

而如果把数组声明在main外面成为全局变量，C++会默认把它初始化为0。很多老手写这种题喜欢把计数数组放全局，就是为了省掉手动初始化的麻烦。但这里有个需要注意的地方：全局数组的大小要在编译期确定，所以不能写int cnt[n + 1]这种动态大小，除非用vector。

如果非要用局部数组，务必写int cnt[1005] = {0};把整个数组清零。这个等号后面的初始化列表，把一个0复制给所有元素，是C++的语法特性，实际效果就是全零初始化。

4.3 样例通过但WA的原因：逻辑顺序错了

还有一个很常见的错误：把输出放在了自增之前。

cout << cnt[x]; ++cnt[x];

这样写，第一个编号会输出0，第二个相同的编号会输出1，整体答案整体左移了一位。样例跑起来，第一次看到的是0 0 1 2 0，跟正确答案全都不一致。但如果测试数据恰好是"每个编号只出现一次"，那输出就全是0，本来就该输出1的程序也能测出0来——你可能会怀疑是全局初始化问题，而不是逻辑顺序问题。

所以检查这种序列统计题，第一优先级就是确认输出值到底是不是"当前计数"，而不是"此前计数"或"下一次计数"。

4.4 排查问题的实操方法

当你改了代码还是WA，别在那里瞪眼干看。把思路换成构造对拍：自己写一个绝对暴力但绝对正确的版本，比如用一个字典记录所有出现次数，然后生成随机小数据，把暴力版结果和优化版结果逐行对比。

对拍工具的流程不复杂：

1. 写一个数据生成器，随机产生n和编号序列。
2. 跑暴力版，得到一个答案文件。
3. 跑你的提交版，得到另一个答案文件。
4. 用diff命令比较两个文件。

如果某组数据对不上，把输入打印出来，人工走一遍就知道问题出在哪了。这个过程对第一题这种规模的问题，最多十分钟就能得出结论。

5. 门禁系统不是终点：序列处理题还能怎么变形

5.1 从统计出现次数到定位第几次

门禁系统本身是"当前是第几次出现"。如果题目改一个问法：求每个编号第k次出现的位置，你该怎么处理？

思路很简单，把计数器map里的值换成vector，遇到一个编号x，就向pos[x]的vector里追加当前下标，之后想查第k次出现的位置，直接访问pos[x][k-1]。这个变形在思路上完全继承了门禁系统的数据结构，只是把int换成vector。

类似地，如果要求"最后一次出现的位置"，那就更简单，每次读到编号x，用last[x] = i覆盖更新，循环结束后所有编号的last值天然就是最后一次出现的位置。

5.2 让"统计频次"具备工程意义

这种计数器思想在真实系统里非常常见。比如某个接口需要统计不同用户的调用次数，某台网关需要统计每个IP的访问频次，本质上都是"来了一个标识，给它计数加1"。门禁系统就是这个模型的简化加在线化版本。

从这题往后延伸，序列处理的方向大概有这么几条：

• 求出现次数最多的元素：计数完再遍历一次找最大值。
• 判断是否存在出现次数超过一半的元素：计数后逐一检查阈值。
• 统计区间内不同数字的个数：这就要上升到离线查询、树状数组或者莫队了。
• 字符串中第一个不重复字符：同样是计数器的变种，先数一遍再扫第二遍。

你会发现，所有这些进阶问题都以"维护频次表"作为地基，而门禁系统把这块地基打得很扎实。

5.3 做CSP第一题的固定节奏

经历过几次认证之后，我养成了一套固定节奏，遇到第一题就这么走：

一、把题目样例在草稿纸上手动跑一遍，确认输出规则，不要急。二、圈出数据范围词，想清楚编号上限是多少，决定用数组还是map。三、动手写最简洁的版本，控制代码行数在30行以内。四、把边界测试数据打一遍：最小n、全相同、全不同、大编号。五、提交前再盯一眼输出格式代码，是不是把换行放在最后了。

这套流程看起来很基础，但正是这些基础动作决定你第一题是10分钟拿100分，还是30分钟反复试错拿不到满分。门禁系统这道题本身很简单，把它当成一个训练"读题-选结构-补边界"的标杆，价值比单纯刷一道题大得多。