首页 > 代码库 > PAT L2-018. 多项式A除以B

PAT L2-018. 多项式A除以B

暴力,模拟。

比赛搞了一个小时搞到了$1$分。赛场上不够冷静......之前没接触过多项式除法,但赛场上想到了除法的规则,莫名其妙写的时候不知道哪里崩了。对于这样的题目,应该先测一测数据的指数是不是很大,指数不大开数组存就可以了。

#include<bits/stdc++.h>using namespace std;double eps=1e-1;double a[5010],b[5010],c[5010];int n;int main(){    memset(a,0,sizeof a);    memset(b,0,sizeof b);    scanf("%d",&n);    for(int i=1;i<=n;i++)    {        int e; double x; scanf("%d%lf",&e,&x);        a[e]=x;    }    scanf("%d",&n);    for(int i=1;i<=n;i++)    {        int e; double x; scanf("%d%lf",&e,&x);        b[e]=x;    }    int limit;    for(int i=3000;i>=0;i--)    {        if(b[i]>0)        {            limit=i;            break;        }    }    while(1)    {        int g=-1;        for(int i=3000;i>=0;i--)        {            if(a[i]!=0)            {                g=i;                break;            }        }        if(g<limit) break;        c[g-limit] = a[g]/b[limit];        for(int i=0;i<=3000;i++)        {            if(g-limit+i<=3000)                a[g-limit+i]-=c[g-limit]*b[i];        }        for(int i=0;i<=3000;i++)        {            if(abs(a[i])<eps) a[i]=0;            if(abs(b[i])<eps) b[i]=0;            if(abs(c[i])<eps) c[i]=0;        }    }    int num1=0,num2=0;    for(int i=3000;i>=0;i--)    {        if(c[i]==0) continue;        num1++;    }    if(num1==0) printf("0 0 0.0\n");    else    {        printf("%d ",num1);        for(int i=3000;i>=0;i--)        {            if(c[i]==0) continue;            printf("%d %.1f",i,c[i]);            num1--;            if(num1==0) printf("\n");            else printf(" ");        }    }    for(int i=3000;i>=0;i--)    {        if(a[i]==0) continue;        num2++;    }    if(num2==0) printf("0 0 0.0\n");    else    {        printf("%d ",num2);        for(int i=3000;i>=0;i--)        {            if(a[i]==0) continue;            printf("%d %.1f",i,a[i]);            num2--;            if(num2==0) printf("\n");            else printf(" ");        }    }    return 0;}

 

PAT L2-018. 多项式A除以B