PAT 甲级 1009 Product of Polynomials 多项式乘法

思路：

PAT 甲级 1002 多项式加法
可以先参考多项式加法。乘法的思路和加法基本一样。我们先找出两个多项式的最高指数项的指数max1、max2和最小指数项的指数min1、min2，相乘后得到的多项式的最高指数项的指数一定是max1+max2，最小指数项的指数一定是min1+min2。遍历这个指数范围，输出最后的结果即可。

代码如下：c

#include<iostream>
#include<math.h>
#include<iomanip>
using namespace std;

int a1[15],a2[15];
double b1[15],b2[15];
double xishu[2005];//最终结果的系数
int visit[2005];//访问数组

int main(){
  int k1,k2;//k1为第一个多项式的k，k2为第二个多项式的k
  cin>>k1;
  int max1,min1;//max1为两个多项式中的最大项指数
                //min1为两个多项式中的最小项指数
  for(int i=0;i<k1;i++){//读入第一个数的指数和系数
    cin>>a1[i]>>b1[i];
  }

  max1=a1[0];//a1[0]肯定为第一个多项式的指数最大项
  min1=a1[k1-1];//a1[k1-1]肯定为第一个多项式的指数最小项

  cin>>k2;
  for(int i=0;i<k2;i++){//读入第二个多项式1
    cin>>a2[i]>>b2[i];
  }

  max1=a2[0]+max1;
  min1=a2[k2-1]+min1;//求出两个多项式的指数最大项和最小项

  for(int i=0;i<2005;i++){//初始化xishu[]和visit[]
    xishu[i]=0;
    visit[i]=0;
  }

  for(int i=0;i<k1;i++){//合并两个多项式指数相同的项，将合并后的系数存入xishu数组
    for(int j=0;j<k2;j++){
            xishu[a1[i]+a2[j]]+=b1[i]*b2[j];
            visit[a1[i]+a2[j]]=1;//标记该指数已访问
    }
  }



  int cnt=0;//cnt为合并后的所有非0系数项有多少个
  for(int i=min1;i<=max1;i++){
    if(visit[i]==1&&xishu[i]!=0){
        cnt++;
    }
  }

  if(cnt==0){//若两个多项式相加等于0，直接返回0
    cout<<0;
    return 0;
  }

  cout<<cnt<<' ';
  for(int i=max1;i>=min1;i--){
    if(i!=min1&&visit[i]==1){//若不为最后一项
      if(xishu[i]==0){//若系数为0，直接跳过
        continue;
      }
      cout<<i<<' ';

      int flag=true;//这里就是非常坑的点，因为若
                    //某一项的后面所有项都为0
                    //这一项后面就不能输出空格
                    //所以要用一个flag来判断
      for(int j=i-1;j>=0;j--){
        if(xishu[j]!=0){
            flag=false;
            break;
        }
      }
      if(flag){//某一项的后面项全为0
        cout<<fixed<<setprecision(1)<<xishu[i];
        return 0;
      }else{
        cout<<fixed<<setprecision(1)<<xishu[i]<<' ';
      }
    }else if(i==min1&&visit[i]==1){//若是最后一项
      if(xishu[i]==0){
        continue;
      }
      cout<<i<<' ';
      cout<<fixed<<setprecision(1)<<xishu[i];
    }
  }
  return 0;

}