题目描述
给定两个多项式 A 和 B,计算 A×B 的结果。
输入格式
共两行,每行包含一个多项式的信息,格式如下:
K N1 aN1 N2 aN2 … NK aNK
其中,K 表示多项式中非零项的数量,Ni 和 aNi 分别表示其中一个非零项的指数和系数。
输出格式
按照与输入相同的格式,输出 A×B 的结果。
结果中的各项的系数均保留一位小数。
数据范围
K 为整数,1≤K≤10。
Ni 为整数,0≤NK<⋯<N2<N1≤1000。
aNi 为浮点数,−100≤aNi≤100。
样例
输入样例:
2 1 2.4 0 3.2
2 2 1.5 1 0.5
输出样例:
3 3 3.6 2 6.0 1 1.6
算法1
(双数组模拟) $O(n^2)$
这题刚开始大方向思路是对的,但是一些细节没有考虑清楚
比如在yoghurt第二个多项式每一个都乘以前一个多项式的时候,那一个用作乘法运算的数组是不能动的,所以要使用双数组
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
double num[N];
double res[N];
bool check(double num)
{
if(fabs(num-0)<1e-6)return false;
return true;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<=200;i++)
{
num[i]=0;
res[i]=0;
}
for(int i=0;i<n;i++)
{
int z;
double x;
cin>>z>>x;
num[z]+=x;
}
int m;
cin>>m;
for(int i=0;i<m;i++)
{
int z;
double x;
cin>>z>>x;
for(int j=0;j<=2000;j++)
{
if(check(num[j]))
{
int j1=j+z;
double ans=num[j]*x;
res[j1]+=ans;
}
}
}
int cnt=0;
for(int i=0;i<=2000;i++)
{
if(check(res[i]))cnt++;
}
cout<<cnt<<" ";
for(int i=2000;i>=0;i--)
{
if(check(res[i])&&cnt>1)
{
printf("%d %.1lf ",i,res[i]);
cnt--;
}
else if(check(res[i]))
{
printf("%d %.1lf",i,res[i]);
}
}
return 0;
}