题目链接：https://www.luogu.org/problemnew/show/P2281
题目的意思很简单，输入两个系数、指数都是整数，变量都是大写字母的多项式，求他们的加法结果和乘法结果。
按照题目的意思模拟，先设计我们需要的类。
单项式
一个单项式由系数以及各个变量的指数组成，为了简单起见他们都是带符号数。
多项式
一个多项式由一个单项式的向量组成。
然后实现一些细节就可以了：
#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<<"...
"<<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]=' ';
}
if(s[i]!=' '&&s[i]!='
') {
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]=' ';
}
if(s[i]!=' '&&s[i]!='
') {
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;
}