pat

题目

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≤N_K<⋯<N_2<N_1≤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

1⃣️注意一下，直接在C[n+tn]处判断非零则加入set是错的，因为C[n+tn]的值还可能改变。


#include <vector>
#include <set>
using namespace std;
typedef vector<double> vd;
typedef vector<int> vi;
int (){
    int K1, K2, n, cnt = 0;
    double a;
    vd A(1001, 0.0), B(1001, 0.0), C(2001, 0.0);
    vi indexs;  set<int> res_index;
    scanf("%d", &K1);
    for(int i = 0;i < K1;i++){
        scanf("%d %lf", &n, &a);
        A[n] = a;
        indexs.push_back(n);
    }
    scanf("%d", &K2);
    for(int i = 0;i < K2;i++){
        scanf("%d %lf", &n, &a);
        B[n] = a;
        for(auto iter = indexs.begin(); iter != indexs.end(); iter++){
            int tn = iter;
            C[n + tn] += B[n]  A[tn];
            if(C[n + tn] != 0.0)
                res_index.insert(n + tn);
        }
    }
    for(auto iter = res_index.rbegin(); iter != res_index.rend(); iter++)
        if(C[iter] != 0.0)
            cnt++;
    printf("%d", cnt);
    for(auto iter = res_index.rbegin(); iter != res_index.rend(); iter++)
        if(C[iter] != 0.0)
            printf(" %d %.1f", iter, C[iter]);
    return 0;
}

近期文章

近期评论

标签

热门

文章归档

分类目录

功能