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 aN1 N2 aN2 … NK aNK, 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
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
struct t {
int z;
double x;
};
t cheng(t t1, t t2) {
t temp;
temp.z = t1.z + t2.z;
temp.x = t1.x*t2.x;
return temp;
}
bool cmp(t a, t b) {
return a.z > b.z;
}
int main() {
#ifdef LOCAL
freopen("d:\\datain.txt", "r", stdin);
#endif LOCAL
int n;
scanf("%d", &n);
vector<t> a, b;
t t1;
for (int i = 0; i < n; i++) {
scanf("%d%lf", &t1.z, &t1.x);
a.push_back(t1);
}
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d%lf", &t1.z, &t1.x);
b.push_back(t1);
}
int n1 = a.size();
int n2 = b.size();
vector<t> ans;
t temp;
for (int i = 0; i < n1; i++) {
for (int j = 0; j < n2; j++) {
temp = cheng(a[i], b[j]);
//cout << temp.z << " " << temp.x << endl;
//cout << temp.z << endl;
bool is = false;
for (int k = 0; k < ans.size(); k++) {
if (temp.z == ans[k].z) {
ans[k].x += temp.x;
is = true;
break;
}
}
if(!is)
ans.push_back(temp);
}
}
for (auto it = ans.begin(); it != ans.end();) {
if ((*it).x == 0) {
it=ans.erase(it);
}
else
++it;
}
sort(ans.begin(), ans.end(), cmp);
printf("%d", ans.size());
for (int i = 0; i < ans.size(); i++) {
printf(" %d %.1lf", ans[i].z, ans[i].x);
}
return 0;
}
更加简洁
#include <cstdio>
using namespace std;
int main() {
int n1, n2, a, cnt = 0;
scanf("%d", &n1);
double b, arr[1001] = {0.0}, ans[2001] = {0.0};
for(int i = 0; i < n1; i++) {
scanf("%d %lf", &a, &b);
arr[a] = b;
}
scanf("%d", &n2);
for(int i = 0; i < n2; i++) {
scanf("%d %lf", &a, &b);
for(int j = 0; j < 1001; j++)
ans[j + a] += arr[j] * b;
}
for(int i = 2000; i >= 0; i--)
if(ans[i] != 0.0) cnt++;
printf("%d", cnt);
for(int i = 2000; i >= 0; i--)
if(ans[i] != 0.0)
printf(" %d %.1f", i, ans[i]);
return 0;
}