题目

This time, you are supposed to find A+B where A and B are two polynomials.

Input

Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: K N1 aN1 N2 aN2 ... NK aNK, where K is the number of nonzero terms in the polynomial, Ni and aNi (i=1, 2, ..., K) are the exponents and coefficients, respectively. It is given that 1 <= K <= 10，0 <= NK < ... < N2 < N1 <=1000.

Output

For each test case you should output the sum of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate to 1 decimal place.

Sample Output

2 1 2.4 0 3.2
2 2 1.5 1 0.5

Sample Output

3 2 1.5 1 2.9 0 3.2

题目大意

输出两个多项式相加后的多项式。
　　
思路

常规思路是分别用double数组来记录每一个多项式：数组的下标为指数，对应的值为系数（当然这只适用于正整数指数的情况）。当数组的值为0（即系数为0）时，表示多项式中不存在指数为该下标的项（用于判读是否输出）。将读入的两个多项式数组按对应下标相加，存入第三个数组中，即为目标多项式数组。
　　因第一次提交时有一个测试点未通过，一时想不到问题所在（后已修正），就对原有代码进行了改进：只创建一个目标多项式数组，每一次读入、相加都直接在该数组中进行。

代码实现—三数组版

#include <stdio.h>
#define maxSize 1001

struct poly_arr 
{
    double poly[maxSize];
    int max_index;          // 系数非零项的最大指数
    int count;              // 非零项个数
};

void init_poly(poly_arr &X)
{
    int i;
    X.max_index = 0;
    X.count = 0;
    for (i=0; i < maxSize; ++i)
        X.poly[i] = 0;
}

void insert_poly(poly_arr &X)
{
    int expo;
    double coef;
    scanf("%d %lf", &expo, &coef);
    X.poly[expo] = coef;
    ++X.count;
    if (X.max_index < expo)         // 更新多项式最大指数
        X.max_index = expo;
}

void add_poly(poly_arr A, poly_arr B, poly_arr &C)
{
    int i;
    int max;
    max = A.max_index > B.max_index ? A.max_index : B.max_index;
    for (i = 0; i <= max; ++i)
        if (A.poly[i] != 0.0 || B.poly[i] != 0.0)
        {
            C.poly[i] = A.poly[i] + B.poly[i];
            if (C.poly[i] != 0.0)   // 规范应该为fabs(x - 0.0) > 1e-8
            {
                ++C.count;
                C.max_index = i;    // 系数非零时才更新最大指数
            }
        }
}

void print_poly(poly_arr X)
{
    int i;
    printf("%d", X.count);
    for (i = X.max_index; i >= 0; --i)
        if (X.poly[i] != 0.0)
            printf(" %d %.1lf", i, X.poly[i]);
}

int main(void)
{
    poly_arr A, B, C;
    int k;
    int i; 
    init_poly(A);
    init_poly(B);
    init_poly(C);
    scanf("%d", &k);
    for (i = 0; i < k; ++i)
        insert_poly(A);
    scanf("%d", &k);
    for (i = 0; i < k; ++i)
        insert_poly(B);
    add_poly(A, B, C);
    print_poly(C);
}

代码实现—单数组版

#include <stdio.h>
#define maxSize 1001

struct poly
{
    double arr[maxSize];
    int count;
    int max_index;
};

void init_poly(poly &X)
{
    X.count = 0;
    X.max_index = 0;
    for (int i = 0;i < maxSize; ++i)
        X.arr[i] = 0;
}

void add_poly(poly &X)
{
    double coef;
    int expo;
    scanf("%d %lf", &expo, &coef);
    if (X.arr[expo] == 0.0)     // 原系数为零时项数+1
        ++X.count;
    X.arr[expo] = X.arr[expo] + coef;
    if (X.arr[expo] == 0.0)     // 相加后系数为零时项数-1
        --X.count;
    if (X.max_index < expo)     // 更新最大指数
        X.max_index = expo;
}

void print_poly(poly X)
{
    printf("%d", X. count);
    for (int i = X.max_index; i >= 0; --i)
        if (X.arr[i] != 0.0)
            printf(" %d %.1lf", i, X.arr[i]);
}

int main(void)
{
    int i, j, K;
    poly C;
    init_poly(C);
    for (i = 0; i < 2; ++i)
    {
        scanf("%d", &K);
        for (j=0; j<K; ++j)
            add_poly(C);
    }   
    print_poly(C);
}