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通不过.sif ( -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
// ..
}
实际代码如下:
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;
}