1. 从一道经典题看多项式加法不只是AB那么简单“AB for Polynomials” 这行字对于任何一个刷过PAT浙江大学计算机程序设计能力考试甲级、乙级或者准备过类似编程能力测试的人来说都再熟悉不过了。它通常以“1002”这样的题号出现是数据结构与算法入门的一道“门神”。表面上看题目要求简单到令人发指给你两个多项式每个多项式由若干项组成每项包含一个非零的系数和一个指数要求你计算这两个多项式的和并按指数降序输出结果中非零的项。很多新手甚至一些有经验的程序员看到这里可能已经打开了IDE准备用两个数组或者两个map把指数映射到系数然后遍历相加最后排个序输出。搞定提交。然后他们可能会遇到一些意想不到的“坑”比如系数相加后恰好为0的项需要被“吞掉”不输出比如输出的格式要求非常严格指数和系数的小数位数都有规定再比如当两个多项式项数很多时如何高效地合并。这道题之所以经典绝不仅仅是因为它考察了基础的输入输出和算术运算。它像一面镜子清晰地照出了编程者对于数据表示、算法效率和边界处理这三个核心工程能力的理解深度。一个合格的实现和一个优秀的实现中间隔着对“合并”操作本质的思考。今天我们就以这道题为引子深入聊聊多项式表示与运算背后的那些事以及如何写出一个既正确又优雅的解法。你会发现这远不止是“AB”那么简单。2. 多项式加法的本质与核心挑战在动手写代码之前我们必须先想清楚我们在操作的对象到底是什么一个一元多项式例如3.4x^5 2.1x^2 - 1.7其核心信息是一系列系数指数对。这里的“一系列”意味着顺序不是本质属性虽然我们通常按指数排序以便阅读本质是一个从指数到系数的映射关系。2.1 数据结构的选型数组、链表还是映射这是第一个分水岭。不同的选择直接决定了算法的效率和实现的复杂度。数组或向量这是最直观的想法。我们可以声明一个足够大的数组coef[1001]下标代表指数值代表系数。对于指数范围明确例如题目常限定指数为0到1000的非负整数且范围不大的情况这种方法极其高效。相加操作就是一次线性遍历result_coef[i] a_coef[i] b_coef[i]。时间复杂度是O(N)其中N是指数范围。它的缺点是空间可能浪费如果多项式很稀疏只有少数几项且无法直接处理指数范围很大或不确定的情况。有序链表每个节点存储一项系数指数下一节点指针。输入时即按指数降序插入保证链表有序。合并两个有序链表是数据结构课的经典算法时间复杂度O(MN)空间复杂度O(1)如果复用节点。它天然支持指数范围很大的情况且空间利用紧凑。缺点是代码实现比数组稍复杂需要小心处理指针和节点插入/删除。有序映射如 C 的std::map或std::unordered_map 排序map红黑树实现本身按键指数有序自动处理了排序问题。插入和查找是对数时间复杂度。相加过程就是遍历一个map将项加到另一个map中如果系数加为零则删除该项。最后遍历输出即可。这种方法代码最简洁几乎贴近于我们对“映射”这一数学概念的直译在项数不是特别巨大时表现良好。unordered_map哈希表插入查找更快平均O(1)但最后需要将结果拷贝到向量中排序输出。注意在实际解题如PAT中由于指数范围通常明确如0~1000且时间限制宽松使用数组法往往是代码最短、运行最快、最不易出错的选择。它避免了动态内存管理和复杂数据结构的细节让你能更专注于处理题目本身的边界条件。这就是“在正确的场景选择最简单的工具”。2.2 算法核心合并有序序列无论采用上述哪种结构多项式加法的核心算法都是合并两个有序序列。这与合并两个有序数组、两个有序链表的思路完全一致。我们维护两个指针或迭代器分别指向两个多项式当前待处理的项指数最大的项。比较两个指针所指项的指数如果指数相等则系数相加。若结果不为零则在结果中新增一项若结果为零则两项抵消两个指针都后移。如果A的指数大于B的指数则将A的当前项加入结果A指针后移。如果B的指数大于A的指数则将B的当前项加入结果B指针后移。这个过程一直进行到两个多项式的所有项都处理完毕。这个算法是一次遍历时间复杂度是线性的O(MN)是最高效的方式。如果使用数组法这个“合并”过程就隐含在了逐下标相加的过程中。2.3 边界与精度魔鬼在细节中这是这道题主要的“坑点”也是区分代码是否健壮的关键。系数为零项的消除这是题目明确要求的。在数组法中这意味着在统计结果项数或输出时要跳过系数为零的位置。在链表或映射法中意味着在系数相加为零时要删除该节点或条目。务必注意两个多项式输入时保证系数非零但相加后可能产生零这是一个必须处理的边界条件。输出格式这是OJOnline Judge题目常见的严格之处。通常要求先输出结果中的非零项个数K。随后输出K行或在一行内以空格分隔每行按“指数 系数”的格式。指数必须按降序排列。系数保留小数点后1位例如用printf(“%.1f”)。这里必须注意浮点数的精度问题虽然本题数据通常不会涉及极端精度但使用double类型并遵循格式化输出是良好习惯。零多项式这是一个极端但重要的边界情况。如果两个多项式完全抵消结果为零多项式。此时输出的项数K应为0。在数组法中遍历完整个数组都找不到非零系数在链表/映射法中结果容器为空。之后通常不需要再输出任何系数指数对或者有些题目要求输出一个空行。务必仔细阅读题目输出说明。3. 三种实现方案的代码级拆解与对比理解了原理我们来看代码。我将分别用数组、链表和映射C实现并分析各自的优劣。假设题目输入格式为每个多项式第一行是一个整数K表示该多项式的非零项数随后K行每行给出一个指数和系数。3.1 方案一数组法静态数组这是最推荐在限时编程中使用的方案尤其是当指数范围已知时。#include cstdio const int MAX_EXP 1001; // 假设最大指数为1000 double poly[MAX_EXP] {0}; // 数组初始化下标为指数值为系数 int main() { int k, exp; double coef; // 读取第一个多项式 scanf(%d, k); for (int i 0; i k; i) { scanf(%d %lf, exp, coef); poly[exp] coef; // 直接加到对应位置 } // 读取第二个多项式 scanf(%d, k); for (int i 0; i k; i) { scanf(%d %lf, exp, coef); poly[exp] coef; // 继续累加 } // 统计非零项个数 int count 0; for (int i 0; i MAX_EXP; i) { if (poly[i] ! 0.0) { // 注意浮点数比较通常与0比较是安全的 count; } } // 输出 printf(%d, count); // 注意题目要求降序输出所以从最高指数向低遍历 for (int i MAX_EXP - 1; i 0; i--) { if (poly[i] ! 0.0) { printf( %d %.1f, i, poly[i]); // 格式空格分隔系数1位小数 } } // 如果count为0这里就只输出了一个0符合要求 return 0; }为什么这样设计空间换时间简化逻辑我们牺牲了最多1001个double的空间约8KB换来了极致简单的逻辑。相加操作就是简单的数组累加O(1)复杂度。规避排序因为数组下标天然有序输出时从高到低遍历即可完全不需要排序操作。易于处理零项统计和输出时用一个if判断跳过零系数即可。输入顺序无关无论输入的多项式项是否有序都不影响结果正确性。实测心得在PAT等OJ上这种方法的代码行数最少运行速度最快几乎不会超时。浮点数比较poly[i] ! 0.0在本题场景下是安全的因为数据是精确的。但在更一般的数值计算中判断浮点数是否为零应使用fabs(poly[i]) 1e-8之类的精度容差。一定要看清指数范围。如果题目说指数是0~1000那么数组大小至少为1001。如果指数可能为负则需要进行偏移例如poly[exp 1000]或者改用其他方法。3.2 方案二有序链表法这种方法更贴近数据结构教学能锻炼指针操作能力适用于指数范围未知或很大的情况。#include cstdio #include algorithm // 用于sort如果输入无序则需先排序 struct Node { int exp; double coef; Node* next; Node(int e, double c) : exp(e), coef(c), next(nullptr) {} }; // 向有序降序链表中插入一项如果指数已存在则合并系数为零则删除 Node* insertOrAdd(Node* head, int exp, double coef) { if (coef 0.0) return head; // 系数为零直接忽略 Node dummy(-1, 0.0); // 哑节点简化头节点插入处理 dummy.next head; Node* prev dummy; Node* curr head; // 寻找插入位置找到第一个指数小于等于当前指数的节点 while (curr ! nullptr curr-exp exp) { prev curr; curr curr-next; } if (curr ! nullptr curr-exp exp) { // 指数相同合并系数 curr-coef coef; if (curr-coef 0.0) { // 系数抵消删除该节点 prev-next curr-next; delete curr; } } else { // 指数不同创建新节点插入到prev和curr之间 Node* newNode new Node(exp, coef); newNode-next curr; prev-next newNode; } return dummy.next; // 返回新的头节点 } int main() { Node* resultHead nullptr; int k, exp; double coef; // 处理两个多项式 for (int polyNum 0; polyNum 2; polyNum) { scanf(%d, k); for (int i 0; i k; i) { scanf(%d %lf, exp, coef); resultHead insertOrAdd(resultHead, exp, coef); } } // 统计并输出 int count 0; Node* p resultHead; while (p ! nullptr) { count; p p-next; } printf(%d, count); p resultHead; while (p ! nullptr) { printf( %d %.1f, p-exp, p-coef); p p-next; } // 释放内存在实际OJ中可省略但好习惯 while (resultHead ! nullptr) { Node* temp resultHead; resultHead resultHead-next; delete temp; } return 0; }为什么这样设计动态空间只为非零项分配空间在多项式非常稀疏时比数组法更省内存。在线处理insertOrAdd函数保证了链表始终有序可以边读入边合并无需等待所有输入完毕再排序。通用性强不依赖固定的指数范围。踩坑点指针操作易错特别是处理头节点插入、节点删除时使用哑节点dummy node可以极大简化逻辑避免对头节点的特殊判断。内存管理在OJ环境中程序结束操作系统会回收内存所以不delete也可以。但在实际工程或养成好习惯的角度应该释放。注意如果题目时间极端苛刻频繁的new/delete可能成为性能瓶颈。输入有序假设上面的insertOrAdd假设每次插入都可能在任意位置。如果题目保证输入的多项式项是按指数降序给出的那么合并算法可以进一步优化为类似合并有序链表的O(MN)算法而无需在插入时查找位置。但通常OJ不保证这一点所以上述通用插入法更稳妥。3.3 方案三映射法使用 std::map利用C STL的map代码可以非常简洁。#include cstdio #include map #include algorithm // 用于reverse_iterator using namespace std; int main() { mapint, double, greaterint polyMap; // greaterint使map按key降序排列 int k, exp; double coef; for (int polyNum 0; polyNum 2; polyNum) { scanf(%d, k); for (int i 0; i k; i) { scanf(%d %lf, exp, coef); polyMap[exp] coef; // 如果相加后系数为零需要删除该项 if (polyMap[exp] 0.0) { polyMap.erase(exp); } } } // 输出 printf(%d, (int)polyMap.size()); for (auto it polyMap.begin(); it ! polyMap.end(); it) { printf( %d %.1f, it-first, it-second); } return 0; }为什么这样设计代码极度简洁map自动处理了键的排序和唯一性我们只需要关心系数的累加和归零删除。表达直观polyMap[exp] coef;这行代码几乎就是数学定义的直接翻译。灵活通过自定义比较器greaterint轻松实现降序输出无需反转。性能考量每次polyMap[exp]操作如果exp不存在会先插入一个默认构造的值0.0然后返回引用进行加法。这比数组的直接寻址慢但代码更清晰。对于项数N插入和查找的时间复杂度是O(log N)。对于本题规模完全足够。需要注意在系数累加为零后必须手动erase该项否则它会作为一个系数为零的项留在map中影响后续计数和输出。这是使用map时的一个关键细节。4. 举一反三多项式运算的扩展与应用解决了加法我们很自然地会想到其他运算减法、乘法、求导、积分甚至是求值。这些运算的核心依然离不开我们之前讨论的数据表示和核心算法。4.1 多项式乘法乘法比加法复杂。多项式A乘以B结果是A的每一项与B的每一项相乘系数相乘指数相加然后将所有乘积项合并同类项。数组法实现乘法如果指数范围有限如0~1000两个多项式相乘结果的指数范围会扩大0~2000。我们可以用一个两倍大小的结果数组result_coef[2001]。两层循环遍历两个多项式的非零项进行乘积累加result_coef[i j] a_coef[i] * b_coef[j]。最后遍历结果数组输出非零项。时间复杂度O(M*N)对于指数范围K则是O(K^2)。在K1000时百万级操作也是瞬间完成。链表/映射法实现乘法需要双重循环生成所有乘积项存入一个临时容器如mapint, double在插入时合并同类项。最后输出该容器。代码比数组法稍复杂但原理相同。4.2 多项式求值与霍纳法则给定多项式P(x) a_n*x^n a_{n-1}*x^{n-1} ... a_1*x a_0和一个值x0求P(x0)。 最笨的方法是计算每一项a_i * pow(x0, i)然后求和需要多次计算幂效率低。霍纳法则Horner‘s Rule提供了高效的方法P(x0) (...((a_n * x0 a_{n-1}) * x0 a_{n-2}) * x0 ... a_1) * x0 a_0。 从最高次项开始依次乘x0并加上低一次项的系数。只需要n次乘法和n次加法。// 假设系数存储在数组coef中coef[i]对应x^i的系数且已知最高次项为n double horner(double coef[], int n, double x0) { double result coef[n]; for (int i n - 1; i 0; i--) { result result * x0 coef[i]; } return result; }如果多项式是用链表降序存储的遍历链表执行同样的累加过程即可。4.3 工程中的应用场景你以为多项式运算只存在于教科书和编程题中吗远非如此。计算机图形学贝塞尔曲线、B样条曲线的参数方程就是多项式或有理多项式。曲线的绘制、求交、分割等操作底层都在进行多项式运算。数值分析多项式插值拉格朗日插值、牛顿插值、多项式拟合最小二乘法是逼近复杂函数、进行数据分析的基础工具。密码学与编码理论某些加密算法和纠错码如Reed-Solomon码的运算是在有限域上的多项式环中进行的。符号计算系统如Mathematica、Maple其核心功能之一就是进行符号化的多项式运算因式分解、展开、求最大公因式等。所以熟练掌握多项式的表示和基本运算是通向这些更高级领域的一块坚实的垫脚石。下次你再看到“AB for Polynomials”希望你能意识到它不是一个简单的加法题而是一个关于如何优雅、高效地表示和操作结构化数据的经典案例。从数组的暴力美学到链表的精细操作再到映射的抽象简洁不同的实现反映了你对问题不同层面的理解和权衡。这才是编程真正有趣的地方。 从多项式加法看数据结构选型：数组、链表与映射的实战对比
1. 从一道经典题看多项式加法不只是AB那么简单“AB for Polynomials” 这行字对于任何一个刷过PAT浙江大学计算机程序设计能力考试甲级、乙级或者准备过类似编程能力测试的人来说都再熟悉不过了。它通常以“1002”这样的题号出现是数据结构与算法入门的一道“门神”。表面上看题目要求简单到令人发指给你两个多项式每个多项式由若干项组成每项包含一个非零的系数和一个指数要求你计算这两个多项式的和并按指数降序输出结果中非零的项。很多新手甚至一些有经验的程序员看到这里可能已经打开了IDE准备用两个数组或者两个map把指数映射到系数然后遍历相加最后排个序输出。搞定提交。然后他们可能会遇到一些意想不到的“坑”比如系数相加后恰好为0的项需要被“吞掉”不输出比如输出的格式要求非常严格指数和系数的小数位数都有规定再比如当两个多项式项数很多时如何高效地合并。这道题之所以经典绝不仅仅是因为它考察了基础的输入输出和算术运算。它像一面镜子清晰地照出了编程者对于数据表示、算法效率和边界处理这三个核心工程能力的理解深度。一个合格的实现和一个优秀的实现中间隔着对“合并”操作本质的思考。今天我们就以这道题为引子深入聊聊多项式表示与运算背后的那些事以及如何写出一个既正确又优雅的解法。你会发现这远不止是“AB”那么简单。2. 多项式加法的本质与核心挑战在动手写代码之前我们必须先想清楚我们在操作的对象到底是什么一个一元多项式例如3.4x^5 2.1x^2 - 1.7其核心信息是一系列系数指数对。这里的“一系列”意味着顺序不是本质属性虽然我们通常按指数排序以便阅读本质是一个从指数到系数的映射关系。2.1 数据结构的选型数组、链表还是映射这是第一个分水岭。不同的选择直接决定了算法的效率和实现的复杂度。数组或向量这是最直观的想法。我们可以声明一个足够大的数组coef[1001]下标代表指数值代表系数。对于指数范围明确例如题目常限定指数为0到1000的非负整数且范围不大的情况这种方法极其高效。相加操作就是一次线性遍历result_coef[i] a_coef[i] b_coef[i]。时间复杂度是O(N)其中N是指数范围。它的缺点是空间可能浪费如果多项式很稀疏只有少数几项且无法直接处理指数范围很大或不确定的情况。有序链表每个节点存储一项系数指数下一节点指针。输入时即按指数降序插入保证链表有序。合并两个有序链表是数据结构课的经典算法时间复杂度O(MN)空间复杂度O(1)如果复用节点。它天然支持指数范围很大的情况且空间利用紧凑。缺点是代码实现比数组稍复杂需要小心处理指针和节点插入/删除。有序映射如 C 的std::map或std::unordered_map 排序map红黑树实现本身按键指数有序自动处理了排序问题。插入和查找是对数时间复杂度。相加过程就是遍历一个map将项加到另一个map中如果系数加为零则删除该项。最后遍历输出即可。这种方法代码最简洁几乎贴近于我们对“映射”这一数学概念的直译在项数不是特别巨大时表现良好。unordered_map哈希表插入查找更快平均O(1)但最后需要将结果拷贝到向量中排序输出。注意在实际解题如PAT中由于指数范围通常明确如0~1000且时间限制宽松使用数组法往往是代码最短、运行最快、最不易出错的选择。它避免了动态内存管理和复杂数据结构的细节让你能更专注于处理题目本身的边界条件。这就是“在正确的场景选择最简单的工具”。2.2 算法核心合并有序序列无论采用上述哪种结构多项式加法的核心算法都是合并两个有序序列。这与合并两个有序数组、两个有序链表的思路完全一致。我们维护两个指针或迭代器分别指向两个多项式当前待处理的项指数最大的项。比较两个指针所指项的指数如果指数相等则系数相加。若结果不为零则在结果中新增一项若结果为零则两项抵消两个指针都后移。如果A的指数大于B的指数则将A的当前项加入结果A指针后移。如果B的指数大于A的指数则将B的当前项加入结果B指针后移。这个过程一直进行到两个多项式的所有项都处理完毕。这个算法是一次遍历时间复杂度是线性的O(MN)是最高效的方式。如果使用数组法这个“合并”过程就隐含在了逐下标相加的过程中。2.3 边界与精度魔鬼在细节中这是这道题主要的“坑点”也是区分代码是否健壮的关键。系数为零项的消除这是题目明确要求的。在数组法中这意味着在统计结果项数或输出时要跳过系数为零的位置。在链表或映射法中意味着在系数相加为零时要删除该节点或条目。务必注意两个多项式输入时保证系数非零但相加后可能产生零这是一个必须处理的边界条件。输出格式这是OJOnline Judge题目常见的严格之处。通常要求先输出结果中的非零项个数K。随后输出K行或在一行内以空格分隔每行按“指数 系数”的格式。指数必须按降序排列。系数保留小数点后1位例如用printf(“%.1f”)。这里必须注意浮点数的精度问题虽然本题数据通常不会涉及极端精度但使用double类型并遵循格式化输出是良好习惯。零多项式这是一个极端但重要的边界情况。如果两个多项式完全抵消结果为零多项式。此时输出的项数K应为0。在数组法中遍历完整个数组都找不到非零系数在链表/映射法中结果容器为空。之后通常不需要再输出任何系数指数对或者有些题目要求输出一个空行。务必仔细阅读题目输出说明。3. 三种实现方案的代码级拆解与对比理解了原理我们来看代码。我将分别用数组、链表和映射C实现并分析各自的优劣。假设题目输入格式为每个多项式第一行是一个整数K表示该多项式的非零项数随后K行每行给出一个指数和系数。3.1 方案一数组法静态数组这是最推荐在限时编程中使用的方案尤其是当指数范围已知时。#include cstdio const int MAX_EXP 1001; // 假设最大指数为1000 double poly[MAX_EXP] {0}; // 数组初始化下标为指数值为系数 int main() { int k, exp; double coef; // 读取第一个多项式 scanf(%d, k); for (int i 0; i k; i) { scanf(%d %lf, exp, coef); poly[exp] coef; // 直接加到对应位置 } // 读取第二个多项式 scanf(%d, k); for (int i 0; i k; i) { scanf(%d %lf, exp, coef); poly[exp] coef; // 继续累加 } // 统计非零项个数 int count 0; for (int i 0; i MAX_EXP; i) { if (poly[i] ! 0.0) { // 注意浮点数比较通常与0比较是安全的 count; } } // 输出 printf(%d, count); // 注意题目要求降序输出所以从最高指数向低遍历 for (int i MAX_EXP - 1; i 0; i--) { if (poly[i] ! 0.0) { printf( %d %.1f, i, poly[i]); // 格式空格分隔系数1位小数 } } // 如果count为0这里就只输出了一个0符合要求 return 0; }为什么这样设计空间换时间简化逻辑我们牺牲了最多1001个double的空间约8KB换来了极致简单的逻辑。相加操作就是简单的数组累加O(1)复杂度。规避排序因为数组下标天然有序输出时从高到低遍历即可完全不需要排序操作。易于处理零项统计和输出时用一个if判断跳过零系数即可。输入顺序无关无论输入的多项式项是否有序都不影响结果正确性。实测心得在PAT等OJ上这种方法的代码行数最少运行速度最快几乎不会超时。浮点数比较poly[i] ! 0.0在本题场景下是安全的因为数据是精确的。但在更一般的数值计算中判断浮点数是否为零应使用fabs(poly[i]) 1e-8之类的精度容差。一定要看清指数范围。如果题目说指数是0~1000那么数组大小至少为1001。如果指数可能为负则需要进行偏移例如poly[exp 1000]或者改用其他方法。3.2 方案二有序链表法这种方法更贴近数据结构教学能锻炼指针操作能力适用于指数范围未知或很大的情况。#include cstdio #include algorithm // 用于sort如果输入无序则需先排序 struct Node { int exp; double coef; Node* next; Node(int e, double c) : exp(e), coef(c), next(nullptr) {} }; // 向有序降序链表中插入一项如果指数已存在则合并系数为零则删除 Node* insertOrAdd(Node* head, int exp, double coef) { if (coef 0.0) return head; // 系数为零直接忽略 Node dummy(-1, 0.0); // 哑节点简化头节点插入处理 dummy.next head; Node* prev dummy; Node* curr head; // 寻找插入位置找到第一个指数小于等于当前指数的节点 while (curr ! nullptr curr-exp exp) { prev curr; curr curr-next; } if (curr ! nullptr curr-exp exp) { // 指数相同合并系数 curr-coef coef; if (curr-coef 0.0) { // 系数抵消删除该节点 prev-next curr-next; delete curr; } } else { // 指数不同创建新节点插入到prev和curr之间 Node* newNode new Node(exp, coef); newNode-next curr; prev-next newNode; } return dummy.next; // 返回新的头节点 } int main() { Node* resultHead nullptr; int k, exp; double coef; // 处理两个多项式 for (int polyNum 0; polyNum 2; polyNum) { scanf(%d, k); for (int i 0; i k; i) { scanf(%d %lf, exp, coef); resultHead insertOrAdd(resultHead, exp, coef); } } // 统计并输出 int count 0; Node* p resultHead; while (p ! nullptr) { count; p p-next; } printf(%d, count); p resultHead; while (p ! nullptr) { printf( %d %.1f, p-exp, p-coef); p p-next; } // 释放内存在实际OJ中可省略但好习惯 while (resultHead ! nullptr) { Node* temp resultHead; resultHead resultHead-next; delete temp; } return 0; }为什么这样设计动态空间只为非零项分配空间在多项式非常稀疏时比数组法更省内存。在线处理insertOrAdd函数保证了链表始终有序可以边读入边合并无需等待所有输入完毕再排序。通用性强不依赖固定的指数范围。踩坑点指针操作易错特别是处理头节点插入、节点删除时使用哑节点dummy node可以极大简化逻辑避免对头节点的特殊判断。内存管理在OJ环境中程序结束操作系统会回收内存所以不delete也可以。但在实际工程或养成好习惯的角度应该释放。注意如果题目时间极端苛刻频繁的new/delete可能成为性能瓶颈。输入有序假设上面的insertOrAdd假设每次插入都可能在任意位置。如果题目保证输入的多项式项是按指数降序给出的那么合并算法可以进一步优化为类似合并有序链表的O(MN)算法而无需在插入时查找位置。但通常OJ不保证这一点所以上述通用插入法更稳妥。3.3 方案三映射法使用 std::map利用C STL的map代码可以非常简洁。#include cstdio #include map #include algorithm // 用于reverse_iterator using namespace std; int main() { mapint, double, greaterint polyMap; // greaterint使map按key降序排列 int k, exp; double coef; for (int polyNum 0; polyNum 2; polyNum) { scanf(%d, k); for (int i 0; i k; i) { scanf(%d %lf, exp, coef); polyMap[exp] coef; // 如果相加后系数为零需要删除该项 if (polyMap[exp] 0.0) { polyMap.erase(exp); } } } // 输出 printf(%d, (int)polyMap.size()); for (auto it polyMap.begin(); it ! polyMap.end(); it) { printf( %d %.1f, it-first, it-second); } return 0; }为什么这样设计代码极度简洁map自动处理了键的排序和唯一性我们只需要关心系数的累加和归零删除。表达直观polyMap[exp] coef;这行代码几乎就是数学定义的直接翻译。灵活通过自定义比较器greaterint轻松实现降序输出无需反转。性能考量每次polyMap[exp]操作如果exp不存在会先插入一个默认构造的值0.0然后返回引用进行加法。这比数组的直接寻址慢但代码更清晰。对于项数N插入和查找的时间复杂度是O(log N)。对于本题规模完全足够。需要注意在系数累加为零后必须手动erase该项否则它会作为一个系数为零的项留在map中影响后续计数和输出。这是使用map时的一个关键细节。4. 举一反三多项式运算的扩展与应用解决了加法我们很自然地会想到其他运算减法、乘法、求导、积分甚至是求值。这些运算的核心依然离不开我们之前讨论的数据表示和核心算法。4.1 多项式乘法乘法比加法复杂。多项式A乘以B结果是A的每一项与B的每一项相乘系数相乘指数相加然后将所有乘积项合并同类项。数组法实现乘法如果指数范围有限如0~1000两个多项式相乘结果的指数范围会扩大0~2000。我们可以用一个两倍大小的结果数组result_coef[2001]。两层循环遍历两个多项式的非零项进行乘积累加result_coef[i j] a_coef[i] * b_coef[j]。最后遍历结果数组输出非零项。时间复杂度O(M*N)对于指数范围K则是O(K^2)。在K1000时百万级操作也是瞬间完成。链表/映射法实现乘法需要双重循环生成所有乘积项存入一个临时容器如mapint, double在插入时合并同类项。最后输出该容器。代码比数组法稍复杂但原理相同。4.2 多项式求值与霍纳法则给定多项式P(x) a_n*x^n a_{n-1}*x^{n-1} ... a_1*x a_0和一个值x0求P(x0)。 最笨的方法是计算每一项a_i * pow(x0, i)然后求和需要多次计算幂效率低。霍纳法则Horner‘s Rule提供了高效的方法P(x0) (...((a_n * x0 a_{n-1}) * x0 a_{n-2}) * x0 ... a_1) * x0 a_0。 从最高次项开始依次乘x0并加上低一次项的系数。只需要n次乘法和n次加法。// 假设系数存储在数组coef中coef[i]对应x^i的系数且已知最高次项为n double horner(double coef[], int n, double x0) { double result coef[n]; for (int i n - 1; i 0; i--) { result result * x0 coef[i]; } return result; }如果多项式是用链表降序存储的遍历链表执行同样的累加过程即可。4.3 工程中的应用场景你以为多项式运算只存在于教科书和编程题中吗远非如此。计算机图形学贝塞尔曲线、B样条曲线的参数方程就是多项式或有理多项式。曲线的绘制、求交、分割等操作底层都在进行多项式运算。数值分析多项式插值拉格朗日插值、牛顿插值、多项式拟合最小二乘法是逼近复杂函数、进行数据分析的基础工具。密码学与编码理论某些加密算法和纠错码如Reed-Solomon码的运算是在有限域上的多项式环中进行的。符号计算系统如Mathematica、Maple其核心功能之一就是进行符号化的多项式运算因式分解、展开、求最大公因式等。所以熟练掌握多项式的表示和基本运算是通向这些更高级领域的一块坚实的垫脚石。下次你再看到“AB for Polynomials”希望你能意识到它不是一个简单的加法题而是一个关于如何优雅、高效地表示和操作结构化数据的经典案例。从数组的暴力美学到链表的精细操作再到映射的抽象简洁不同的实现反映了你对问题不同层面的理解和权衡。这才是编程真正有趣的地方。