UVa 126 The Errant Physicist

题目概述

著名物理学家Alfred E Neuman\texttt{Alfred E Neuman}Alfred E Neuman在处理涉及xxx和yyy多项式乘法的问题时经常出错，导致核弹头提前引爆，摧毁了五座大城市和几片雨林。
你的任务是编写一个程序，正确计算两个多项式的乘积，以避免进一步的灾难。

输入

• 输入数据包含若干对行，每行最多包含808080个字符。
• 最后一行的第一个字符是#，表示输入结束。
• 每行输入一个没有空格、没有显式乘方运算符的多项式。
• 指数为正非零无符号整数，系数为整数（可为负）。
• 指数和系数的绝对值均不超过100100100。
• 每一项最多包含一个xxx因子和一个yyy因子。

输出

• 对于每一对多项式，计算乘积并输出两行：第一行输出指数，第二行输出对应的项。
• 两行长度相等，较短的末尾用空格补齐。
• 输出格式需满足以下规则：
  1. 项按xxx的降序排列，xxx相同时按yyy的升序排列。
  2. 同类项合并。
  3. 系数为零的项不输出。
  4. 系数为111时省略（常数项111除外）。
  5. 指数为111时省略。
  6. x0x^0x0和y0y^0y0因子省略。
  7. 项间的加减号前后各有一个空格。
  8. 首项系数为负时，第一列输出负号，无空格；否则从第一列开始输出系数。

解题思路

本题的核心是多项式乘法的模拟与格式化输出。我们可以将问题分解为以下几个步骤：

1. 解析输入
   将每行输入按+或-拆分为单独的项。由于输入没有空格，且可能以正号或负号开头，我们需要为每项补上符号以便后续处理。

2. 解析单项式
   对于每一项，需要提取出：

   • 符号（正或负）
   • 系数（整数）
   • xxx的指数（默认为000）
   • yyy的指数（默认为000）

   注意系数可能省略（即为111），指数也可能省略（即为111）。解析时需要处理这些情况。

3. 多项式乘法
   使用二维数组coefficients[i][j]表示xiyjx^i y^jxiyj项的系数。
   遍历第一个多项式的每一项和第二个多项式的每一项，计算它们相乘后的系数，并累加到对应位置。

4. 格式化输出
   输出分为两行：

   • 第一行输出指数，即每个项的xxx和yyy的指数，按规则对齐。
   • 第二行输出具体的项（包括系数、变量和符号）。

   输出时需按xxx降序、yyy升序遍历coefficients数组。对于每个非零系数项：

   • 处理符号（首项特殊处理）
   • 输出系数（注意省略111）
   • 输出xxx和yyy（注意指数为111时省略）
   • 确保两行对齐，指数和变量位置对应

5. 对齐处理
   由于第一行只输出数字，第二行输出变量和符号，为了保证两行等长且对齐，需要计算每个数字占用的宽度，并在输出时用空格补齐。

代码实现

// The Errant Physicist// UVa ID: 126// Verdict: Accepted// Submission Date: 2020-05-08// UVa Run Time: 0.000s//// 版权所有（C）2020，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;#defineMAXN210intcoefficients[MAXN][MAXN];intpart1[4],part2[4];voidgetItem(vector<string>&c,string line){if(line[0]!='-'&&line[0]!='+')line='+'+line;while(true){intplusIndex=line.rfind('+');intminusIndex=line.rfind('-');if(plusIndex>=0||minusIndex>=0){c.push_back(line.substr(max(plusIndex,minusIndex)));line=line.substr(0,max(plusIndex,minusIndex));}elsebreak;}}intgetExponent(string&item,charnext){intexponent=0,haveExponent=0;item=item.substr(1);while(item.length()&&item[0]!=next){haveExponent=1;exponent=exponent*10+item[0]-'0';item=item.substr(1);}if(!haveExponent)exponent=1;returnexponent;}voidgetPart(string item,intpart[]){// 解析符号。part[0]=(item[0]=='-'?-1:1);if(item[0]=='+'||item[0]=='-')item=item.substr(1);// 获取系数。intcoefficient=0;inthaveDigit=0;while(item.length()&&item[0]>='0'&&item[0]<='9'){haveDigit=1;coefficient=coefficient*10+item[0]-'0';item=item.substr(1);}part[1]=(haveDigit==0?1:coefficient);// 获取指数。if(item.length()){charstart=item[0];intexponent1=0,exponent2=0;if(start=='x'||start=='y'){charnext=(start=='x'?'y':'x');exponent1=getExponent(item,next);if(item.length()>0)exponent2=getExponent(item,next);}part[2]=start=='x'?exponent1:exponent2;part[3]=start=='x'?exponent2:exponent1;}}// 将两个项目相乘。voidmultiply(string term1,string term2){memset(part1,0,sizeof(part1));memset(part2,0,sizeof(part2));getPart(term1,part1);getPart(term2,part2);coefficients[part1[2]+part2[2]][part1[3]+part2[3]]+=part1[0]*part1[1]*part2[0]*part2[1];}stringspace(intn){stringstream ss;string line;ss<<n;ss>>line;returnstring(line.length(),' ');}voidoutput(boolprintExponent,intn){if(printExponent)cout<<n;elsecout<<space(n);}boolprint(boolprintExponent){boolfirstItemPrinted=false;for(inti=200;i>=0;i--)for(intj=0;j<=200;j++)if(coefficients[i][j]!=0){if(firstItemPrinted==false){if(coefficients[i][j]<0)cout<<(printExponent?" ":"-");firstItemPrinted=true;}else{cout<<" ";cout<<(printExponent?" ":((coefficients[i][j]>0)?"+":"-"));cout<<" ";}if(fabs(coefficients[i][j])>1)output(!printExponent,fabs(coefficients[i][j]));elseif(i==0&&j==0)cout<<(printExponent?" ":"1");if(i>0)cout<<(printExponent?" ":"x");if(i>1)output(printExponent,i);if(j>0)cout<<(printExponent?" ":"y");if(j>1)output(printExponent,j);}returnfirstItemPrinted;}intmain(intac,char*av[]){string line;vector<string>polynomial1,polynomial2;while(getline(cin,line),line!="#"){polynomial1.clear();polynomial2.clear();getItem(polynomial1,line);getline(cin,line);getItem(polynomial2,line);memset(coefficients,0,sizeof(coefficients));for(inti=0;i<polynomial1.size();i++)for(intj=0;j<polynomial2.size();j++)multiply(polynomial1[i],polynomial2[j]);print(true);cout<<'\n';boolflag=print(false);if(!flag)cout<<0;cout<<'\n';}return0;}

总结

本题主要考察字符串解析、多项式乘法模拟和格式化输出。需要注意的细节非常多，尤其是输出格式的严格要求。通过合理设计数据结构和遍历顺序，可以高效地完成计算和输出。代码中使用二维数组存储系数，解析函数提取每项信息，乘法过程累加系数，最后按规则输出两行，确保对齐。