1002. A+B for Polynomials (25)

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 a_N1 N2 a_N2 ... NK a_NK, where K is the number of nonzero terms in the polynomial, Ni and a_Ni (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 Input

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

/* 这题多项式指数为0~1000 所以可以考虑数组进行存储。下标为指数
    数组值为系数。
*/
#include "iostream"
using namespace std;
int main() {
    float a[1002] = { 0 };
    float b[1002] = { 0 };
    int n, t;
    cin >> n;
    int exp;
    float coef;
    while (n--) {
        cin >> exp >> coef;
        a[exp] = coef;
    }
    cin >> t;
    while (t--) {
        cin >> exp >> coef;
        b[exp] = coef;
    }
    int cnt = 0;
    for (int i = 0; i <= 1000; i++) {
        a[i] = a[i] + b[i];
        if (a[i] != 0)
            cnt++;
    }
    cout << cnt;
    for (int i = 1000; i >= 0; i--)
        if (a[i] != 0)
            printf(" %d %.1f",i,a[i]);
    cout << endl;
    return 0;
}

/*
   多项式加法。用链表进行存储指数和系数。
*/
#include "iostream"
using namespace std;
struct Node {
    int exp;
    float coef;
    Node* next;
};
typedef Node* ptrToNode;
typedef ptrToNode* List; /* 指向指针的指针 */
int len = 0;
void attach(List l,int exp, float coef) {
    ptrToNode p = (ptrToNode)malloc(sizeof(Node));
    p->exp = exp;
    p->coef = coef;
    p->next = NULL;
    (*l)->next = p;
    (*l) = (*l)->next;
}
ptrToNode ReadPoly() {
    ptrToNode l = (ptrToNode)malloc(sizeof(Node));
    ptrToNode rear = l;
    l->next = NULL;
    int n;
    cin >> n;
    while (n--) {
        int exp;
        float coef;
        cin >> exp >> coef;
        attach(&rear, exp, coef);
    }
    ptrToNode p = l;
    l = l->next;
    free(p);
    return l;
}
int compare(int a,int b) {
    if (a < b)
        return -1;
    if (a == b)
        return 0;
    if (a > b)
        return 1;
}
ptrToNode addPoly(ptrToNode l1,ptrToNode l2) {
    ptrToNode l = (ptrToNode)malloc(sizeof(Node));
    l->next = NULL;
    ptrToNode rear = l;
    while (l1 != NULL && l2 != NULL) {
        switch (compare(l1->exp,l2->exp)) {
        case -1: attach(&rear, l2->exp, l2->coef); l2 = l2->next; len++; break;
        case 1: attach(&rear, l1->exp, l1->coef); l1 = l1->next; len++; break;
        case 0: 
            if (l1->coef + l2->coef != 0) { attach(&rear, l1->exp, l1->coef + l2->coef); len++; }
            l1 = l1->next; l2 = l2->next;  break;
        }
    }
    while (l1 != NULL) { attach(&rear, l1->exp, l1->coef); l1 = l1->next; len++; }
    while (l2 != NULL) { attach(&rear, l2->exp, l2->coef); l2 = l2->next; len++; }
    ptrToNode p = l;
    l = l->next;
    free(p);
    return l;
}
void disp(ptrToNode p) {
    while (p != NULL) {
        printf( " %d %.1f",p->exp,p->coef);
        p = p->next;
    }
}
int main() {
    ptrToNode l1 = ReadPoly();
    ptrToNode l2 = ReadPoly();
    ptrToNode p = addPoly(l1, l2);
    cout << len;
    disp(p);
    cout << endl;
    return 0;
}