C 刷题日记Map 的三种“打开方式”从入门到超时再到 AC 导语在算法竞赛和日常开发中std::map绝对是 C STL 里的“万金油”。它不仅能自动排序还能提供极快的键值对查找能力。最近我刷到了三道关于map的经典题目涵盖了基础增删改查、反向映射优化以及数学逻辑转换。今天就把我的解题思路、踩过的坑以及最终的 AC 代码整理出来分享给大家 第一题P5266【深基17.例6】学籍管理 题目描述您需要设计一个学籍管理系统最开始时数据都是空的。然后该系统能够支持下面的操作不超过10510^5105条输入与修改格式1 NAME SCORE在系统中插入姓名为 NAME(由字母和数字组成不超过 20 个字符的字符串区分大小写)分数为 SCORE (0≤SCORE2310 \le \text{SCORE} 2^{31}0≤SCORE231) 的学生。如果已经有同名的学生则更新该学生的成绩为 SCORE。如果成功插入或者修改则输出OK。查询格式2 NAME在系统中查询姓名为 NAME 的学生成绩。如果没找到这名学生则输出Not found否则输出该生成绩。删除格式3 NAME在系统中删除姓名为 NAME 的学生信息。如果没能找到这名学生则输出Not found否则输出Deleted successfully。汇总格式4输出系统中学生数量。输入格式第一行输入一个正整数 Q (1≤Q≤1051 \le Q \le 10^51≤Q≤105)表示操作数量。接下来 Q 行每行先输入一个正整数 op (op∈[1,4]op \in [1, 4]op∈[1,4])表示操作种类。接着如果 op 1则再输入一个字符串 NAME 以及一个正整数 SCORE含义见题目描述。如果 op 2则再输入一个字符串 NAME含义见题目描述。如果 op 3则再输入一个字符串 NAME含义见题目描述。如果 op 4则无需再输入其他内容。输出格式共输出 Q 行每行输出一个字符串或正整数为对应操作的处理结果具体含义见题目描述。 解题思路这道题是map的教科书级应用。核心数据结构使用mapstring, long long其中string存姓名Keylong long存分数Value。插入与更新map的下标操作符[]非常强大。mp[name] score;这行代码会自动判断如果name存在就覆盖旧值如果不存在就新建键值对。查询与删除利用mp.count(name)来检查键是否存在避免直接访问不存在的键导致意外插入默认值。 AC 代码实现#includebits/stdc.husingnamespacestd;intmain(){// 开启快速IO防止大数据量下输入输出超时ios::sync_with_stdio(false);cin.tie(0);longlongn;cinn;mapstring,longlongmp;while(n--){longlongop;cinop;if(op1){string name;longlongscore;cinnamescore;// map的下标操作符可以直接赋值存在则更新不存在则插入mp[name]score;coutOKendl;}elseif(op2){string name;cinname;// count()返回键出现的次数map中只能是0或1if(mp.count(name))coutmp[name]endl;elsecoutNot foundendl;}elseif(op3){string name;cinname;if(mp.count(name)){mp.erase(name);// 删除操作coutDeleted successfullyendl;}elsecoutNot foundendl;}else{// op 4coutmp.size()endl;// size()直接获取元素个数}}return0;} 第二题P1918 保龄球 题目描述DL 算得分算得很烦闷所以常常到体育馆去打保龄球解闷。因为他保龄球已经打了几十年了所以技术上不成问题于是他就想玩点新花招。DL 的眼力真的很不错虽然能够数清楚在他前方十米左右每个位置的瓶子的数量。他突然发现这是一个炫耀自己眼力的好借口——他看清远方瓶子的个数后从某个位置发球这样就能打到一定数量的瓶子。○○○○○○○○○○○如上每个 “○” 代表一个瓶子。如果 DL 想要打到 3 个瓶子就在 1 位置发球想要打到 4 个瓶子就在 2 位置发球。现在他想打倒 m 个瓶子。他告诉你每个位置的瓶子数请你给他一个发球位置。输入格式第一行包含一个正整数 n表示位置数。第二行包含 n 个正整数aia_iai​表示 i 个位置的瓶子数保证各个位置的瓶子数不同。第三行包含一个正整数 Q表示 DL 发球的次数。第四行至文件尾每行包含一个正整数 m表示 DL 想要打倒 m 个瓶子。输出格式共 Q 行。第 i 行的整数表示 DL 第 i 次的发球位置。若无解则输出 0。 解题思路与“踩坑”实录这道题乍一看很简单但很容易掉进陷阱❌错误示范暴力枚举 - TLE刚开始我的想法很直接把数据存进 map 里每次查询时遍历整个 map看看哪个值的瓶子数等于目标 m。代码如下// ❌ 错误代码时间复杂度 O(M*N)会超时for(autoitmp.begin();it!mp.end();it){if(it-secondx){// 遍历查找值kit-first;}}为什么超时因为 map 是基于 Key 排序的查找 Value 必须遍历所有元素。当N,MN, MN,M达到10510^5105级别时运算量高达101010^{10}1010计算机根本跑不完。✅正确思路反向映射我们需要利用 mapKey 查找快的特性。既然我们要通过“瓶子数”找“位置”那就把瓶子数作为 Key位置作为 Value这样查询时直接用mp[x]时间复杂度瞬间降为O(log⁡N)O(\log N)O(logN)。 AC 代码实现#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(0);longlongn;cinn;// 核心技巧反向映射Key存瓶子数Value存位置编号maplonglong,longlongmp;for(longlongi1;in;i){longlongnum;cinnum;mp[num]i;// 瓶子数是Key位置是Value}longlongm;cinm;for(inti0;im;i){longlongx;cinx;// 直接通过 Key 查找O(logN) 复杂度if(mp.count(x))coutmp[x]endl;elsecout0endl;}return0;} 第三题P1102 A-B 数对 题目背景出题是一件痛苦的事情相同的题目看多了也会有审美疲劳于是我舍弃了大家所熟悉的 AB Problem改用 A-B 了哈哈题目描述给出一串正整数数列以及一个正整数 C要求计算出所有满足A−BCA - B CA−BC的数对的个数不同位置的数字一样的数对算不同的数对。输入格式输入共两行。第一行两个正整数 N, C。第二行第 i 个数为aia_iai​数字之间用一个空格隔开共 N 个正整数作为要求处理的那串数。输出格式一行表示该串正整数中包含的满足A−BCA - B CA−BC的数对的个数。输入输出样例输入 #1输出 #14 11 1 2 33说明/提示对于 75% 的数据1≤N≤20001 \le N \le 20001≤N≤2000。对于 100% 的数据1≤N≤2×1051 \le N \le 2 \times 10^51≤N≤2×1050≤ai2300 \le a_i 2^{30}0≤ai​2301≤C2301 \le C 2^{30}1≤C230。 解题思路这道题考察的是数学公式变形 Map 计数。如果暴力双重循环查找A−BCA - B CA−BC复杂度是O(N2)O(N^2)O(N2)对于N2×105N2 \times 10^5N2×105的数据肯定超时。我们可以把公式变形为ABCA B CABC。这意味着对于数组中的每一个数BBB我们把它当作减数我们只需要知道数组里有多少个AAA等于BCB CBC即可。预处理先遍历一遍数组用mapint, long long统计每个数字出现的次数。这里 Value 必须是long long因为答案可能很大。统计答案再次遍历数组对于每个数a[i]a[i]a[i]计算目标值target a[i] C然后直接在 map 中查找target出现的次数累加到答案中。 AC 代码实现#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(0);intn,c;cinnc;vectorinta(n);// 使用 map 记录每个数字出现的次数// 注意次数可能会很多累加后需要用 long longmapint,longlongcnt;for(inti0;in;i){cina[i];cnt[a[i]];// 计数加 1}longlongans0;for(inti0;in;i){// 寻找满足 A - B C 的 A即 A B C// 当前 a[i] 是 B我们要找值为 a[i] c 的 A 有多少个inttargeta[i]c;anscnt[target];}coutans;return0;} 总结通过这三道题我们可以看到std::map的强大之处基础应用它是天然的字典适合处理字符串映射、模拟管理系统。性能优化通过反向映射交换 Key 和 Value可以将暴力查找转化为高效的二分查找。算法辅助结合数学公式变形可以将O(N2)O(N^2)O(N2)的问题优化为O(Nlog⁡N)O(N \log N)O(NlogN)。希望这篇推文能帮你更好地理解 Map 的用法如果你觉得有用欢迎点赞、在看、转发三连支持一下❤️