1009 Product of Polynomials (25分)  

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​​​​ (,) are the exponents and coefficients, respectively. It is given that 1, 0.

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

 这道题很容易来思路，难度不大   做题一开始，发现多项式相乘需要两重for循环，一直在想有没有更好的解法，担心超时   写程序的时候，太节约内存了，然后出了一些莫名其妙的输出结果（inf inf。。。。），搞得我一脸懵逼   其实这题的 套路没有那么多，老老实实写就行了，没有必要太节约内存（最开始创建了一个数组）   不然出了莫名其妙的bug很难排查   而且把题目做出来才是最主要 1 #include<iostream>

 2 #include <cstdio>
 3 #include <malloc.h>
 4 #include <string.h>
 5 #include <vector>
 6 #include <math.h>
 7 
 8 using namespace std;
 9 
10 #define maxNum 1001
11 
12 int main()
13 {
14     double poly1[maxNum] = {0.0};
15     double poly2[maxNum] = {0.0};

　　　　//指数相加，可能会到1000，所以结果数组必须开两倍
16     double res[2*maxNum] = {0.0};
17 
18     int n;
19     cin>>n;
20     int exp;
21     float cof;
22     for(int i=0;i<n;i++){
23         cin>>exp>>cof;
24         poly1[exp] = cof;
25     }
26     cin>>n;
27     for(int i=0;i<n;i++){
28         cin>>exp>>cof;
29         poly2[exp] = cof;
30     }
31 
32     for(int i=0;i<maxNum;i++){
33         for(int j=0;j<maxNum;j++){
　　　　　　　　　　//合并指数相同的多项式的系数
34             res[i+j] += poly1[i]*poly2[j];
35         }
36     }
37 
38     int cnt=0;
39     for(int i=0;i<2*maxNum;i++){
40         if(res[i]!=0){
41             cnt++;
42         }
43     }
44     cout<<cnt;
45     for(int i=2*maxNum-1;i>=0;i--){
46         if(res[i]!=0){
47             printf(" %d %.1f",i,res[i]);
48         }
49     }
50 
51     return 0;
52 }