PAT-A 真题- 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 a_N1 N2 a_N2 ... NK a_NK, where K is the number of nonzero terms in the polynomial, Ni and a_Ni (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

这道题是一道很简单的多项式相乘的问题。如果考虑考试时候答题的效率，推荐直接将多项式保存到数组中，然后遍历数组相乘，存放到结果数组中。之后遍历结果数组，找到有几个非0的数据，这就是答案个数。再次遍历数组，输出这些非0的数据即可。

代码推荐柳婼小姐姐的：https://www.liuchuo.net/archives/2026

这应该是最不容易错，最方便的办法了。但是如果考虑效率和内存，推荐使用链表来做。但是链表更复杂一些，所以下面使用了vector。

如果使用vector来做，要特别注意对0的判断，下面是几组易错的数据：

//测试点0要注意可能有正负抵消的情况
1 3 2
1 3 -2
//测试点3和4如果段错误说明数组开小了。要2000以上
1 1000 1
1 1000 1
//测试点2出错，检查当只有一个数据的时候程序能否正常处理

使用vector的代码如下：（存放结果避免排序所以还是使用了一个数组）

#include <iostream>
#include <vector>
#define MAXN 2010
using namespace std;

typedef struct {
  double data;
  int exp;
} node;

void readData(vector<node>* array){
  int K;
  cin >> K;
  for(int i = 0 ; i < K ;i++){
    node tmp;
    cin >> tmp.exp >> tmp.data;
    array->push_back(tmp);
  }
}

int main(){
  vector<node> a, b;
  //读入第一个多项式
  readData(&a);
  //读入第二个多项式
  readData(&b);
  //遍历并计算结果
  double result[MAXN] = {0.0};
  int cnt = 0;
  for(int i = 0 ; i < a.size(); i++){
    for(int j = 0 ; j < b.size(); j++){
      int exp = a[i].exp + b[j].exp;
      double data = a[i].data * b[j].data;
      //如果这个位置不是0，并且将要加上的数也不是0，那么这就是另一个答案 
      if(result[exp] == 0 && data != 0.0) cnt++;
      //如果这个位置原本不是0，但是加上data后变成0了，那么就删掉这个答案
      else if(result[exp] != 0 && result[exp] + data == 0.0) cnt--;
      result[exp] += data;
    }
  }
  //遍历结果并输出
  printf("%d", cnt);  //输出个数 
  if(cnt != 0) printf(" ");  //输出个数后面的空格。cnt==0的时候不必输出 
  int out_cnt = 0;  //输出计数 
  for(int i = MAXN-1 ; i >= 0; i--){
    if(result[i] != 0.0){
      out_cnt++;
      printf("%d %.1f", i, result[i]);
      if(out_cnt == cnt) break;
      printf(" ");
    }
  }
  return 0;
}