浙江财经大学
信息管理与工程学院

PAT(A) 1009. Product of Polynomials (25)

本文由 Ocrosoft 于 2016-12-29 20:38:26 发表

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 <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define strend string::npos
#define ms(a) memset(a,0,sizeof(a))
#define  rep(a,v,b) for(int a=v;a<b;a++)
#define  repe(a,v,b) for(int a=v;a<=b;a++)
typedef long long LL;
const LL LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const int MAXN = 2000 + 10;
const int MOD = 1000000009;
LL GCD(LL a, LL b)
{
	if (!b)return a;
	return GCD(b, a%b);
}
/*(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
/*(◕‿‿◕) 签订契约,成为马猴烧酒吧! (◕‿‿◕)*/
/*(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
using namespace std;
int main()
{
	map<int, double,greater<int> > x, x1, x2;
	x.clear(); x1.clear(); x2.clear();
	int n; cin >> n;
	for (int i = 0; i < n; i++)
	{
		int t; double y;
		cin >> t >> y;
		x1[t] = y;
	}
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int t; double y;
		cin >> t >> y;
		x2[t] = y;
	}
	map<int, double,greater<int> >::iterator i, j;
	for (i = x1.begin(); i != x1.end(); i++)
	{
		for (j = x2.begin(); j != x2.end(); j++)
		{
			if (x.count(i->first + j->first))x[i->first + j->first] += i->second*j->second;
			else x[i->first + j->first] = i->second*j->second;
		}
	}
	int sum = 0;
	for (i = x.begin(); i != x.end(); i++)
		if (i->second)sum++;
	printf("%d", sum);
	for (i = x.begin(); i != x.end(); i++)
		if (i->second)printf(" %d %.1lf", i->first, i->second);
	printf("\n");
	return 0;
}

欢迎转载,请保留出处与链接。Ocrosoft » PAT(A) 1009. Product of Polynomials (25)

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址