GPLT L2-018 多项式A除以多项式B 多项式除法

题目链接:https://pintia.cn/problem-sets/994805046380707840/problems/994805060372905984

这个题是模拟多项式除法,关于多项式除法可以看这个问题下方十字学习体系的回答:https://www.zhihu.com/question/53488160/answer/1280612213

理解怎么算后,代码就是模拟了

#include <bits/stdc++.h>
using namespace std;
const int inf=1<<30;
typedef long long ll;
typedef pair<int,int> P;
const double pi=acos(-1);
const int mod=1e8+7;
const int maxn=1e5+7;
const int maxm=25000;
double c1[3000],c2[3000],c3[3000];
int rule(double c[],int end){
    int cnt=0;
    for(int i=end;i>=0;i--){
        if(abs(c[i])+0.05>=0.1)cnt++;
    }
    return cnt;
}
void print(double c[],int end){
    int cnt=rule(c,end);
    cout<<cnt;
    if(cnt==0){
        cout<<" 0 0.0";
        return ;
    }
    for(int i=end;i>=0;i--){
        if(abs(c[i])+0.05>=0.1){
            printf(" %d %.1lf",i,c[i]);
        }
    }
}
int main(){
    int n;scanf("%d",&n);
    int mx1=-1,mx2=-1;
    for(int i=0;i<n;i++){
        int t;scanf("%d",&t);
        mx1=max(mx1,t);
        scanf("%lf",&c1[t]);
    }
    int m;scanf("%d",&m);
    for(int i=0;i<m;i++){
        int t;scanf("%d",&t);
        mx2=max(mx2,t);
        scanf("%lf",&c2[t]);
    }
    int t1=mx1,t2=mx2;
    while(t1>=t2){
        c3[t1-t2]=1.0*c1[t1]/c2[t2];
        for(int i=t1,j=t2;j>=0;i--,j--)c1[i]-=c3[t1-t2]*c2[j];
        while(abs(c1[t1])<0.00001)t1--;    
    }
    print(c3,mx1-mx2);
    cout<<endl;
    print(c1,t1);
    return 0; 
}

 

上一篇:C++-文件输入输出流-学生信息读取/文件复制


下一篇:关于C++模板类运算符重载在类内外实现的不同