团体程序设计天梯赛 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=1<<28;
const ll INF=1LL<<60;
const double Pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=100100;
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=0;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=0;
    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])!=0)//注意
        coundiv++;
    }
    for(int i=maxsor-1;i>=0;--i)
    {
            remindex[counsor]=i;
            remainde[counsor]=divide[i];
            if(sgn(remainde[counsor])!=0)
                counsor++;
    }
    return;
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(divide,0,sizeof(divide));
        memset(divisor,0,sizeof(divisor));
        int maxdiv=0,maxsor=0;
        int index;
        for(int i=0;i<n;++i)
        {
            scanf("%d",&index);
            maxdiv=max(maxdiv,index);
            scanf("%lf",&divide[index]);
        }
        scanf("%d",&n);
        for(int i=0;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 0;
}
时间: 03-27

团体程序设计天梯赛 L2-018. 多项式A除以B(模拟)的相关文章

团体程序设计天梯赛-练习集 L2-2. 链表去重 数组模拟链表

L2-2. 链表去重 时间限制 300 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 作者 陈越 给定一个带整数键值的单链表L,本题要求你编写程序,删除那些键值的绝对值有重复的结点.即对任意键值K,只有键值或其绝对值等于K的第一个结点可以被保留.同时,所有被删除的结点必须被保存在另外一个链表中.例如:另L为21→-15→-15→-7→15,则你必须输出去重后的链表21→-15→-7.以及被删除的链表-15→15. 输入格式: 输入第一行包含链表第一个结

PAT 团体程序设计天梯赛-练习集L1-011. A-B

本题要求你计算A-B.不过麻烦的是,A和B都是字符串 —— 即从字符串A中把字符串B所包含的字符全删掉,剩下的字符组成的就是字符串A-B. 输入格式: 输入在2行中先后给出字符串A和B.两字符串的长度都不超过104,并且保证每个字符串都是由可见的ASCII码和空白字符组成,最后以换行符结束. 输出格式: 在一行中打印出A-B的结果字符串. 输入样例: I love GPLT! It's a fun game! aeiou 输出样例: I lv GPLT! It's fn gm! 1 #inclu

PAT 团体程序设计天梯赛-练习集 L1-015. 跟奥巴马一起画方块

美国总统奥巴马不仅呼吁所有人都学习编程,甚至以身作则编写代码,成为美国历史上首位编写计算机代码的总统.2014年底,为庆祝“计算机科学教育周”正式启动,奥巴马编写了很简单的计算机代码:在屏幕上画一个正方形.现在你也跟他一起画吧! 输入格式: 输入在一行中给出正方形边长N(3<=N<=21)和组成正方形边的某种字符C,间隔一个空格. 输出格式: 输出由给定字符C画出的正方形.但是注意到行间距比列间距大,所以为了让结果看上去更像正方形,我们输出的行数实际上是列数的50%(四舍五入取整). 输入样例

PAT 团体程序设计天梯赛-练习集 L1-007. 念数字

输入一个整数,输出每个数字对应的拼音.当整数为负数时,先输出“fu”字.十个数字对应的拼音如下: 0: ling 1: yi 2: er 3: san 4: si 5: wu 6: liu 7: qi 8: ba 9: jiu 输入格式: 输入在一行中给出一个整数,如: 1234 . 提示:整数包括负数.零和正数. 输出格式: 在一行中输出这个整数对应的拼音,每个数字的拼音之间用空格分开,行末没有最后的空格.如 yi er san si. 输入样例: -600 输出样例: fu liu ling

PAT 团体程序设计天梯赛-练习集 L1-005. 考试座位号

每个PAT考生在参加考试时都会被分配两个座位号,一个是试机座位,一个是考试座位.正常情况下,考生在入场时先得到试机座位号码,入座进入试机状态后,系统会显示该考生的考试座位号码,考试时考生需要换到考试座位就座.但有些考生迟到了,试机已经结束,他们只能拿着领到的试机座位号码求助于你,从后台查出他们的考试座位号码. 输入格式: 输入第一行给出一个正整数N(<=1000),随后N行,每行给出一个考生的信息:“准考证号 试机座位号 考试座位号”.其中准考证号由14位数字组成,座位从1到N编号.输入保证每个

PAT 团体程序设计天梯赛-练习集 L1-016. 查验身份证

一个合法的身份证号码由17位地区.日期编号和顺序编号加1位校验码组成.校验码的计算规则如下: 首先对前17位数字加权求和,权重分配为:{7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2}:然后将计算的和对11取模得到值Z:最后按照以下关系对应Z值与校验码M的值: Z:0 1 2 3 4 5 6 7 8 9 10M:1 0 X 9 8 7 6 5 4 3 2 现在给定一些身份证号码,请你验证校验码的有效性,并输出有问题的号码. 输入格式: 输入第一行给出正整数N(<= 100

PAT 团体程序设计天梯赛-练习集 L1-017. 到底有多二

一个整数“犯二的程度”定义为该数字中包含2的个数与其位数的比值.如果这个数是负数,则程度增加0.5倍:如果还是个偶数,则再增加1倍.例如数字“-13142223336”是个11位数,其中有3个2,并且是负数,也是偶数,则它的犯二程度计算为:3/11*1.5*2*100%,约为81.82%.本题就请你计算一个给定整数到底有多二. 输入格式: 输入第一行给出一个不超过50位的整数N. 输出格式: 在一行中输出N犯二的程度,保留小数点后两位. 输入样例: -13142223336 输出样例: 81.8

PTA|团体程序设计天梯赛-练习题目题解锦集(C/C++)(持续更新中……)

PTA|团体程序设计天梯赛-练习题目题解锦集(持续更新中) 实现语言:C/C++:      欢迎各位看官交流讨论.指导题解错误:或者分享更快的方法!! 题目链接:https://pintia.cn/problem-sets/994805046380707840/problems 目录 (点击对应题目即可进入相应题解--小声BB--) L1-001 Hello World (5 分) L1-002 打印沙漏 (20 分) L1-003 个位数统计 (15 分) L1-004 计算摄氏温度 (5

第四届cccc团体程序设计天梯赛

蒟蒻的第一次参加天梯赛,也能也是最后一次参加天梯赛了,下半年打完icpc就要退役了,准备考研复习了 本人的第一次天梯赛,也是本校的第一次天梯赛,由于大家都缺少经验,痛失银奖,只拿了个铜奖回来(刚开始银牌区第二的,比赛结束变成铜牌第二了,哭唧唧),下次打应该会少踩写坑. 这届次的L1-8是“罪魁祸首”,我们几个队友头铁一直去莽这道题(我也花了不少时间),直到主办人员过来说进阶标准降到600分,我才写L2的,然后L2-4用stack写又出bug了,改了半天改不出来,浪费了 几十分钟,最后受不了了,直

PAT 团体程序设计天梯赛-练习集 题解(凑零钱,堆栈,社交集群)

开始准备cccc(cry)天梯赛了,第一周训练题,把官网挂出的训练题刷完了,对pat有了一点点的熟悉感. L1-1  就不说了... L1-2 打印沙漏 一个变量保存空格数,一个变量保存沙漏符号数,打印就行了,但这题话说wrong好几次啊,坑点是沙漏符号后面不打印空格,orz... <span style="font-size:14px;">#include<iostream> #include<stdio.h> #include<math.h