C++ STL map求解一元多项式乘法与加法运算详解

说实话第一次在考场上看到这道“一元多项式的乘法与加法运算”时我的表情大概是这样的题目不长逻辑也不绕但真到动手写代码的时候就发现一堆细枝末节能把人坑到怀疑人生。这道题在数据结构与算法课程里算是“线性结构”阶段的经典练习也是很多学校机试、期末上机的常客。核心就两件事给两个一元多项式让你算它们的和与积按规定的格式输出结果。这道题最容易让人翻车的不是加减乘除本身而是输入格式、输出格式、零多项式的特判以及指数和系数在运算过程中的细节处理。很多同学用数组硬解也能过但写得又长又容易错。我自己后来改用C STL里的map来做发现整个过程清爽得不是一点半点——map天然支持按键排序、按键查找、自动去重合并简直是为这道题量身定做的工具。下面直接把我的完整思路、实现细节、测试点分析全部摊开来讲争取让你看完就能自己写出满分代码而不是只会对着题面发呆。1. 题意与解题思路拆解先别急着写代码把题目本身吃透。这个题目的输入分两行第一行第一个多项式的项数 n然后跟着 2n 个整数每两个一组分别是这一项的系数和指数。第二行第二个多项式的项数 m然后跟着 2m 个整数同样每两个一组。举个例子输入可能是这样的4 3 4 -5 2 6 1 -2 0 3 2 3 4 1 -5 0第一行意思是第一个多项式有 4 项分别是3x^4 - 5x^2 6x - 2。第二行意思是第二个多项式有 3 项分别是2x^3 4x - 5。注意一个细节输入里给定的项已经不包含零系数项但并没有保证指数按从高到低或者从低到高排列——题目没有明确说有序所以你在处理时不能依赖输入顺序必须自己完成排序和合并。输出要求也很严格按“系数 指数”的格式输出每一项之间用空格隔开行尾不能有空格。如果结果是零多项式也就是所有系数加起来或乘起来全为 0则输出0 0。说白了题目在考三个能力多项式的加法运算规则指数相同的项系数相加。多项式的乘法运算规则每一项之间交叉相乘系数相乘指数相加然后合并同类项。结果的组织与格式化输出按指数降序排列、过滤零系数、处理空结果。如果你用数组来写脑子里要想清楚下标到底是系数还是指数要不要开 2001、4001 这么大的数组怎么处理负指数——虽然这道题指数是非负的但设计一个够用的上界还是得纠结一阵。用 map 就没有这些问题。我选 map 的理由很直接它把“指数”和“系数”这一对映射关系直接建模成键值对键就是指数值就是系数。加法时直接对相同键累加乘法时用两重循环把生成的新键值放进另一个 map 自动合并所有同类项合并的操作都被 map 的特性接管了。2. map容器用法与选择理由map 是 C STL 里的关联容器底层是红黑树。它有两个和这道题高度契合的特性第一键是唯一的。如果你在 map 里执行mp[key] value而 key 第一次出现时就自动创建并初始化为 0第二次出现时直接在上一次的值上累加。这正好就是合并同类项需要的语义。第二键自动排序。map 默认按照键的大小升序排列也就是指数从低到高。可题目要求输出时指数从高到低所以最后输出要倒着遍历。这个用一个反向迭代器mp.rbegin()到mp.rend()就能解决根本不用手动排序。很多初学者第一次接触 map 会有一个疑惑mp[key]如果 key 不存在会直接插入一个默认值吗答案是会。对 int 类型的 value默认值是 0。这个特性看起来方便但也有隐患——你拿if (mp[key] 0)去做判断的时候可能无意中向 map 里插入一个本来不存在的键。更稳妥的写法是先用mp.count(key)或mp.find(key)判断键是否存在再决定是插入还是累加。再说说选用 map 的另一个深层原因鲁棒性。数组解法虽然在这道题里可行因为指数范围是有限的非负整数但万一指数范围很大数组就撑不住了。map 的键可以是任意可比类型不受范围限制。而且代码的可读性也更好别人一看你的代码就知道“指数是键系数是值”逻辑一目了然。当然 map 也有它的代价底层红黑树的单次操作复杂度是 O(log k)k 是项的个数。这道题 n 和 m 都不大撑死几十项乘法之后最多也就几千个键值对O(logn) 和 O(1) 的差别根本看不出来。如果你在一个对性能极其敏感的大型系统里处理海量多项式运算那另当别论但应付考试和课程作业map 是兼顾简洁与效率的最优解。3. 完整实现与关键代码解析直接上代码我用的是 C因为 map 是 STL 的东西用起来最顺手。#include iostream #include map using namespace std; int main() { // 读入第一个多项式 int n; cin n; mapint, int poly1; // 键指数值系数 for (int i 0; i n; i) { int coef, exp; cin coef exp; poly1[exp] coef; } // 读入第二个多项式 int m; cin m; mapint, int poly2; for (int i 0; i m; i) { int coef, exp; cin coef exp; poly2[exp] coef; } // 乘法每一项交叉相乘 mapint, int product; for (auto p1 : poly1) { for (auto p2 : poly2) { int newExp p1.first p2.first; int newCoef p1.second * p2.second; product[newExp] newCoef; } } // 加法先拷贝 poly1再把 poly2 的每一项累加进去 mapint, int sum poly1; for (auto p2 : poly2) { sum[p2.first] p2.second; } // 输出乘法的结果 bool firstFlag true; for (auto it product.rbegin(); it ! product.rend(); it) { if (it-second 0) continue; if (!firstFlag) cout ; cout it-second it-first; firstFlag false; } if (firstFlag) cout 0 0; cout endl; // 输出加法的结果 firstFlag true; for (auto it sum.rbegin(); it ! sum.rend(); it) { if (it-second 0) continue; if (!firstFlag) cout ; cout it-second it-first; firstFlag false; } if (firstFlag) cout 0 0; cout endl; return 0; }这段代码的骨架非常清晰读入两个多项式到两个 map算乘法用一个二重循环算加法直接拷贝一份再累加输出时用反向迭代器保证指数降序。有几个细节我要单独拎出来说明输出格式里那个firstFlag是干什么的它就是控制空格用的。第一个输出的项前面不加空格后面的每一项前面都要加一个空格。如果你不管三七二十一每一项前面都输出空格行尾就会多出一个多余的空格这道题会报格式错误PE。如果你用“先输出第一个然后循环输出‘空格项’”的方式也可以但要用一个标志位区分是不是第一个上面代码里的写法是最不容易出错的。还有一个细节加法这里为什么mapint, int sum poly1;而不是把 poly1 和 poly2 的项一一加进一个空 map因为直接拷贝 poly1 可以省掉后面处理 poly1 的循环一次拷贝抵得上遍历一遍 poly1 的复杂度。当然你写两重循环处理也行但拷贝更优雅。关于乘法里的“合并同类项”有个容易踩的坑乘法会产生完全相同的指数比如(x^2) * (2x^3)和(2x^3) * (x^2)都会生成指数 5、系数 2 的项。如果你每次乘完直接 push 到数组里不合并最后就要自己再做一次合并排序。而用 map 后product[newExp] newCoef天然把这种重复键的值累加起来了完全不用手动处理。还有一点如果两个多项式中本身就含有系数为 0 的项比如输入给你0 5系数 0 指数 5你存进 map 后这一项在输出时会被if (it-second 0) continue;过滤掉逻辑上完全正确。这类脏数据在测试点里出现过所以过滤环节一个都不能少。4. 测试点分析与坑点实录题目明面上只有短短几行描述但隐藏在背后的边界条件至少可以拆出六个测试点。我把它们全部列出来并给出对应的输入和预期输出你照着自查一遍就能知道自己的代码到底漏了哪里。测试点 1基础加法与乘法输入 2 1 2 1 1 2 1 2 1 1第一个多项式是x^2 x第二个也是x^2 x。加法结果是2x^2 2x乘法结果是x^4 2x^3 x^2。预期输出1 4 2 3 1 2 2 2 2 1这个测试点考察最基本的规则大多数人都能过。测试点 2加法结果为 0输入 2 1 1 -1 1 1 1 1第一个多项式是x - x 0不对等等——仔细看第一项系数 1 指数 1第二项系数 -1 指数 1合并后指数 1 的系数是 0。第二个多项式是x。加法结果是x乘法结果是 0。预期输出0 0 1 1这个测试点专门考察一个多项式内部自己就有抵消项指数相同、系数一正一负在做加法和乘法之前这些项必须已经合并掉了。测试点 3乘法结果为 0输入 1 0 5 1 3 2第一个多项式是0x^5也就是 0。第二个是3x^2。乘法结果 0加法结果3x^2。预期输出0 0 3 2这个测试点是很多人的拦路虎。因为输入给了系数为 0 的项你如果不做过滤最后输出的时候会把0 5那一项也打出来结果就错了。正确做法是把系数为 0 的项在判空之前直接跳过。测试点 4常数项与零多项式输入 1 2 0 1 -3 0第一个是2第二个是-3。加法结果-1乘法结果-6。预期输出-6 0 -1 0常数项的指数是 0这种特殊情况尤其要注意指数 0 在 map 里和其他指数一样正常处理而输出时不能把 0 当作“没有项”。测试点 5指数跨度大考察降序输出输入 3 1 10 2 5 3 0 2 4 2 5 3第一个是x^10 2x^5 3第二个是4x^2 5x^3。你需要自己做乘法和加法并确认输出时指数是从大到小排的。这个测试点用来考察反向迭代器的正确性如果你用的是正向迭代器或者忘了排序输出顺序就会反。测试点 6多项式中包含指数相同的项需要合并输入 3 1 2 2 2 3 2 1 1 2第一个多项式输入了三项但指数全部是 2合并后是6x^2。第二个是x^2。加法结果是7x^2乘法结果是6x^4。预期输出6 4 7 2这个测试点专门考察 map 的自动合并能力。如果你用数组硬解得自己写合并逻辑用 map 的话poly1[exp] coef已经搞定了。我把这些测试点总结成一张表方便你对照测试点考察内容关键预期1基础运算正常输出乘法和加法结果2多项式内部抵消加法后零项被过滤3系数为0的项乘法结果为0时输出“0 0”4常数项指数0的项正常处理5指数降序输出从高次到低次6同类项合并相同指数合并为一个系数除了测试点里能看到的坑还有几个我在实际调试中碰到的“隐性陷阱”这里一起说清楚。第一个坑是关于输出顺序的。题目要求“按指数降序输出”这个降序指的是指数从大到小。map 默认升序很多第一次写的人直接for (auto p : mp)输出结果整个顺序反了。用rbegin()和rend()就能优雅解决不要手动把数据搬到 vector 再sort那是绕远路。第二个坑是 map 在operator[]中可能“无中生有”。在输出循环里如果你写的是if (mp[it-first] 0) continue;这里的it-first是已经存在的键那没问题。但如果你写的是if (mp[某个不存在的键] 0)map 就会偷偷插一个键进去导致遍历时多出不该有的项。所以判断时不要再用operator[]直接判断it-second就行。第三个坑是输入项数很大时的读入性能。这道题 n 和 m 通常不超过 100用cin完全够。但如果你在其他类似题目里遇到很大的输入规模建议关掉同步ios::sync_with_stdio(false); cin.tie(0);否则cin在某些平台上会比较吃力。第四个坑是空格输出的次序。很多人喜欢用“先输出第一个再循环输出空格”的正向思路但如果你用的是“每一项都输出一个前置空格”的反向思路第一项前也会多一个空格。用firstFlag是最直的思路也最容易验证正确性。5. 常见问题与调试技巧在写代码和跑测试点的过程中我把大家容易犯的错整理成了一组速查表每一类都配有典型的错误写法和修正建议。错误类型错误写法正确写法的关键合并遗漏乘法结果直接 push 数组不合并用product[newExp] newCoef排序错误正序遍历 map 直接输出用反向迭代器零项未过滤不判断系数是否为 0 就输出遍历时跳过second 0的项多余空格每项输出前都打空格用firstFlag控制零多项式认为结果为空就不是多项式空结果时输出“0 0”读入失败用 while(cin n) 循环读按题目要求读两行重复累加加法时把 poly1 和 poly2 合并到新 map 时忘了初始化mapint,int sum poly1除了这些比较“宏”的错误我还想分享几个亲测有效的调试技巧。第一招造小型用例手动脑算。写代码之前先拿一个 2 项 2 项的例子比如(x^2 1)乘以(2x 3)在纸上把2x^3 3x^2 2x 3写出来。然后跑你的代码看输出是不是完全一致。如果这一步就对不上后面的复杂用例只会错得更离谱。第二招把输出过程可视化。如果你对输出格式不放心可以在循环里临时加一句注释掉的调试输出把每一项的系数和指数打印到标准错误流cerr里。反正最终版本删掉调试代码就行能节约你很多排查时间。第三招做“零检测”练习。专门设计一个答案为零多项式的用例确认程序输出的是0 0而不是什么都不输出或者输出多余空格。零多项式的表现是很多同学最后卡住的最后一关。第四招关于“负零”问题。既然输入可能有负数系数那理论上可能存在-0这种东西吗C 里整数的 0 不会有正负之分所以不用担心。但如果你把系数存成浮点数就真的要小心了好在题目给的是整数。还有一个我认为值得多说两句的关于 map 遍历时删除元素。有些同学会在遍历过程中根据条件erase掉系数为 0 的项这个问题在 C 不同版本里行为不一样非常容易出错。我的建议是遍历之前先做一次过滤或者干脆遍历时不删除只跳过不输出。不要在输出循环里写mp.erase(it)尤其是配合rbegin()时反向迭代器的 erase 行为很反直觉容易把迭代器搞崩直接导致运行时错误。其实这道题还有一个隐藏的考点就是你能不能理解“乘积多项式的项数”和“合并后的项数”完全是两码事。乘法展开时最多可能有 n 乘以 m 项但其中大量是指数相同可以合并的。用 map 后合并自动完成项数的变化对你透明你只需要关心最终 map 里有多少个非零键值对。6. map做法的延展思考这道题用 map 虽然香但我不建议只停留在“会写”这个层面。等你熟练掌握了 map 的使用可以继续思考几个延展方向如果输入里包含多个变量比如一个多项式同时含 x 和 y那映射关系就从“指数→系数”变成“(指数x, 指数y)→系数”。C 的 map 可以用pairint,int作为键比较规则自动按字典序这个扩展其实很容易实现。如果要做多项式的除法那就不能只用 map 了因为每一步要“对齐”高次项运算逻辑更复杂。但加法乘法的基础能力依然是核心。如果你偏爱函数式风格可以试试用 Python 的字典推导式或defaultdict实现同样的逻辑思路完全一致只不过 C 的 map 对类型约束更严格、性能更可控。我自己在实际应用中还有一个习惯把“多项式的加法和乘法”封装成一个类或者函数输入输出做统一接口。以后再做类似的表达式计算题直接复用这套逻辑省去重新调试的时间。你如果想练手可以试着把这个题的代码改成支持动态传入两个多项式并返回结果的形式这样离真正的工程化代码又近了一步。最后再分享一个个人体会每次遇到“数据结构”类题目不要急着写代码先花两分钟想想“这个数据形态最适合用什么容器来建模”。容器选对了你写的代码不仅短而且几乎没有隐蔽错误。map 用在这道题上是“真香”的典型这种思路可以迁移到很多类似题目比如多项式求导、稀疏矩阵相加、频次统计等都是一通百通的应用场景。希望这篇详解能帮你一次把这道 20 分题稳稳拿下。