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:

where K is the number of nonzero terms in the polynomial, Ni and aNi(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

Solution:

Polynomials是多项式的意思.
每个case给出两行,

2 1 2.4 0 3.2     // 2.4*X^1 + 3.2*X^0
2 2 1.5 1 0.5     // 1.5*X^2 + 0.5*X^1

A*B的结果就是

3 3 3.6 2 6.0 1 1.6    // 3.6*X^3 + 6.0*X^2 + 1.6*X^1

总的相乘的结果是, 对应项相乘后相加的结果。
对应项相乘, 指数相加, 系数相乘; 如果相乘后的指数已经存在, 该指数对应的总系数要加上这次相乘的系数.

将A和B放在两个map里, 多对多的去相乘。

第一个问题:
相乘后的结果以何种形式保存？

如果放在map中, 可能不满足从指数从大到小排列的顺序, 只能通过一个case.

于是, 用map+vector, 建立一个Node保存计算后的指数n和系数a, 再把node放进vector中排序.

坑点:
若系数a为0的情况, 应该不会被打印。主要a的类型是double, 比较db与0之间的关系。否则会导致case1通不过.s

if ( -0.00005 <= db - 0.0 && db-0.0 <= 0.000005) {    // db == 0
    // ..
}

if (db - 0.0 < -0.00005 || db-0.0 > 0.000005) {       // db != 0
    // ..
}

实际代码如下:

#include <cstdio>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

struct Node {
  int n;
  double a;
};

bool cmp(Node n1, Node n2) {
  return n1.n > n2.n;
}

int main() {
  unordered_map<int, double> poly1, poly2, ans;
  vector<Node> v;
  int N, M;
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    int n; double a; scanf("%d %lf", &n, &a);
    auto it = poly1.find(n);
    if (it != poly1.end()) {
      it->second += a;
    } else {
      poly1[n] = a;
    }
  }
  scanf("%d", &M);
  for (int i = 0; i < M; i++) {
    int n; double a; scanf("%d %lf", &n, &a);
    auto it = poly2.find(n);
    if (it != poly2.end()) {
      it->second += a;
    } else {
      poly2[n] = a;
    }
  }

  for (auto it1 = poly1.begin(); it1 != poly1.end(); it1++) {
    for (auto it2 = poly2.begin(); it2 != poly2.end(); it2++) {
      int n = it1->first + it2->first;
      double a = it1->second * it2->second;
      auto it_ans = ans.find(n);
      if (it_ans != ans.end()) {
        it_ans->second += a;
      } else {
        ans[n] = a;
      }
    }
  }
  for (auto it = ans.begin(); it != ans.end(); it++) {
    if (it->second-0.0 < -0.0005 || it->second-0.0 > 0.0005) {   // case1
      v.push_back(Node{it->first, it->second});
    }
  }
  sort(v.begin(), v.end(), cmp);
  printf("%lu", v.size());
  for (int i = 0; i < v.size(); i++) {
    printf(" %d %.1lf", v[i].n, v[i].a);
  }
  return 0;
}