题解：P2281 [HNOI2003] 多项式的加法和乘法

Twig_K · 2024-11-12 20:22:32 · 题解

求求 NOIP 出题人，如果要出字符串大模拟，善待我一些吧/kel

用一个结构体封装单项式，一个结构体封装多项式。

单项式中要用到的东西：

• 结构体中存系数，以及大小为 26 的数组用于记录每个字母的指数。
• 读入，从字符串转换为单项式。
• 重载运算符小于和等于，用来排序和去重。
• 重载运算符乘号，用于单项式乘法。
• 单项式的输出函数 printmono。

多项式中要用到的东西：

• 一个 vector，存多项式的每一项（每一项类型都是前面的单项式）。
• 获取多项式的函数 getpoly。
• 重载运算符加和乘，多项式的加法和乘法。
• unique 函数，用于多项式的排序和去重。
• 多项式的输出函数 print。

下面是每个函数的具体坑点：

单项式：

• 读入，从字符串转换为单项式。
  • 单项式系数：没有读入的话默认绝对值是 1，需要考虑负号，不清楚有没有系数是 -1 只保留负号的情况。
  • 指数：和系数一样，有可能为负数，且要注意指数 1 的省略。
  • 可能存在 AAA 这样的指数未合并的情况，所以或许更保险的做法是，每次累加指数而不是直接赋值。
  • 对于有些写法（比如这篇题解），结尾最后的一个字母（和它的指数）不要忘记。
• 重载运算符小于和等于，用来排序和去重。
  • 需要特别考虑系数为 0 的情况，有时候系数为 0，后面的指数仍然会有值。所以在比较时如果存在系数为 0 的直接返回。
• 重载运算符乘号，用于单项式乘法。
  • 系数相乘，对应指数相加就可以了。
• 单项式的输出函数 printmono。
  • 对于一些写法（不包括这篇题解），如果系数为 0，不需要输出。
  • 如果系数绝对值不为 1，首先输出系数。
  • 如果系数为 -1，首先输出负号。
  • 在遍历完所有指数后，如果所有指数都为 0 且系数绝对值为 1 输出系数。

多项式：

• 一个 vector，存多项式的每一项。
• 获取多项式的函数 getpoly。
  • 通过一些左右都有空格的加号或减号，将整行字符串分割成一些子串，扔到单项式的读入函数中。
• 重载运算符加和乘，多项式的加法和乘法。
• unique 函数，用于多项式的排序和去重。
  • 在这里面使用单项式中重载的小于和等于，可以像一般的数组那样手动去重。
  • 如果某一项系数为 0，就直接丢掉。
  • 函数最后要 resize 重设 vector 大小。
  • 我在多项式的乘法和加法最后，以及输出函数的最开头，同时调用了 unique，但是删去输出函数开头的 unique 或者删去运算最后的 unique，都会出问题，于是都加上了（不知道为什么，如果看出来的话求评论区解答）。
• 多项式的输出函数 print。
  • 如果多项式为空，输出 0 并直接返回。
  • 调用输出单项式的函数，将多项式的每一项输出。
  • 如果不是第一项且系数非负，输出一个加号连接该项和前一项（如果系数为负数的话会在输出单项式的部分输出）。

想不到别的坑点了。

Code

#include<bits/stdc++.h>
#define int long long
#define pb emplace_back
#define Fr(i,il,ir) for(int i=(il);i<(ir);++i)
using namespace std;

struct mono{
    int v,a[26];
    mono(){ v=0;memset(a,0,sizeof(a)); }
    bool operator < (mono rc)const{ if(!v||!rc.v) return v<rc.v; Fr(i,0,26) if(a[i]!=rc.a[i]) return a[i]<rc.a[i];return 0; }
    bool operator == (mono rc)const{ if(!v||!rc.v) return v==rc.v; Fr(i,0,26) if(a[i]!=rc.a[i]) return 0; return 1; }
    mono operator * (mono rc)const{ mono res;res.v=v*rc.v; Fr(i,0,26) res.a[i]=a[i]+rc.a[i]; return res; }
    void printmono(){//输出单项式
        if(abs(v)!=1) printf("%lld",v);
        if(v==-1) putchar('-'),v=1;
        bool printflag=false;
        Fr(i,0,26) if(a[i]){
            printflag=true,putchar('A'+i);
            if(a[i]!=1) printf("^%lld",a[i]);
        }
        if(!printflag&&v==1) printf("%lld",v);
    }
};
mono getmo(string s)//获取单项式
{
    mono ret;int len=s.size();
    //获取系数
    int i,x=0,f=1;bool flag=false;
    for(i=0;i<len&&!isupper(s[i]);i++)
        if(s[i]=='-') f=-f;
        else if(isdigit(s[i])) x=x*10+(s[i]^48),flag=true; 
    ret.v=flag?x*f:f;
    //指数累加
    int nw=-1;x=0,f=1,flag=false;
    for(;i<len;++i)
        if(isupper(s[i])){
            if(~nw) ret.a[nw]+=flag?x*f:f;
            nw=s[i]-'A',x=0,f=1,flag=false;
        }
        else if(s[i]=='^') flag=true;
        else if(s[i]=='-') f=-f;
        else if(isdigit(s[i])) x=x*10+(s[i]^48);
    if(~nw) ret.a[nw]+=flag?x*f:f;
    return ret;
}
struct polyno{
    vector<mono> ve;
    void unique()
    {
        if(!ve.size()) return;
        sort(ve.begin(),ve.end());int tot=-1;
        for(auto x:ve) if(x.v)
            if(~tot&&x==ve[tot]) ve[tot].v+=x.v;
            else ve[++tot]=x;
        ve.resize(tot+1);
    }
    void getpoly(){//获取多项式
        string s,t="";getline(cin,s);
        s=" "+s+" ";int len=s.size();//为了循环中 i-1 和 i+1 不越界，前后各加一个空格。
        Fr(i,0,len)//分割成单项式（string t）加进去
            if((s[i]=='+'||s[i]=='-')&&s[i-1]==' '&&s[i+1]==' '){
                if(t!="") ve.pb(getmo(t)),t="";
                if(s[i]=='-') t=t+s[i];
            }else if(s[i]!=' ') t=t+s[i];
        if(t!="") ve.pb(getmo(t));
        unique();
    }
    polyno operator + (polyno rc)const{
        polyno res;
        for(auto x:ve) res.ve.pb(x);
        for(auto x:rc.ve) res.ve.pb(x);
        res.unique();return res;
    }
    polyno operator * (polyno rc)const{
        polyno res;
        for(auto x:ve) for(auto y:rc.ve) res.ve.pb(x*y);
        res.unique();return res;
    }
    void print(){//多项式输出
        unique();
        if(!ve.size()){ puts("0"); return; }
        Fr(i,0,ve.size()){
            if(i&&ve[i].v>=0) putchar('+');
            ve[i].printmono();
        }putchar('\n');
    }
}A,B,C,D;
signed main(){
    A.getpoly();B.getpoly();
    C=A+B,D=A*B;C.print(),D.print();
    return 0;
}