202504272117 1009 Product of Polynomials

PTA | 程序设计类实验辅助教学平台

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 $N_1$ $a_{N_1}$ $N_2$ $a_{N_2}$ … $N_K$ $a_{N_K}$

where K is the number of nonzero terms in the polynomial, $N_i$ and $a_{N_i}$ (i=1,2,⋯,K) are the exponents and coefficients, respectively. It is given that 1≤K≤10, 0≤$N_K$<⋯<$N_2$<$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

Solve

和 202504231438 1002 A+B for Polynomials 都是多项式相关的模拟题。

本题是模拟多项式相乘，我们可以使用hash表存取指数和系数，读入第一个多项式后，第二个多项式边读边与第一个多项式相乘并存入新的 hash 表作为结果。

同样，也要处理系数相乘为0的结果。

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
 
int main() {
 
    map<int, double> polynomial;
    int k;
    cin >> k;
    while(k--) {
        int exp;
        double coef;
        cin >> exp >> coef;
        polynomial[exp] += coef;
    }
 
    map<int, double, greater<int>> newPolynomial;
    cin >> k;
    while(k--) {
        int exp;
        double coef;
        cin >> exp >> coef;
 
        for(auto pair : polynomial)
            newPolynomial[exp + pair.first] += coef * pair.second;
        
    }
 
    // 移除系数为0的项
    for(auto it = newPolynomial.begin(); it != newPolynomial.end();) {
        if(it->second == 0) {
            it = result.erase(it);
        } else {
            ++it;
        }
    }
 
    cout << newPolynomial.size();
    for_each(newPolynomial.begin(), newPolynomial.end(), [](const auto& pair) {
        // cout << " " << pair.first << " " << setPrecision(1) << pair.second;
        printf(" %d %.1f", pair.first, pair.second);
    });
    cout << endl;
	return 0;
}