题目翻译

1002: 多项式A和B的合并

输入格式

每个输入文件包含一个测试样例，每个样例占两行，每行存放着一个多项式的信息，格式如下：

KN₁a_N₁N₂a_N₂···N_Ka_{N_K}

其中K为多项式中的非零项数；N_i和a_N_i分别为各项的幂指数和系数。给定1≤K≤10，0≤N_K≤1000。

输出格式

对于每个测试样例，在一行中输出A和B的和，输出格式同输入格式相同。要格外注意在每行的末尾没有额外的空格。结果精确到小数点后一位。

样例

输入

1 2	2 1 2.4 0 3.2 2 2 1.5 1 0.5

输出

1	3 2 1.5 1 2.9 0 3.2

题目分析

首先要弄懂题目中的标准表示法的原理。以样例为例：第一行为A，A的第一个数字2表示有两项，1 2.4表示幂指数为1的项系数为2.4，0 3.2同理，可得A=2.4x¹+3.2x⁰=2.4x+3.2；同理B=1.5x²+0.5x。设C=A+B，C=1.5x²+2.9x+3.2=1.5x²+2.9x¹+3.2x⁰，用标准表示法为：3 2 1.5 1 2.9 0 3.2。排列顺序为从高次幂到低次幂。

要完成这一多项式合并的功能，只需借助一个数组来存储个多项式的系数即可。我们可以借助结构体来整合这个问题。每个多项式都是一个结构体poly，其成员有两个，一个int num代表结构体的项数，一个double coef[max]代表从0到max次幂的每一项的系数。然后我们实例化三个结构体A，B和SUM，分别将两个加项数据读入A和B，完成合并后存入SUM中，再以标准格式打印出来即可。

这里有两个注意事项：

一是，题目要求精确到一位小数，这个功能可以通过cout << setiosflags(ios::fixed) << setprecision(/* 这里填入你要保留到小数点后多少位 */) << /* 这里是你要输出的数据 */ ;实现。要使用这两个函数，必须在头文件中包含"iomanip"。

二是，对于合并后系数抵消的项，不计入项数，且不打印出来。这里只需要在打印函数中用if语句进行判断即可。

代码

#include "iostream"
#include "iomanip"
#define max_expo 1005
using namespace std;

struct poly{
    int num;
    double coef[max_expo];
};
// 初始化结构体
void init(poly &P){
    P.num = 0;
    for(int i=0; i<max_expo; ++i){
        P.coef[i] = 0;
    }
}
// 结构体数据的读入
void input(poly &P){
    cin >> P.num;
    int index = 0;
    for(int i=0; i<P.num; ++i){
        cin >> index;
        cin >> P.coef[index];
    }
}
// 合并函数
poly poly_add(poly A, poly B){
    poly SUM;
    init(SUM);
    for(int i=0; i<max_expo; ++i){
        SUM.coef[i] = A.coef[i] + B.coef[i];
        if(SUM.coef[i] != 0){
            SUM.num++;
        }
    }
    return SUM;
}
// 打印函数
void output(poly SUM){
    cout << SUM.num;
    for(int i=max_expo-1; i>=0; --i){
        if(SUM.coef[i] != 0){
            cout << " " << i << " " << setiosflags(ios::fixed) << setprecision(1) << SUM.coef[i];
        }
    }
}

int main(){
    poly A, B, SUM;
    init(A); init(B);
    input(A); input(B);
    SUM = poly_add(A, B);
    output(SUM);
    return 0;
}

踩坑指南

接下来喜闻乐见的踩坑环节。

首先是没有考虑0系数抵消的问题，在网上查阅了许多题解后才注意到这个问题。其次是在初始化函数中只初始化了数组，没有初始化num变量，导致程序在自己电脑上正常运行，但一直无法通过在线判题系统。声明变量一定要初始化，这又为我敲响了一次警钟。

最后是程序的优化过程，最初我使用了一个bool型数组来标记合并过程中出现了哪些项，从而可以只对有标记的项进行合并，虽然说时间上有微小的效率提升，但是对编程人员很不友好，弃之；此外，由于输入项中按降幂顺序给出整式，因此只需要用两个数记录两个加项的最高次幂，然后取其较大者作为循环边界，这样可以不用循环到max_expo处，不过这个优化由于跟上面相同的原因也未应用到本程序中。