比较好的解法
解题思路：使用两个double类型的数组，第一个数组保存第一个多项式，第二个数组用来输出多项式相乘的结果，逻辑比较简单，需要注意的是相乘后指数相加极值为2000，所以第二个数组要乘以2！
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
| #include <cstdio>
#include <cstring>
const int maxn=1010;
double poly1[maxn];
double poly2[maxn*2];
int main(){
int n,e;
double c;
memset(poly1,0,sizeof(poly1));
memset(poly2,0,sizeof(poly2));
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%lf",&e,&c);
poly1[e]=c;
}
scanf("%d",&n);
double c1;
int e1;
for(int i=0;i<n;i++){
scanf("%d%lf",&e,&c);
for(int j=0;j<=1000;j++){
if(poly1[j]!=0){
e1=j+e;
c1=poly1[j]*c;
if(c1!=0){
poly2[e1]+=c1;
}
}
}
}
int cnt=0;
for(int i=2*maxn;i>=0;i--){
if(poly2[i]!=0){
cnt++;
}
}
printf("%d",cnt);
for(int i=2*maxn;i>=0;i--){
if(poly2[i]!=0){
printf(" %d %.1f",i,poly2[i]);
}
}
return 0;
}
|
可能出现系数为0的情况（题目对系数的输入没有限制），需将其排除在外，否则测试点0无法通过。
最后一个测试点不通过！
1
2
| 2 1 0 0 3.2
2 2 1.5 1 0.5
|
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
62
| #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 2100;
struct Poly {
int n;
float c;
};
Poly p1[maxn];
Poly p2[maxn];
vector<Poly> p3;
bool cmp(Poly a,Poly b) {
return a.n > b.n;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n;i++) {
cin >> p1[i].n >> p1[i].c;
}
cin >> n;
for (int i = 0; i < n; i++) {
cin >> p2[i].n >> p2[i].c;
}
Poly p;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
p.n = p1[i].n + p2[j].n;
p.c = p1[i].c * p2[j].c;
int len = p3.size();
bool putIn = false;
for (int k = 0; k < len;k++) {
if (p.n==p3[k].n) {
putIn = true;
p3[k].c += p.c;
}
}
if (!putIn) {
p3.push_back(p);
}
}
}
int l = p3.size();
for (int i = 0; i < l; i++) {
if (p3[i].c == 0) {
l--;
}
}
cout << l;
sort(p3.begin(),p3.end(),cmp);
for (int i = 0; i < p3.size();i++) {
if (p3[i].c == 0) continue;
printf(" %d %.1f", p3[i].n, p3[i].c);
}
cout << endl;
return 0;
}
|
AC解法
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
62
| #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 2100;
struct Poly {
int n;
float c;
};
Poly p1[maxn];
Poly p2[maxn];
vector<Poly> p3;
bool cmp(Poly a, Poly b) {
return a.n > b.n;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> p1[i].n >> p1[i].c;
}
cin >> n;
for (int i = 0; i < n; i++) {
cin >> p2[i].n >> p2[i].c;
}
Poly p;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
p.n = p1[i].n + p2[j].n;
p.c = p1[i].c * p2[j].c;
if (p.c == 0) continue;
int len = p3.size();
bool putIn = false;
for (int k = 0; k < len; k++) {
if (p.n == p3[k].n) {
putIn = true;
p3[k].c += p.c;
}
}
if (!putIn) {
p3.push_back(p);
}
}
}
int l = p3.size();
for (int i = 0; i < l; i++) {
if (p3[i].c == 0) {
l--;
}
}
cout << l;
sort(p3.begin(), p3.end(), cmp);
for (int i = 0; i < p3.size(); i++) {
if (p3[i].c == 0) continue;
printf(" %d %.1f", p3[i].n, p3[i].c);
}
cout << endl;
return 0;
}
|
AC解法更新
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
62
63
64
| #include <iostream>
#include <vector>
#include <algorithm>
#define Len(arr) sizeof(arr)/sizeof(arr[0])
using namespace std;
const int maxn = 2100;
struct Poly {
int n;
float c;
};
Poly p1[maxn];
Poly p2[maxn];
vector<Poly> p3;
bool cmp(Poly a, Poly b) {
return a.n > b.n;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> p1[i].n >> p1[i].c;
}
cin >> n;
for (int i = 0; i < n; i++) {
cin >> p2[i].n >> p2[i].c;
}
Poly p;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
p.n = p1[i].n + p2[j].n;
p.c = p1[i].c * p2[j].c;
int len = p3.size();
bool putIn = false;
for (int k = 0; k < len; k++) {
if (p.n == p3[k].n) {
putIn = true;
p3[k].c += p.c;
}
}
if (!putIn) {
p3.push_back(p);
}
}
}
int l = p3.size();
for (int i = 0; i <p3.size(); i++) {
if (p3[i].c == 0) {
l--;
}
}
cout << l;
sort(p3.begin(), p3.end(), cmp);
for (int i = 0; i < p3.size(); i++) {
if (p3[i].c == 0) continue;
printf(" %d %.1f", p3[i].n, p3[i].c);
}
cout << endl;
return 0;
}
|
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
| #include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
int main() {
map<int, double> mmap;
int k1, k2;
cin >> k1;
vector<int> exp(k1);
vector<double> coef(k1);
for (int i = 0; i < k1; i++) {
cin >> exp[i] >> coef[i];
}
cin >> k2;
for (int i = 0; i < k2; i++) {
int tempExp;
double tempCoef;
cin >> tempExp >> tempCoef;
for (int j = 0; j < k1;j++) {
int newExp = tempExp + exp[j];
mmap[newExp] += (tempCoef*coef[j]);
if (mmap[newExp] == 0) {
mmap.erase(newExp);
}
}
}
cout << mmap.size();
auto it = mmap.rbegin();
for (; it != mmap.rend(); ++it) {
printf(" %d %.1f", it->first, it->second);
}
return 0;
}
|