PTA(Advanced Level)1009.Product of Polynomials

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

Input Specification:

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 ... *N**K* aNK

where K is the number of nonzero terms in the polynomial, *N**i* and aNi (i=1,2,⋯,K) are the exponents and coefficients, respectively. It is given that 1≤K≤10, 0≤*N**K<⋯<N2<N*1≤1000.

Output Specification:

For each test case you should output the product 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 up to 1 decimal place.

Sample Input:

2 1 2.4 0 3.2
2 2 1.5 1 0.5

Sample Output:

3 3 3.6 2 6.0 1 1.6

思路

• 多项式相乘，就是逐项展开乘即可，所以我们需要分别记录两个多项式的系数，指数，然后手动模拟展开即可。

代码

#include<bits/stdc++.h>
using namespace std;
struct node
{
    double a;
    int n;
    node(){}
    node(double _a, int _n): a(_a), n(_n){}
};//a*x^n
vector<node> v1;
vector<node> v2;   //分别用来记录里2个多项式
double a[2010] = {0};

int main()
{
    int k;

    cin >> k;
    int id;
    double tmp;
    while(k--)
    {
        cin >> id >> tmp;
        v1.push_back(node(tmp, id));
    }
    cin >> k;
    while(k--)
    {
        cin >> id >> tmp;
        v2.push_back(node(tmp, id));
    }
    double ans = 0.0;
    int index = 0;
    int base = 0;
    for(int i=0;i<v1.size();i++)
    {
        for(int j=0;j<v2.size();j++)
        {
            ans = v1[i].a * v2[j].a;
            index = v1[i].n + v2[j].n;  //系数相乘，指数相加
            //printf("ans:%d index:%d\n", ans, index);
            a[index] += ans;
        }
    }  //逐项展开的过程
    int cnt = 0;
    for(int i=0;i<2010;i++)
    {
        if(a[i] != 0)
            cnt++;
    }
    cout << cnt;
    for(int i=2009;i>=0;i--)
    {
        if(a[i] != 0)
            printf(" %d %.1f", i, a[i]);
    }
    return 0;
}

引用

https://pintia.cn/problem-sets/994805342720868352/problems/994805509540921344