题解：UVA126 The Errant Physicist

b__b · 2025-04-25 22:22:24 · 题解

~太好了是大模拟我们没救了~

此题难点在于输入与输出，~以及克服奇怪的题面和奇怪的翻译~。

题面简述

有若干个测试数据，每一个测试数据有两个行，分别代表两个多项式，将这两个多项式相乘。输入格式已比较透彻，只需注意 x 与 y 的输入顺序可能调换。

每一个测试数据输出两行，第一行为指数行，下一行为底数行。

第一行包含所有指数，相对于其余行适当定位信息。

实现

可以先将第一行的多项式输入完成，接着~由人教版八年级上册数学书~可得 一般的，单项式与多项式相乘，就是用单项式去乘多项式的每一项，再把所得的积相加。

一般的，多项式与多项式相乘，先用一个多项式的每一项乘另一个多项式的每一项，再把所得的积相加。

因此我们只需要在第二行不断输入单项式，遍历原多项式的每一项单项式相乘后放入结果。

需要进行指数的判重，可以用 map 实现，找到指数相同的单项式后将系数相加，因为 ax^m+bx^m=(a+b)x^m（其中 a,b 均为常整数），合并后可能会出现系数为 0 的情况，输出时要把这些系数为 0 的单项式忽略。

输出行中的项必须按 x 的幂次降序排列，对于给定的幂次按照 y 的幂次递增的顺序。

例如，对于 4y^{17}-1-x^5，

1. 由于 -x^5 是这个多项式内 x 的次数最高的单项式，因此将 -x^5 放到最前面。
2. 因为 -1 可看作 -y^0，因此这是这个多项式内 y 的次数最低的单项式，因此将 -1 放到第二个。
3. 将 4y^{17} 放到最后。

综上所述，这个多项式的排序结果为 -x^5-1+4y^{17}。

写成 C++ 代码可表示为：（xcs 为 x 的次数，ycs 为 y 的次数）

if (a.xcs > b.xcs) return 1;
else if (a.xcs < b.xcs) return 0;
else return a.ycs < b.ycs;

第一行包含所有指数，相对于其余行适当定位信息。

个人感觉是本题最难的地方，理解和实现都有点困难（再加上奇怪的输出样例就更难了）。

下文中 \mathrm{ans1} 为第一行的输出的缓冲，\mathrm{ans2} 为第二行的输出的缓冲，\mathrm{ansind} 为输出的字符数量，直接说输出时指输出到 \mathrm{ans2}。

用上文已排序的 -x^5-1+4y^{17} 举例，

1. 先输出 -x^5，

   如果第一项的系数为负，则在第一列中以一元减号开头，中间没有空白栏。