题目描述

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 N1 a**N1 N2 a**N2 … N**K aNK

where K is the number of nonzero terms in the polynomial, N**i and aNi (i=1,2,⋯,K) are the exponents and coefficients, respectively. It is given that 1≤K≤10, 0≤N**K<⋯<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:

1
2
3
4
5
6
2 1 2.4 0 3.2
2 2 1.5 1 0.5



结尾无空行

Sample Output:

1
2
3
4
5
3 3 3.6 2 6.0 1 1.6



结尾无空行

思路

  1. 将第一个多项式的值乘以 第二个多项式中的所有的值
  2. 将多项式的次数 作为 key 放入 map 中

题解(一个测试用例没过，找不出来)

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
//
// Created by 张旭辉 on 2021/8/16.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <vector>
// 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
using namespace std;


int main() {
    int n, m;

    int key;
    float val;
    cin >> n;
    vector<float> A[n];
    for (int i = 0; i < n; i++) {
        cin >> key >> val;
        A[i].push_back(key);
        A[i].push_back(val);
    }
    cin >> m;
    vector<float> B[m];
    for (int i = 0; i < m; i++) {
        cin >> key >> val;
        B[i].push_back(key);
        B[i].push_back(val);
    }
    map<int, float> res;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int coefficient = A[i][0] + B[j][0];
            float value = A[i][1] * B[j][1];
            if (res.count(coefficient) == 0) {
                res.insert(pair<int, float>(coefficient, value));
            } else if (res.count(coefficient) == 1) {
                float temp = res[coefficient];
                res.erase(coefficient);
                res.insert(pair<int, float>(coefficient, value + temp));
            }

        }
    }

    map<int, float>::reverse_iterator iter;
    cout.precision(2);
    cout << res.size();
    for (iter = res.rbegin(); iter != res.rend(); iter++) {
        printf(" %d %.1f", iter->first, iter->second);
    }

    return 0;
}