C++ map实现一元多项式乘法与加法：从数组、链表到STL的解题全解析

刷算法题时很多题拍脑袋能想出大致思路但一落到满分实现就出问题。一元多项式的乘法与加法运算这道20分题我前后折腾过数组、链表、map三种写法最后才服气那句map真香。题目本身并不难无非是给两个一元多项式求乘法和加法结果但真正决定能否满分的地方全在细节合并同类项、删除系数归零的项、按指数递减格式输出。只要把这三个点打透剩下的只是逻辑组织。这篇就完整拆解这道题的思路、map做法的代码以及每个测试点对应的用例和踩坑位置正在被这题卡住的同学可以直接对照着查。1. 题目拆解20分的题值钱在哪三个子问题上1.1 加法的一眼结论和容易被忽略的合并要求两个一元多项式相加从数学定义上讲非常直白把指数相同的项拎出来系数相加后保留指数不同的项原样落下来。这句话听起来简单但放到编程里就分成了两件事一是怎么快速按指数找到已有项二是系数相加后如果变成0该怎么办。第一个问题很多同学一开始会想到预先存两个数组用下标表示指数。这在一元多项式指数范围小的时候确实能跑但题目没有明确限制指数大小指数万一到几百上千数组就要开到那么大内存被白白浪费。更麻烦的是数组里的空间并不连续合并的时候要跳过大量空位逻辑变得分散。第二个问题才是真正的丢分点。比如有两个多项式一个是 (x1)另一个是 (x-1)相加后得到 (2x)指数为0的常数项被抵消掉了这一项必须从结果中删掉。如果程序里只做系数叠加不处理结果为0的情况输出就会多出0 0这一组轻则格式错重则整个测试点都判不过。1.2 乘法最容易漏掉的是配对顺序和中间合并乘法比加法多了一层循环。两个多项式相乘要对第一个多项式的每一项分别去乘第二个多项式的每一项指数相加、系数相乘累加到结果里。这个思路大多数人能马上说出来但写成代码之后问题就来了双重循环遍历出来的中间项指数顺序是错乱的必须全部收集完再统一排序输出而且同一个指数可能对应多个中间项比如 (x^2) 乘以 (x^3) 和 (x^4) 乘以 (x) 都会得到指数5的项必须合并成同一个系数。如果只做乘法不合并输出会出现指数相同的重复项判题系统直接判错。如果合并完不删零项输出又会出现误导性的系数0。1.3 输出格式不是套路是明确的判分规则题目要求按指数递减顺序输出每项输出系数 指数中间用空格隔开多项式末尾不能残留多余空格。如果结果是零多项式要输出0 0。这些约束每一条都对应一个测试点少处理一个就少拿一个分数。2. 为什么我放弃数组和链表扭头选了map2.1 数组解法在指数范围面前的无力感用数组存多项式最直观的做法是coef[exp] value指数当数组下标。只要指数范围不大比如题目保证指数不超过100那这个办法又快又简单。但一元多项式的题一般不会把话说死指数到几百上千都很常见数组长度就得跟着扩。指数要是出现负数数组下标更是直接没法用。更重要的是数组天生没法自动排序。指数是散的输出前你得自己想办法按降序把非零下标捞出来这一步又要写循环又要记索引等于把map内部本已解决的问题重新手写一遍。2.2 链表解法不是不行而是实现负担偏重教材里这个题通常出现在链表那一章所以不少人会老老实实写结构体链表。链表的好处是节省空间但代价是细节非常多合并时要维护前后指针乘法时要把新的指数和系数动态插入合适的位置插入过程还需要遍历定位。写的时候爽改的时候哭尤其是删除一个系数变0的节点时某个指针指错就是段错误或者输出顺序错乱。我在第一次写链表版时整体逻辑花了快一百行中间调试指针花了半个小时最后还是因为输出少了一个空格被扣分。这让我意识到这道题的重点根本不在于会不会写链表而在于数据结构能不能替我搞定排序和按指数查找。2.3 map恰好把三个痛点一次解决mapint,int以指数为键以系数为值。它的底层是红黑树所有元素按键自动升序排列插入、查找、删除的复杂度都是对数级别。对这道题来说它带来了三个直接红利一是poly[exp] coef可以用一行代码完成同类项合并不管指数是否重复二是迭代器直接按指数从小到大走输出时用反向迭代器就能得到从大到小的顺序三是map支持动态增删指数多大都不用预分配空间。从工程角度看map把一个原本需要手动管理的内存和排序问题变成了一个键值对的读写问题。这也是为什么我最后彻底放弃了手写链表所有精力都放在业务逻辑上。3. 加法与乘法的主逻辑map做法到底怎么组织3.1 加法的核心代码只有三行用map做加法思路是先读入两个多项式的项分别存进两个map然后把其中一个map合并到另一个map里同一个指数上的系数直接相加。代码如下#include iostream #include map using namespace std; int main() { int k1, k2; cin k1; mapint, int a, b; for (int i 0; i k1; i) { int coef, exp; cin coef exp; a[exp] coef; } cin k2; for (int i 0; i k2; i) { int coef, exp; cin coef exp; b[exp] coef; } // 加法把b合并进a mapint, int sum a; for (auto p : b) { sum[p.first] p.second; } return 0; }读入时用a[exp] coef而不是a[exp] coef是有讲究的。万一输入数据里同一个指数出现了两次前者能自动合并后者就直接覆盖了。虽然题目通常不这么刁钻但用加等写法能避开这类隐蔽问题。加法合并完成后需要把系数为0的项删掉。这一步很多人会忘但绝不能漏因为零项会影响输出判断。for (auto it sum.begin(); it ! sum.end();) { if (it-second 0) { it sum.erase(it); } else { it; } }erase在C11之后会返回下一个有效迭代器所以可以放心在循环里删。如果不记得这个特性很容易写出迭代器失效的错误代码。3.2 乘法的双重循环与指数合并乘法的主体是两个循环的嵌套。外层遍历第一个多项式的每一项内层遍历第二个多项式的每一项新的指数是两个指数的和新的系数是两个系数的积。结果存到一个新的map中依然用加等号来做中间合并。代码结构如下mapint, int mul; for (auto p : a) { for (auto q : b) { int exp p.first q.first; int coef p.second * q.second; mul[exp] coef; } } // 同样删除系数为0的中间项 for (auto it mul.begin(); it ! mul.end();) { if (it-second 0) { it mul.erase(it); } else { it; } }这段代码背后对应的是手动多项式乘法时的分配律。我习惯在注释里写按分配律展开再合并同类项这样之后回看代码能立刻想起逻辑。实际做题时只要双重循环的边界不写错合并逻辑跟加法完全一致复用同一段删除零项的代码就行。3.3 一个容易搞乱顺序的点先乘法还是先加法题目要求先输出乘法结果再输出加法结果但程序里无论先算哪个都行只要最后输出顺序对。我的建议是先把乘法和加法结果都算完再统一做输出避免算加法时不小心改动了参与乘法的原始map。因为加法如果直接原地改a再拿a去做乘法结果就会出错。最稳的操作是原始数据存两份a、b乘法从头算加法从拷贝的sum a开始算互不干扰。4. 输出细节决定20分的归属4.1 降序输出一个rbegin解决排序问题map默认按指数升序排列而题目要求按指数递减输出。很多人第一反应是先取出所有项再手写排序其实完全没必要。map提供了反向迭代器rbegin()和rend()从指数最大的位置开始向前遍历正好得到递减顺序。核心代码如下void printPoly(mapint, int poly) { if (poly.empty()) { cout 0 0; return; } bool first true; for (auto it poly.rbegin(); it ! poly.rend(); it) { if (!first) cout ; cout it-second it-first; first false; } }这里有一个细节系数和指数的顺序是系数 指数不是指数 系数。输出样例里5 20意思是系数5、指数20也就是 (5x^{20})。这个顺序写反的人非常多提交后分数照样扣。4.2 空多项式输出0 0是硬性要求如果某个多项式没有任何项比如输入第一行就是0那么不管是乘法还是加法结果都可能是空的。这时map里什么都不存在直接走poly.empty()分支输出0 0。我第一次就把这种情况漏了结果输入项数为0的测试点直接WA。要注意即使两个多项式都不为空相乘后的结果也可能因为互相抵消而变成空map比如((x1)(x-1))算出来是 (x^2-1)并没有抵消干净但如果是((x1)(x-1))与另一个多项式叠加某些项也确实可能抵消为0。所以empty()判断必须放在输出函数的开头而不是只判断输入是否为空。4.3 空格陷阱和常数项的特殊表现输出的每一项之间用空格隔开但末尾不能有空格。用first标志位控制前置空格是目前最稳妥的写法。还有一种常见错误是直接把所有内容堆在一行末尾加了空格某些判题系统对空格敏感多一个空格就是格式错误。常数项也就是指数为0的项要输出系数 0。比如常数5要输出5 0不要把它漏掉。指数为0和没有项是完全不同的两种状态前者map里有数据后者map为空输出逻辑要能区分开。4.4 常见输出错误对照表错误情况错误输出示例原因正确输出示例指数顺序颠倒5 20 -25 22遍历顺序写错15 24 -25 22末尾多空格1 2 3 4没有控制空格1 2 3 4系数指数写反20 5 22 -25输出顺序写反5 20 -25 22零项未删除1 2 0 0 3 1相加后系数为01 2 3 1空多项式乱处理不输出或输出空行没有判空0 05. 测试点逐个过样例之外的隐藏用例都帮你测了5.1 题目样例的手动验证先用标准样例走一遍流程。输入4 3 4 -5 2 6 1 -2 0 3 5 20 -7 4 3 1第一个多项式是 (3x^4 - 5x^2 6x - 2)第二个是 (5x^{20} - 7x^4 3x)。乘法展开后合并指数相同的项得到15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1加法合并后得到5 20 -4 4 -5 2 9 1 -2 0很多同学拿这个样例能跑过就以为题没问题了其实样例只覆盖了最常规的情况。5.2 (x1)(x-1) 这类合并消零用例我强烈建议你本地专门测这样一组数据2 1 1 1 0 2 1 1 -1 0也就是 ((x1)) 和 ((x-1))。乘法结果是 (x^2 - 1)减法抵消掉的是常数项还是中间项取决于具体数据。这里加法结果是 (2x)原本的 (1) 和 (-1) 抵消成0如果程序没有删除零项就会输出1 2 -1 0 2 1 0 0正确输出应该是1 2 -1 0 2 1这里能直接检验删除零项的逻辑是否正确。5.3 空多项式的组合再来一组0 1 2 3第一个是零多项式第二个是 (2x^3)。合法输出应该是乘法结果0 0加法结果2 3。如果程序没有处理输入为0的情况很可能把乘法结果也输出成空行直接格式错。同理可以测两边都为空的情况0 0输出两行0 0才正确。5.4 指数为0的常数项和负系数排序常数项是最容易被单独拎出来测试的点。比如1 8 0 1 -3 2第一个是常数8第二个是 (-3x^2)。乘法结果是 (-24x^2)输出-24 2加法结果是 (-3x^2 8)按指数递减输出是-3 2 8 0。这个用例能同时验证常数项输出、负系数输出、降序排序三个点。还有一组故意混入较多指数差的用例3 1 100 2 50 3 0 2 -2 50 4 30乘法里 (x^{100}) 和 (x^{50}) 组合会产生指数150的项同时 (2x^{50}) 与 (-2x^{50}) 相乘会产生指数100且系数为-4的项注意合并后不一定抵消。这种大指数组合最考验map是否有足够的空间和排序能力。6. WA之后我从哪里开始查一条完整排查链路6.1 先看输入读法再看算法我第一次提交WA的时候第一反应是怀疑算法错了结果反复检查后发现问题出在输入上。当时用了while(cin coef exp)来读但题目中每个多项式第一行是项数后面才是项这种读法会把项数当成系数读进去。正确做法是先读项数再用for循环读固定数量的项。这是很多初学者的第一道坎排查顺序上应该放在第一位。6.2 用临时调试输出看map内部状态如果输入读法没错下一步就是确认map里到底存了什么。我会在计算乘法之前先打印一遍两个原始map再打印乘法结果比如for (auto p : a) { cerr a: p.second p.first endl; } for (auto p : mul) { cerr mul: p.second p.first endl; }用cerr而不是cout是因为不影响最终提交的输出。看到中间状态后很多问题一眼就能定位是乘法漏了某些配对还是合并时用了赋值而不是加等又或者是删除零项时把迭代器搞失效。6.3 逐字符对输出空格和换行都不放过如果把数据打印出来都对了输出还是WA那问题基本在格式。建议把正确输出和程序输出放到两个文件里用diff命令逐字符比较。如果只在肉眼层面看很容易忽略末尾多一个空格这种细节。我第一次用diff对比时才发现自己一直在每行末尾多输出了一个空格。改完空格问题之后那道题直接满分。6.4 多测试几组极端抵消数据再提交平时在自己的测试里一定要主动制造系数抵消的场景比如((2x^23)(-2x^23))这种中间项会完全抵消。只有把消零、删除、排序、格式全部验证到位提交时才不会在隐藏测试点上翻车。7. map做法能延伸到的其他场景7.1 指数范围大到离谱时同一套代码照样跑有些同学担心map在指数很大的情况下性能不够。实际上一元多项式的项数通常不超过几百红黑树的操作复杂度是对数级跑起来非常轻松。就算指数达到一百万map也不会因为指数大而多占内存只有实际存在的项才会创建节点这比数组解法优雅太多。7.2 如果题目要求按升序输出只需改一个迭代方向现在大多题目要求指数递减用rbegin()就行了。但如果哪天遇到要求递增输出的题目或者要求同时给出两种顺序只需要把反向迭代器换成普通迭代器其他代码完全不用动。这就是map做法可移植性好的地方排序逻辑被容器替你承担了。7.3 同样思路可以迁移到稀疏矩阵和多项式求导map以键值对形式存储稀疏数据的特点不仅适合一元多项式也适合稀疏矩阵的加法乘法。如果你以后再遇到稀疏多项式求导两个稀疏多项式做卷积这类题目基本思路都是把键当成位置索引把值当成权重计算时按位置合并。这比重新设计一套链表结构省力得多。最后说句实在话算法竞赛里使用STL不是偷懒而是把已解决的问题交给成熟容器把精力留在真正需要思考的地方。这道一元多项式题我后来复盘时觉得最有价值的收获不是会做乘法而是理解了数据结构选型对实现效率的巨大影响。你要是也卡在这题上按这篇的顺序理一遍逻辑重点检查合并、删零、输出格式这三关应该很快就能跑通。