1002 A+B for Polynomials （25 分)

This time, you are supposed to find A+BA+BA+B where AAA and BBB 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:

KKK N1N_1N​1​​ aN1a_{N_1}a​N​1​​​​ N2N_2N​2​​ aN2a_{N_2}a​N​2​​​​ ... NKN_KN​K​​ aNKa_{N_K}a​N​K​​​​

where KKK is the number of nonzero terms in the polynomial, NiN_iN​i​​ and aNia_{N_i}a​N​i​​​​ (i=1,2,⋯,Ki=1, 2, \cdots , Ki=1,2,⋯,K) are the exponents and coefficients, respectively. It is given that 1≤K≤101 \le K \le 101≤K≤10，0≤NK<⋯<N2<N1≤10000 \le N_K < \cdots < N_2 < N_1 \le 10000≤N​K​​<⋯<N​2​​<N​1​​≤1000.

Output Specification:

For each test case you should output the sum of AAA and BBB 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 to 1 decimal place.

Sample Input:

2 1 2.4 0 3.2
2 2 1.5 1 0.5

Sample Output:

3 2 1.5 1 2.9 0 3.2

给两个多项式，分别求其相加的结果。输入格式：K表示该多项式的项数，N表示幂，ai表示多项式的系数

思路：水题，细节很重要，注意保留1位小数；然后系数为0的项要忽略，无论是相加后为0还是输入时就为0都不应该输出。其实这题桶排好一点，贴上打了n个补丁的代码。噢对，如果幂不是整数的话要使用map，这题系数为整数。

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, double > T;
T l1[20], l2[20];
int K1, K2;
vector<T> tab;
int vis1[1001], vis2[1001];

bool MyCompare (T a, T b) {
  return a.first > b.first;
}

int main() {
  memset(vis1, -1, sizeof(vis1));
  memset(vis2, -1, sizeof(vis2));
  cin >> K1;
  for (int i = 0; i < K1; i++) {
    cin >> l1[i].first >> l1[i].second;
    if (vis1[l1[i].first] != -1) {
      l1[vis1[l1[i].first]].second += l1[i].second;
      i--;
      K1--;
    } else {
      vis1[l1[i].first] = i;
    }
  }
  cin >> K2;
  for (int i = 0; i < K2; i++) {
    cin >> l2[i].first >> l2[i].second;
    if (vis2[l2[i].first] != -1) {
      l2[vis2[l2[i].first]].second += l2[i].second;
      i--;
      K2--;
    } else {
      vis2[l2[i].first] = i;
    }
  }
  sort(l1, l1 + K1, MyCompare);
  sort(l2, l2 + K2, MyCompare);
  int i = 0, j = 0;
  while (i < K1 && j < K2) {
    if (l1[i].second == 0) {
      i++;
      continue;
    }
    if (l2[j].second == 0) {
      j++;
      continue;
    }
    if (l1[i].first == l2[j].first) {
      if (l1[i].second + l2[j].second != 0) {
        tab.push_back(make_pair(l1[i].first, l1[i].second + l2[j].second));
      }
      i++;
      j++;
    } else if (l1[i].first > l2[j].first) {
      tab.push_back(make_pair(l1[i].first, l1[i].second));
      i++;
    } else {
      tab.push_back(make_pair(l2[j].first, l2[j].second));
      j++;
    }
  }
  for (; i < K1; i++) {
    tab.push_back(make_pair(l1[i].first, l1[i].second));
  }
  for (; j < K2; j++) {
    tab.push_back(make_pair(l2[j].first, l2[j].second));
  }
  cout << tab.size();
  for (vector<T>::iterator it = tab.begin(); it != tab.end(); it++) {
    cout << " " << it->first << " " << setiosflags(ios::fixed) << setprecision(1) << it->second;
  }
  cout << endl;
  return 0;
}