

DS线性表—多项式运算

时间限制: 1 Sec 内存限制: 128 MB

题目描述

对于一元多项式$p(x) = p_{0} + p_{1}x + p_{2}x^{2} + … + p_{n}x^{n}$，每个项都有系数和指数两部分，例如$p_{2}x^{2}$的系数为$p_{2}$,指数为2。

编程实现两个多项式的加法、减法、乘法。

例如：多项式$A = 5 + x + 2x^{2}$，多项式$B = -x + 4x^{4}$，计算：

$A + B = 5 + 2x^{2} + 4x^{4}$

$A - B = 5 + 2x + 2x^{2} - 4x^{4}$

$A * B = -5x - x^{2} - 2x^{3} +20x^{4} + 4x^{5} + 8x^{6}$

实现方法不限，可以使用容器。

输入

测试次数t，每组测试数据格式如下:

第一行，第一个多项式A的项数n（n>0)

第二行，A的每一项的系数 指数（共2n个数字，均为整数，以空格分隔）

第三行，第一个多项式B的项数m（m>0)

第四行，B的每一项的系数 指数（共2m个数字，均为整数，以空格分隔）

输出

对每组测试数据，输出五行，分别是：

多项式A

多项式B

A+B

A-B

A*B

每组测试数据间以空行分隔。

多项式输出格式：项之间用+连接，例如，1+x 。但后一项系数为负数，不输出+号，如: $1 + (-2x^{2})$，输出为1-2x^2。

如果该项：系数为0，不输出，但表达式只有一项0，要输出。

指数为0，不输出x^0。指数为负数，例如-3，输出x^(-3)。指数为正数，例如3，输出x^3。指数为1，输出x。

以上一句话总结：和数学中多项式表示相同，x的指数加^表示。

样例输入

2
2
1 0 1 1
2
-1 0 -1 1
3
5 0 1 1 2 2
2
-1 1 4 4

样例输出

1+x
-1-x
0
2+2x
-1-2x-x^2

5+x+2x^2
-x+4x^4
5+2x^2+4x^4
5+2x+2x^2-4x^4
-5x-x^2-2x^3+20x^4+4x^5+8x^6

提示

解决方案

#include <iostream>
#include <vector>
#include <algorithm>

class Poly {
public:
    struct Node {
        int coefficient, exponent;

        Node() = default;

        Node(int coefficient, int exponent) : coefficient(coefficient), exponent(exponent) {}

        Node operator+(const Node &rhs) {
            return {this->coefficient + rhs.coefficient, this->exponent};
        }

        bool operator<(const Node &rhs) const {
            return this->exponent < rhs.exponent;
        }

        friend std::ostream &operator<<(std::ostream &os, const Node &rhs) {
            if (rhs.coefficient == -1 && rhs.exponent != 0) {
                os << '-';
            } else if (rhs.coefficient == 1 && rhs.exponent != 0) {
            } else {
                os << rhs.coefficient;
            }
            if (rhs.exponent == 0) {
                return os;
            } else if (rhs.exponent == 1) {
                return os << 'x';
            }
            os << "x^";
            if (rhs.exponent < 0) {
                return os << '(' << rhs.exponent << ')';
            } else {
                return os << rhs.exponent;
            }
        }
    };

    explicit Poly(int size) : poly(size) {}

    explicit Poly(std::vector<Node> &poly) : poly(poly) {}

    void setFromCin() {
        for (auto &item : this->poly) {
            std::cin >> item.coefficient >> item.exponent;
        }
    }

    Poly operator+(const Poly &rhs) {
        std::vector<Node> polyToReturn;
        size_t i1 = 0, i2 = 0;
        while (true) {
            const Node &node1 = this->poly[i1], &node2 = rhs.poly[i2];
            if (i1 == this->poly.size() && i2 == rhs.poly.size()) {
                break;
            }
            if (i1 == this->poly.size()) {
                polyToReturn.emplace_back(node2);
                i2 += 1;
                continue;
            }
            if (i2 == rhs.poly.size()) {
                polyToReturn.emplace_back(node1);
                i1 += 1;
                continue;
            }
            if (node1.exponent < node2.exponent) {
                polyToReturn.emplace_back(node1);
                i1 += 1;
            } else if (node1.exponent == node2.exponent) {
                polyToReturn.emplace_back(Node(node1.coefficient + node2.coefficient, node1.exponent));
                i1 += 1;
                i2 += 1;
            } else {
                polyToReturn.emplace_back(node2);
                i2 += 1;
            }
        }
        return Poly(polyToReturn);
    }

    Poly operator-(const Poly &rhs) {
        Poly rhsReversed(rhs);
        for (auto &item : rhsReversed.poly) {
            item.coefficient = -item.coefficient;
        }
        return (*this + rhsReversed);
    }

    Poly operator*(const Poly &rhs) {
        std::vector<Node> polyToReturn;
        for (auto i1 : this->poly) {
            for (auto i2 : rhs.poly) {
                polyToReturn.emplace_back(Node(i1.coefficient * i2.coefficient, i1.exponent + i2.exponent));
            }
        }
        for (size_t i1 = 0; i1 < polyToReturn.size(); ++i1) {
            for (size_t i2 = i1 + 1; i2 < polyToReturn.size(); ++i2) {
                if (polyToReturn[i1].exponent == 0 || polyToReturn[i2].exponent == 0) {
                    continue;
                }
                if (polyToReturn[i1].exponent == polyToReturn[i2].exponent) {
                    polyToReturn[i1].coefficient += polyToReturn[i2].coefficient;
                    polyToReturn.erase(polyToReturn.begin() + i2);
                }
            }
        }
        std::sort(polyToReturn.begin(), polyToReturn.end());
        return Poly(polyToReturn);
    }

    friend std::ostream &operator<<(std::ostream &os, const Poly &rhs) {
        auto polyToPrint = rhs.poly;
        polyToPrint.erase(std::remove_if(polyToPrint.begin(), polyToPrint.end(),
                                         [](Node &node) { return node.coefficient == 0; }), polyToPrint.end());
        std::sort(polyToPrint.begin(), polyToPrint.end());
        if (polyToPrint.empty()) {
            return os << '0';
        }
        os << polyToPrint.front();
        for (size_t i = 1; i < polyToPrint.size(); ++i) {
            if (polyToPrint[i].coefficient > 0) {
                os << '+';
            }
            os << polyToPrint[i];
        }
        return os;
    }

private:
    std::vector<Node> poly;
};

int main() {
    int T;
    std::cin >> T;

    while (T--) {
        int size;
        std::cin >> size;
        Poly lhs(size);
        lhs.setFromCin();
        std::cout << lhs << std::endl;
        std::cin >> size;
        Poly rhs(size);
        rhs.setFromCin();
        std::cout << rhs << std::endl;
        std::cout << lhs + rhs << std::endl;
        std::cout << lhs - rhs << std::endl;
        std::cout << lhs * rhs << std::endl;
        std::cout << std::endl;
    }

    return 0;
}

评论