PAT A1002：A+B for Polynomials

简单模拟题之多项式加法

本文作者：MowChan · 发布日期：2021/01/23 · 阅读时长：3 分钟

题目内容

This time, you are supposed to find $A+B$ where $A$ and $B$ are two polynomials.

Input Specification:

Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial:

$K$ $N_1 a_{N_1} N_2 a_{N_2} \cdots N_K a_{N_K}$

where $K$ is the number of nonzero terms in the polynomial, $N_i$ and $a_{N_i} (i=1,2,\cdots,K)$ are the exponents and coefficients, respectively. It is given that $1\leqslant K\leqslant 10$，$0\leqslant N_K < \cdots < N_2 < N_1 \leqslant 1000$.

Output Specification:

For each test case you should output the sum of $A$ and $B$ in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate to 1 decimal place.

Sample Input:

2 1 2.4 0 3.2
2 2 1.5 1 0.5

Sample Output:

3 2 1.5 1 2.9 0 3.2

题目要点

本题 25 分，是比较简单的模拟题。在输入时，Python可以不用考虑给定的$K$，直接用数组切片隔位取指数列表、系数列表，再用zip()构造字典。

重点需要考虑的是如何将多项式的指数和对应系数映射。C/C++可以用数组下标作为指数，数组浮点数值为对应系数。这里Python使用字典比较方便，而且考虑到两个多项式的指数项不一定相同，在求和时要指数项系数对应相加，Python可以使用集合的求并集|运算符实现。

注意，测试点6是非零系数项个数，也就是$K$为0的情况，这时候只输出0。如果有多余空格会出现“格式错误”。

AC 源代码

ins1 = input()
ins2 = input()

a = dict(zip( map(int, ins1.split()[1::2]), map(float, ins1.split()[2::2]) ))
b = dict(zip( map(int, ins2.split()[1::2]), map(float, ins2.split()[2::2]) ))
poly = {}

for key in (a.keys() | b.keys()):
    total = a.get(key, 0.0) + b.get(key, 0.0)
    if total != 0.0:
        poly[key] = total

poly = sorted(poly.items(), reverse=True)
line = ' '.join(map(lambda x: '{:d} {:.1f}'.format(*x), poly))
k = len(poly)

if k:
    print(k, line)
else:
    print(0)

参考来源

柳神的C++代码：https://www.liuchuo.net/archives/1890