自动搬运

查看原文

来自洛谷，原作者为

	purinliang **

搬运于2025-08-24 21:35:54，当前版本为作者最后更新于2019-04-28 18:06:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解： 学过面向对象的同学就可以知道，按题目要求设计单项式类和多项式类，定义他们的一系列行为，然后让他们自己自动完成。这样是最省事的。

其中加法乘法以及合并同类项的思路都很简单，在代码的注释里写的很清楚。

重点说一下怎么toString和fromString，这应该是我觉得这道题有提高+的难度的原因。

toString

首先是toString，我的处理方法是，让单项式每次把自己转成带加减符号的string返回，多项式就调用每个单项式的toString拼接，最后加点特判。

其中有一些需要注意的：

• 当单项式不是常数项时，系数的+1和-1是不输出1的。
• 变量的指数可以是负的。
• 系数为0，不输出。
• 当多项式中没有单项式，输出0。
• 当多项式的开头是+号，则去掉+号。
• 合并同类项，并按题目要求排序。

fromString

然后是巨坑的fromString，调了一晚上。

其中有一些需要注意的：

• 遇到运算符和数字时可以一直读到第一个字母或者运算符或者字符串尾，这些都属于系数。遇到字母表示后面有指数，否则是常数项。
• 没有遇到数字直接遇到字母/遇到运算符后直接遇到字母，系数是暗含的绝对值1。
• 可能同个单项式中存在重复的字母，例如AGAA表示A^3G，没有试过，可能有。
• 遇到字母后立刻判断下一个是不是^符，若是则可以一直读到第一个字母或者运算符或者字符串尾，这些都属于指数，小心负指数。
• 遇到运算符/字符串末尾要立刻保存当前的单项式。
• 一直读入数字时多加的1要减回来，否则会跳过一个字符。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Mo {
    //单项式由两个部分组成：带符号的系数+字母和带符号的指数
    ll xs;          //单项式的系数
    ll zs[256];     //单项式的指数

    Mo() {
        xs=0;
        memset(zs,0,sizeof(zs));
    }

    //单项式的小于序，按题目要求，从A到Z，从小到大排序
    bool operator<(Mo &m) {
        for(int i='A'; i<='Z'; i++) {
            if(zs[i]!=m.zs[i]) {
                return zs[i]<m.zs[i];
            } else {
                continue;
            }
        }
        //为确定严格的小于序，规定指数相同的按系数排列
        return xs<m.xs;
    }

    //指示两个单项式能否合并同类项
    bool canMerge(Mo &m) {
        //能够合并，前提是指数都相同
        for(int i='A'; i<='Z'; i++) {
            if(zs[i]!=m.zs[i]) {
                return false;
            } else {
                continue;
            }
        }
        return true;
    }

    //单项式的乘法，系数相乘，对应指数相加
    Mo operator*(Mo &m) {
        Mo ret;
        ret.xs=xs*m.xs;
        for(int i='A'; i<='Z'; i++) {
            ret.zs[i]=zs[i]+m.zs[i];
        }
        return ret;
    }

    //单项式的带符号输出，即使在多项式的开头也输出符号
    string toString() {
        if(xs==0) {
            //多项式不应该有系数为0的单项式，都进入这里了直接RE吧，为0的项在读入和加法的时候应被消除
            exit(-1);
            return "";
        }

        string ans="";
        char tmp[25];   //用来把数字转成字符串

        if(xs>0) {
            //系数为正，加入单项式前的加号
            ans+="+";
            if(xs>1) {
                //非1的系数必须打印
                sprintf(tmp,"%lld",xs);
                ans+=string(tmp);
            }
        } else {
            //负数自带符号，但-1不输出那个1，就单输出一个负号
            if(xs==-1) {
                ans+="-";
            } else {
                //非-1的系数必须打印
                sprintf(tmp,"%lld",xs);
                ans+=string(tmp);
            }
        }

        int nozs=1;     //指示这个多项式是否 没有指数非零

        for(int i='A'; i<='Z'; i++) {
            if(zs[i]!=0) {
                nozs=0; //有指数非零
                //指数非0，输出该字母
                ans+=(char)(i);
                if(zs[i]!=1) {
                    //指数非1，额外输出指数，负数也一样可以输出
                    ans+="^";
                    sprintf(tmp,"%lld",zs[i]);
                    ans+=string(tmp);
                }
            }
        }

        if(nozs) {
            //没有指数非零，这个是常数项
            if(abs(xs)==1)
                //常数项的正负1要输出
                ans+="1";
        }
        return ans;
    }
};

struct Poly {
    //存放单项式的向量
    vector<Mo> v;

    Poly() {}

    //加法，两个多项式的单项式堆在一起，合并同类项
    Poly operator+(Poly p) {
        Poly ret;
        for(auto vi:v) {
            ret.v.push_back(vi);
        }
        for(auto vi:p.v) {
            ret.v.push_back(vi);
        }

        ret.Merge();
        return ret;
    }

    //乘法，二维遍历每个单项式，乘在一起，然后堆在一起合并同类项
    Poly operator*(Poly p) {
        Poly ret;
        for(auto vi:v) {
            for(auto vpi:p.v) {
                ret.v.push_back(vi*vpi);
            }
        }
        ret.Merge();
        return ret;
    }

    //合并同类项并排序
    void Merge() {
        //临时向量vt
        vector<Mo> vt;
        for(auto &vi:v) {
            //遍历现有的每个项，在临时向量中找它已经插入的同类项，若找到可以合并的项，系数相加
            int suc=0;
            for(auto &vti:vt) {
                if(vti.canMerge(vi)) {
                    vti.xs+=vi.xs;
                    suc=1;
                    break;
                }
            }
            if(suc==0) {
                //没有同类项，则接在临时向量的后面
                vt.push_back(vi);
            }
        }

        v.clear();
        //清空原向量
        for(auto vti:vt) {
            //遍历临时向量，去除系数为0的项
            if(vti.xs) {
                v.push_back(vti);
            }
        }
        //排序，按单项式定义的顺序排序
        sort(v.begin(),v.end());
    }

    //返回一整个排序好的多项式，并自动去除最前面的正号
    string toString() {
        //多项式中没有单项式，返回一个0
        if(v.size()==0)
            return "0";
        Merge();   //合并同类项并排序
        string ans="";
        for(auto vi:v)
            ans+=vi.toString();

        //前面已经保证多项式至少有一个单项式，而且它至少会输出一个负号，故可以ans[0]

        //去除开头多余的+号
        if(ans[0]=='+') {
            ans=ans.substr(1,ans.length()-1);
        }

        return ans;
    }

    void fromString(string s) {
        int n=s.length();

        ll xs=0;        //带符号系数
        ll zs[256];     //带符号指数
        memset(zs,0,sizeof(zs));

        for(int i=0; i<=n; i++) {
            if(i==n) {
                //到达字符串结尾，保存最后一个单项式
                addMo(xs,zs);
                return;
            }
            if(s[i]=='+'||s[i]=='-'||isdigit(s[i])) {
                //遇到数字，处理到直到遇到下一个字母或者运算符或者结尾
                //算法的逻辑保证遇到的必定是系数而不是指数

                //保存最后一个单项式
                addMo(xs,zs);

                int flag=1;
                if(!isdigit(s[i])) {
                    //当前遇到的是符号
                    //cerr<<"+"<<endl;
                    if(s[i]=='-')
                        flag=-1;
                    i++;
                    //指向符号的下一个字符
                    if(i==n) {
                        //到达字符串结尾，保存最后一个单项式？
                        //符号后面都没有东西，系数是0，不用添加单项式
                        return;
                    }

                    if(isdigit(s[i])) {
                        //下一个是显式指定的数字，处理到第一个非数字
                        while(isdigit(s[i])) {
                            xs=10ll*xs+(s[i]-'0');
                            i++;
                            if(i==n) {
                                //到达字符串结尾，保存最后一个单项式，也就是常数项，当然要注意符号
                                xs*=flag;
                                addMo(xs,zs);
                                return;
                            }
                        }
                        //现在s[i]是非数字，下次for会i++，这里补偿--
                        i--;
                        //保存符号
                        xs*=flag;
                    } else {
                        //符号后面不是数字，系数是隐含的1
                        xs=1;
                        //现在s[i]是非数字，下次for会i++，这里补偿--
                        i--;
                        //保存符号
                        xs*=flag;
                    }
                } else {
                    //没有遇到符号就直接遇到数字，是多项式的开头
                    while(isdigit(s[i])) {
                        xs=10ll*xs+(s[i]-'0');
                        i++;
                        if(i==n) {
                            //到达字符串结尾，保存最后一个单项式，也就是常数项，当然要注意符号，虽然一定是+1
                            xs*=flag;
                            addMo(xs,zs);
                            return;
                        }
                    }
                    //现在s[i]是非数字，下次for会i++，这里补偿--
                    i--;
                    //保存符号，虽然一定是+1
                    xs*=flag;
                }
            } else if(isalpha(s[i])) {
                //遇到字母，处理到直到遇到下一个字母或者运算符或者结尾
                //没有遇到运算符和数字就遇到多项式开头的字母，系数为1
                if(xs==0)
                    xs=1;
                //保存这个字母，名字叫做c
                int c=s[i];
                //cout<<(char)(c)<<"!!!"<<endl;
                //指向下一个字符
                i++;
                if(i==n) {
                    //到达字符串结尾，保存最后一个单项式
                    //先把最后一个字符的1次方加上
                    zs[c]++;
                    addMo(xs,zs);
                    return;
                }
                if(s[i]=='^') {
                    //是指数符号，说明要继续处理
                    i++;
                    //指向下一个数字或者符号

                    int flag=1;
                    if(!isdigit(s[i])) {
                        //当前遇到的是符号
                        if(s[i]=='-')
                            flag=-1;
                        i++;
                        //指向符号的下一个字符
                        if(i==n) {
                            //到达字符串结尾，你符号后面居然没有数？那就认为指数是0吧，舍弃最后一个字母，保存单项式
                            addMo(xs,zs);
                            return;
                        }

                        ll tzs=0;
                        if(isdigit(s[i])) {
                            //下一个是显式指定的数字，处理到第一个非数字
                            while(isdigit(s[i])) {
                                tzs=10ll*tzs+(s[i]-'0');
                                i++;
                                if(i==n) {
                                    //到达字符串结尾，保存最后一个单项式
                                    //保存最后一个字母的指数，记得乘上符号
                                    zs[c]+=tzs*flag;
                                    addMo(xs,zs);
                                    return;
                                }
                            }
                            //现在s[i]是非数字，下次for会i++，这里补偿--
                            i--;
                            //保存符号
                            tzs*=flag;
                            //保存指数
                            zs[c]+=tzs;
                        } else {
                            //符号后面不是数字，系数是隐含的1
                            tzs=1;
                            //现在s[i]是非数字，下次for会i++，这里补偿--
                            i--;
                            //保存符号
                            tzs*=flag;
                            //保存指数
                            zs[c]+=tzs;
                        }
                    } else {
                        //没有遇到符号就直接遇到数字，是正的指数
                        //cerr<<"...\n"<<endl;
                        ll tzs=0;
                        while(isdigit(s[i])) {
                            tzs=10ll*tzs+(s[i]-'0');
                            i++;
                            if(i==n) {
                                //到达字符串结尾，保存最后一个单项式，也就是常数项，当然要注意符号，虽然一定是+1
                                tzs*=flag;
                                zs[c]+=tzs;
                                addMo(xs,zs);
                                return;
                            }
                        }
                        //现在s[i]是非数字，下次for会i++，这里补偿--
                        i--;
                        //保存符号，虽然一定是+1
                        tzs*=flag;
                        //保存指数
                        zs[c]+=tzs;
                    }
                } else {
                    //遇到了字母或运算符，保存指数并补偿--
                    zs[c]++;
                    i--;
                }
            }
        }
    }

    //向多项式中添加一个单项式
    void addMo(ll &xs,ll *zs) {
        if(xs==0)
            return;
        Mo m;
        m.xs=xs;
        memcpy(m.zs,zs,sizeof(m.zs));
        v.push_back(m);
        xs=0;
        //不能sizeof(zs)，因为这里zs不是数组而只是一个指针
        memset(zs,0,sizeof(ll)*256);
    }
};

char s[10005],t[10005],n;

int main() {
#ifdef Yinku
    freopen("Yinku.in","r",stdin);
#endif // Yinku

    fgets(s,10000,stdin);
    n=strlen(s);

    for(int i=0,j=0; i<=n; i++) {
        if(i==n) {
            t[j]='\0';
        }
        if(s[i]!=' '&&s[i]!='\n') {
            t[j++]=s[i];
        }
    }

    Poly A;
    A.fromString(string(t));

    fgets(s,10000,stdin);
    n=strlen(s);

    for(int i=0,j=0; i<=n; i++) {
        if(i==n) {
            t[j]='\0';
        }
        if(s[i]!=' '&&s[i]!='\n') {
            t[j++]=s[i];
        }
    }

    Poly B;
    B.fromString(string(t));

#ifdef Yinku
    cout<<A.toString()<<endl;
    cout<<B.toString()<<endl;
#endif // Yinku

    Poly C=A+B;
    Poly D=A*B;
    cout<<C.toString()<<endl;
    cout<<D.toString()<<endl;
}