团体程序设计天梯赛 L2-018. 多项式A除以B（模拟）

题意：给你A，B两个多项式，问你A/B的值；注意多项式给你的是每个式子的指数与系数；保留到一位小数，如果出现系数为0（保留后也是）的情况，请不要输出它，如果没有非系数为0的情况就输出特殊

题解：多项式类似于“a*x^4+b*x^3+c*x^2+d*x^1+e*x^0”的形式，两个多项式除法就是模拟除法做

　　　现在被除数最大指数的系数、被除数最大指数的系数除以、结果就是商的系数，两个指数的差就是商的指数

　　　然后枚举除数每一位乘以这个值来被被除数减去，最后找被除数后一个位置继续循环，直到被除数最大项大于除数最大项

　　　最后有一个点需要注意，因为需要的是保留答案后系数为0也不能输出，所以在保留答案是一定要判断是否为0，不能再最后输出时在判断

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<vector>

#include<string>

#include<cstdio>

#include<cstring>

#include<iomanip>

#include<stdlib.h>

#include<iostream>

#include<algorithm>

using namespace std;

#define eps 1E-1

#define Eps 1E-1

/*注意可能会有输出-0.000*/

#define sgn(x) (x<-Eps? -1 :x<Eps? 0:1)//x为两个浮点数差的比较,注意返回整型

#define cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化

#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0

#define mul(a,b) (a<<b)

#define dir(a,b) (a>>b)

typedef long long ll;

typedef unsigned long long ull;

const int Inf=<<;

const ll INF=1LL<<;

const double Pi=acos(-1.0);

const int Mod=1e9+;

const int Max=;

double divide[Max],divisor[Max];//被除数 除数

double business[Max],remainde[Max];//商 余数

int busindex[Max],remindex[Max];//答案系数

int coundiv,counsor;

void Print(int coun,int* ansindex,double* ans)

{

    if(!coun)

        printf("0 0 0.0\n");

    else

    {

        printf("%d",coun);

        for(int i=;i<coun;++i)

        {

            if(!zero(ans[i]))

            printf(" %d %.1f",ansindex[i],ans[i]);

        }

        printf("\n");

    }

    return;

}

void Divison(int n,int dif,double num)

{

   for(int i=n;i>=dif;--i)

   {

       divide[i]-=divisor[i-dif]*num;

   }

    return;

}

void Solve(int maxdiv,int maxsor)

{

    coundiv=counsor=;

    for(int i=maxdiv;i>=maxsor;--i)

    {

        busindex[coundiv]=i-maxsor;

        int dif=busindex[coundiv];

        business[coundiv]=divide[i]/divisor[maxsor];

        Divison(i,dif,business[coundiv]);

        business[coundiv]=business[coundiv];

        if(sgn(business[coundiv])!=)//注意

        coundiv++;

    }

    for(int i=maxsor-;i>=;--i)

    {

            remindex[counsor]=i;

            remainde[counsor]=divide[i];

            if(sgn(remainde[counsor])!=)

                counsor++;

    }

    return;

}

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

        memset(divide,,sizeof(divide));

        memset(divisor,,sizeof(divisor));

        int maxdiv=,maxsor=;

        int index;

        for(int i=;i<n;++i)

        {

            scanf("%d",&index);

            maxdiv=max(maxdiv,index);

            scanf("%lf",&divide[index]);

        }

        scanf("%d",&n);

        for(int i=;i<n;++i)

        {

            scanf("%d",&index);

            maxsor=max(maxsor,index);

            scanf("%lf",&divisor[index]);

        }

        Solve(maxdiv,maxsor);

        Print(coundiv,busindex,business);

        Print(counsor,remindex,remainde);

    }

    return ;

}

巴特西

团体程序设计天梯赛 L2-018. 多项式A除以B（模拟）

最新文章

热门文章