1009ProductofPolynomials模拟

1009 Product of Polynomials

#

0、题目

#

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≤NK<⋯<N2<N1≤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

1、大致题目

#

多项式相乘，求项数和系数

2、解题思路

#

多项式相乘，可能因为学过计组，感觉也就这么回事，特别是之前有一道 1002 A+B for Polynomials ，导致基本看不出啥难点。

3、AC代码

#

#include<iostream>
#include<map>
#include<cmath>
#include<iomanip>
using namespace std;
int K;
map<int,double,greater<int> >ma1,ma2,ma;
int a;
double b;

int main() {
	ma.clear();
	ma1.clear();
	ma2.clear();
	cin>>K;
	for(int i=0; i<K; i++) {
		cin>>a>>b;
		if(ma1.count(a)==0&&b!=0) {
			ma1[a]=b;
		} else {
			ma1[a]+=b;
		}
	}
	cin>>K;
	for(int i=0; i<K; i++) {
		cin>>a>>b;
		if(ma2.count(a)==0&&b!=0) {
			ma2[a]=b;
		} else {
			ma2[a]+=b;
		}
	}
	for(map<int,double>::iterator it1=ma1.begin(); (it1)!=ma1.end(); it1++) {
		for(map<int,double>::iterator it2=ma2.begin(); (it2)!=ma2.end(); it2++) {
			a=it1->first+it2->first;
			b=it1->second*it2->second;
			if(ma.count(a)==0&&b!=0) {
				ma[a]=b;
			} else {
				ma[a]+=b;
			}
		}
	}
	for(map<int,double>::iterator it=ma.begin(); (it)!=ma.end();) {
		if(it->second==0) {
			ma.erase(it++);
		} else {
			++it;
		}
	}
	if(ma.empty()) {
		cout<<0<<endl;
	} else {
		cout<<ma.size();
		for(map<int,double>::iterator it=ma.begin(); (it)!=ma.end(); it++) {
			cout<<" "<<it->first<<" "<<setiosflags(ios::fixed)<<setprecision(1)<<it->second;
		}
		cout<<endl;
	}
	return 0;
}