1002. A+B for Polynomials (25)

(1)思路

用vector保存两个多项式结构

将其中一个的所有元素压入一个结果vecotor,然后另一个vector对每个元素进行迭代

一旦找到指数相同相的就改变结果vector中项的系数

注意题目中要求 where K is the number of nonzero terms in the polynomial

所以要舍弃所有系数为零的项

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int n;
struct re{
  int exp;
  double coe;
};
const double EPS=1e-8;
vector<re> add_v(vector<re> v1,vector<re> v2) {
  vector<re> temp;
  for(int i=0;i<v2.size();i++) temp.push_back(v2[i]);
  for(int i=0;i<v1.size();i++) {
    int flag=0;
    for(int j=0;j<v2.size();j++) {
      if(v1[i].exp == v2[j].exp) {
    temp[j].coe+=v1[i].coe;
    flag=1;
      }
    }
    if(flag == 0) {
      temp.push_back(v1[i]);
    }
  }
  return temp;
}
bool cmp(re r1,re r2) {
  return r1.exp > r2.exp;
}
int main() {
  vector<re> v1;
  vector<re> v2;
  scanf("%d",&n);
  for(int i=0;i<n;i++) {
    re temp;
    scanf("%d %lf",&temp.exp,&temp.coe);
    v1.push_back(temp);
  }
  scanf("%d",&n);
  for(int i=0;i<n;i++) {
    re temp;
    scanf("%d %lf",&temp.exp,&temp.coe);
    v2.push_back(temp);
  }
  vector<re> result=add_v(v1,v2);
  sort(result.begin(),result.end(),cmp);
  int size=0;
  for(int i=0;i<result.size();i++){
    if(fabs(result[i].coe) < EPS) continue;
    else size++;
  }
  printf("%d",size);
  for(int i=0;i<result.size();i++) {
    if(fabs(result[i].coe) < EPS) continue;
    printf(" %d %.1lf",result[i].exp,result[i].coe);
  }
  return 0;
}

(2)

考虑到这里指数最多只有1000项所以可以用数组保存系数值,下标为指数值

然后读入数据时修改对应指数的系数,然后记录非零项,按指数递减输出系数

#include <cstdio>
#include <cmath>
using namespace std;
const double EPS=1e-8;
int main() {
  double result[1001]={0};
  int n;
  scanf("%d",&n);
  for(int i=0;i<n;i++) {
    double coe;
    int exp;
    scanf("%d %lf",&exp,&coe);
    result[exp]+=coe;
  }
  scanf("%d",&n);
  for(int i=0;i<n;i++) {
    double coe;
    int exp;
    scanf("%d %lf",&exp,&coe);
    result[exp]+=coe;
  }
  int size=0;
  for(int i=0;i<1001;i++) {
    if(fabs(result[i]) > EPS) size++;
  }
  printf("%d",size);
  for(int i=1000;i>=0;i--) {
    if(fabs(result[i]) > EPS) {
      printf(" %d %.1lf",i,result[i]);
    }
  }
  return 0;
}