1009 Product of Polynomials

0、题目

This time, you are supposed to find $A\times 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,\cdots ,K$) are the exponents and coefficients, respectively. It is given that $1\le K\le 10$, $0\le NK<\cdots <N2<N1\le 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
1
2

Sample Output:

3 3 3.6 2 6.0 1 1.6
1

1、大致题目

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

2、解题思路

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

3、AC代码

#include
#include
#include
#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61