PAT(Advanced)甲級---1009 Product of Polynomials(25分)

1722 ワード
PAT甲級 データ構造
1009 Product of Polynomials (25分)
This time,you are supposed to find A×B where A and B artwo polynomials.
Input Specification:
Each input file contains one test case.Each case occupies 2 line,and each line contains the information of a polynomial:
K N 1 a N 1 N 2 a N 2 ... N K a N K
where K is the number of nonzers in the polynomial、 N i and a N i (i=1,2,⋯,K)are the exponents and coefficients,repectively.It is given that 1≦K≦10、 0≦N K
Output Specification:
For each test case you Shouuld output the product of A and B in one line,with the same format.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 1.5 1 0.5
Sample Output:
3 3.6 2 6.0 1 1.6
 
コード:
#include
#include
#include
#include
#include
#include
using namespace std;


map m1,m2;
int N, expo;
double cof;

int main(){
    int i = 0;
    while (i++ < 2){
        scanf("%d", &N);
        for (int j = 0; j < N;j++){
            scanf("%d%lf", &expo, &cof);
            if (i==1)m1[expo] = cof;
            else{
                for (auto it : m1){
                    m2[expo + it.first] += cof*it.second;
                }
            }
        }
    }
    int cnt=0;
    for(auto x:m2){
        if(x.second!=0)cnt++;
    }
    printf("%d", cnt);
    for (auto it = m2.rbegin(); it != m2.rend();it++){
        if(it->second!=0)printf(" %d %.1lf", it->first, it->second);
    }
}
注意:
  • 試験点1:係数が0の点は篩にかける必要があります.
    • スタックの方法はポーランドのサフィックス式に逆です.