PAT 甲级测试题目 -- 1009 Product of Polynomials

题目链接

坑点：注意系数可能为负数！！只有测试点 0 过不去可能就是因为这个！！！

我最初在做这道题的时候用了两种思路，一种将保存结果的数组初始化为 0，把乘积加上去，顺便记录下最后一个指数的值。用两次 2000 次 for 循环过滤掉 0 值以及输出答案，这个代码过了，但是后期测试的时候，有些测试用例会多出来空格，有些则格式不对。。但是过了。。。
代码如下

#include<iostream>
#include<stdio.h>
using namespace std;
int main() {
	double A[1001], B[1001];
	int ExpA[11], ExpB[11];
	double Result[2001];
	double coe;
	int Acounts, Bcounts, exp, EndIndex = 0;

	// 初始化多项式


	for (int i = 0; i < 1001; i++) {
		A[i] = B[i] = 0;
	}
	for (int i = 0; i < 2001; i++) {
		Result[i] = 0;
	}

	cin >> Acounts;
	for (int i = 0; i < Acounts; i++) {
		cin >> exp >> coe;
		ExpA[i] = exp;
		A[exp] = coe;
	}
	cin >> Bcounts;
	for (int i = 0; i < Bcounts; i++) {
		cin >> exp >> coe;
		ExpB[i] = exp;
		B[exp] = coe;
	}

	for (int i = 0; i < Acounts; i++) {
		for (int j = 0; j < Bcounts; j++) {
			//cout << "=====================" << endl;
			//cout << "Result[ExpA[i] + ExpB[j]] = " << Result[ExpA[i] + ExpB[j]] << endl;
			Result[ExpA[i] + ExpB[j]] += A[ExpA[i]] * B[ExpB[j]];
			//cout << "A[ExpA[i]] * B[ExpB[j]] = " << A[ExpA[i]] * B[ExpB[j]] << endl;
			//cout << "Result[ExpA[i] + ExpB[j]] = " << Result[ExpA[i] + ExpB[j]] << endl;
			//cout << "=====================" << endl;
			EndIndex = ExpA[i] + ExpB[j];
		}
	}

	int AllResCount = 0;

	for (int i = 2000; i >= 0; i--) {
		if (Result[i] != 0) {
			AllResCount++;
		}

	}

	cout << AllResCount << " ";
	for (int i = 2000; i >= 0; i--) {
		if (Result[i] != 0) {
			printf("%d %.1f", i, Result[i]);
			if (i != EndIndex)
				cout << " ";

		}

	}

	return 0;
}

另外一种思路是将保存结果的数组初始化为 -1 ，边计算多项式边记录非零多项式的项数，最后输出答案，测试点 0 答案错误。。。我百度了好久，好多帖子指出是跟系数为 0 有关，我自己做了几个系数为 0 测试用例，测试结果和我在纸上计算的答案一致，包括格式也正确，我实在弄不懂了。。。代码如下：

#include<iostream>
#include<stdio.h>
using namespace std;
int main() {
	double A[1001], B[1001];
	int ExpA[11], ExpB[11], ItemIndex[10];
	double Result[2001];
	double coe;
	int Acounts, Bcounts, exp, ResCounts = 0;

	// 初始化多项式


	for (int i = 0; i < 1001; i++) {
		A[i] = B[i] = -1;
	}
	for (int i = 0; i < 2001; i++) {
		Result[i] = -1;
	}

	cin >> Acounts;
	for (int i = 0; i < Acounts; i++) {
		cin >> exp >> coe;
		ExpA[i] = exp;
		A[exp] = coe;
	}
	cin >> Bcounts;
	for (int i = 0; i < Bcounts; i++) {
		cin >> exp >> coe;
		ExpB[i] = exp;
		B[exp] = coe;
	}

	int indexCount = 0;
	for (int i = 0; i < Acounts; i++) {		
		for (int j = 0; j < Bcounts; j++) {			
			if (Result[ExpA[i] + ExpB[j]] == -1) {
				Result[ExpA[i] + ExpB[j]] = A[ExpA[i]] * B[ExpB[j]];

				if (Result[ExpA[i] + ExpB[j]] != 0) {
					ResCounts++;
				}
			}
			else {
				if (Result[ExpA[i] + ExpB[j]] == 0 && A[ExpA[i]] * B[ExpB[j]] != 0)
					ResCounts++;
				Result[ExpA[i] + ExpB[j]] += A[ExpA[i]] * B[ExpB[j]];
			}
			
		}
	}

	cout << ResCounts << " ";
	for (int i = 2000; i >= 0; i--) {
		
		if (Result[i] != -1 && Result[i] != 0) {
			ResCounts--;
			//cout << "----" << ResCounts << "----" << endl;
			printf("%d %.1f", i, Result[i]);
			if (ResCounts != 0)
				printf(" ");
		}
	}

	return 0;
}

后来通过跟大佬交流之后，发现了一些端倪
大佬的代码：

#include <iostream>
#include <map>

using namespace std;

int main()
{
	using map_t = map<int, float>;
	map_t data[2];
	int c;
	int k;
	float v;
	for (int i = 0; i < 2; ++i) {
		cin >> c;
		for (int j = 0; j < c; ++j) {
			cin >> k >> v;
			data[i][k] = v;
		}
	}

	map_t out;
	for (map_t::iterator it0 = data[0].begin(); it0 != data[0].end(); ++it0) {
		for (map_t::iterator it1 = data[1].begin(); it1 != data[1].end(); ++it1) {
			int key = it0->first + it1->first;
			out[key] += it0->second * it1->second;
			if (out[key] == 0.0f) {
				out.erase(key);
			}
		}
	}

	int size = out.size();
	printf("%d ", size);
	for (map_t::reverse_iterator it = out.rbegin(); it != out.rend(); ++it) {
		printf("%d %.1f", it->first, it->second);
		if (--size > 0) {
			printf(" ");
		}
	}

	return 0;
}

我将之前的代码用map改写之后的代码

#include<iostream>
#include<string>
#include<stdio.h>
#include<map>
using namespace std;

struct Decline {
	bool operator()(const int x1, const int x2) const {
		return x1 > x2;
	}

};

int main() {
	map<int, double, Decline> A, B, Result;
	int Exp, number;
	double  Coe;

	cin >> number;
	while (number--) {
		cin >> Exp >> Coe;
		A.insert(pair<int, double>(Exp, Coe));
	}

	cin >> number;
	while (number--) {
		cin >> Exp >> Coe;
		B.insert(pair<int, double>(Exp, Coe));
	}

	pair<map<int, double>::iterator, bool> InsertFlag;

	for (map<int, double>::iterator i = A.begin(); i != A.end(); i++) {
		for (map<int, double>::iterator j = B.begin(); j != B.end(); j++) {
			if (i->second * j->second != 0) {
				InsertFlag = Result.insert(pair<int, double>(i->first + j->first, i->second * j->second));
				if (!InsertFlag.second) {
					Result[i->first + j->first] += i->second * j->second;
				}
			}
				
		}
	}

	int tag = Result.size();
	cout << tag << " ";
	for (map<int, double>::iterator i = Result.begin(); i != Result.end(); i++) {
		tag--;
		printf("%d %.1f", i->first, i->second);		
		if (tag != 0)
			cout << " ";
	}
	return 0;
}

这里可以发现，大佬在处理数据的时候，将加和为 0 的项目用 erase() 函数擦除了。后来经过交流发现，测试点 0 没通过的情况可能是 测试点 0 有负数，
我在对数据处理的时候，没有考虑负数加和，因此测试点 0 过不去。
所以在39行代码下方加入以下判断：

				if (Result[i->first + j->first] == 0)
					Result.erase(i->first + j->first);

即可满分通过
完整代码如下：

#include<iostream>
#include<string>
#include<stdio.h>
#include<map>
using namespace std;

struct Decline {
	bool operator()(const int x1, const int x2) const {
		return x1 > x2;
	}

};

int main() {
	map<int, double, Decline> A, B, Result;
	int Exp, number;
	double  Coe;

	cin >> number;
	while (number--) {
		cin >> Exp >> Coe;
		A.insert(pair<int, double>(Exp, Coe));
	}

	cin >> number;
	while (number--) {
		cin >> Exp >> Coe;
		B.insert(pair<int, double>(Exp, Coe));
	}

	pair<map<int, double>::iterator, bool> InsertFlag;

	for (map<int, double>::iterator i = A.begin(); i != A.end(); i++) {
		for (map<int, double>::iterator j = B.begin(); j != B.end(); j++) {
			if (i->second * j->second != 0) {
				InsertFlag = Result.insert(pair<int, double>(i->first + j->first, i->second * j->second));
				if (!InsertFlag.second) {
					Result[i->first + j->first] += i->second * j->second;
				}
				if (Result[i->first + j->first] == 0)
					Result.erase(i->first + j->first);
			}
				
		}
	}

	int tag = Result.size();
	cout << tag << " ";
	for (map<int, double>::iterator i = Result.begin(); i != Result.end(); i++) {
		tag--;
		printf("%d %.1f", i->first, i->second);		
		if (tag != 0)
			cout << " ";
	}
	return 0;

}

另外，如果觉得额外写一个结构体用于降序排序有些麻烦的话，可以使用 reverse_iterator，只需要将下面的代码

        for (map<int, double>::iterator i = Result.begin(); i != Result.end(); i++) {
		tag--;
		printf("%d %.1f", i->first, i->second);		
		if (tag != 0)
			cout << " ";
	}

改成这样子

	for (map<int, double>::reverse_iterator i = Result.rbegin(); i != Result.rend(); i++) {
		tag--;
		printf("%d %.1f", i->first, i->second);		
		if (tag != 0)
			cout << " ";
	}

即可，且无需定义并实现用于降序的结构体，定义类型的时候也不需要将结构体引入泛型，完整代码如下：

#include<iostream>
#include<string>
#include<stdio.h>
#include<map>
using namespace std;
int main() {
	map<int, double> A, B, Result;
	int Exp, number;
	double  Coe;

	cin >> number;
	while (number--) {
		cin >> Exp >> Coe;
		A.insert(pair<int, double>(Exp, Coe));
	}

	cin >> number;
	while (number--) {
		cin >> Exp >> Coe;
		B.insert(pair<int, double>(Exp, Coe));
	}

	pair<map<int, double>::iterator, bool> InsertFlag;

	for (map<int, double>::iterator i = A.begin(); i != A.end(); i++) {
		for (map<int, double>::iterator j = B.begin(); j != B.end(); j++) {
			if (i->second * j->second != 0) {
				InsertFlag = Result.insert(pair<int, double>(i->first + j->first, i->second * j->second));
				if (!InsertFlag.second) {
					Result[i->first + j->first] += i->second * j->second;
				}
				if (Result[i->first + j->first] == 0)
					Result.erase(i->first + j->first);
			}
				
		}
	}

	int tag = Result.size();
	cout << tag << " ";
	for (map<int, double>::reverse_iterator i = Result.rbegin(); i != Result.rend(); i++) {
		tag--;
		printf("%d %.1f", i->first, i->second);		
		if (tag != 0)
			cout << " ";
	}
	return 0;	
}

希望能帮到大家。