题解 | #多项式输出#

题目链接

多项式输出

题目描述

给定一个一元 $n$ 次多项式 $P(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0$ ，请按照一系列特定规则将其输出为字符串。

格式化规则：

顺序: 从高次到低次（ $n$ 到 $0$ ）依次输出每一项。
零系数: 系数为 $0$ 的项完全省略。
系数 1 和 -1: 当系数为 $1$ 或 $-1$ 且该项次数大于 $0$ 时，省略系数的数字 1。例如 x^2 而不是 1x^2，-x 而不是 -1x。
次数:
- 次数为 $0$ （常数项）时，只输出系数。
- 次数为 $1$ 时，输出 x，而不是 x^1。
- 次数大于 $1$ 时，输出 x^ 加上次数，例如 x^5。
符号:
- 首项：若系数为正，不输出 + 号；若为负，则输出 - 号。
- 非首项：若系数为正，前缀 +；若为负，前缀 -。

输入可能包含多组测试数据。

解题思路

本题的核心是模拟多项式的格式化过程。我们需要从最高次项开始遍历到常数项，并根据题目的规则逐项构建输出字符串。

我们可以设置一个布尔变量 is_first_term，用于判断当前处理的是否为第一个非零系数的项，这对正确处理前导符号至关重要。

详细步骤如下：

初始化 is_first_term = true。
循环遍历多项式的每一项，从最高次 $n$ 降到 $0$ 。设当前处理的项为 $a_i x^i$ 。
处理系数 $a_i$ ：
- 如果 $a_i = 0$ ，则该项被完全忽略，直接进入下一次循环。
处理符号：
- 如果 is_first_term 为 true：
  - 此时是第一个要输出的项。如果 $a_i < 0$ ，我们输出一个负号 -。
  - 然后，将 is_first_term 置为 false，因为后续的项都不再是首项。
- 如果 is_first_term 为 false：
  - 如果 $a_i > 0$ ，输出 +。
  - 如果 $a_i < 0$ ，输出 -。
处理系数的绝对值：
- 获取系数的绝对值 $|a_i|$ 。
- 根据规则，当 $|a_i| = 1$ 且次数 $i > 0$ 时，系数的数字 1 需要省略。在其他所有情况下（即 $|a_i| \ne 1$ 或 $i = 0$ ），都需要输出 $|a_i|$ 。
处理变量和指数：
- 如果次数 $i > 0$ ，说明有变量 x。
  - 输出 x。
  - 如果次数 $i > 1$ ，则还需输出 ^ 和次数 $i$ 。
处理全零多项式：
- 如果循环结束后 is_first_term 仍然为 true，说明所有系数都为零。在这种情况下，需要按题意输出一个 0。

通过以上步骤，即可将任意多项式格式化为符合要求的字符串。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 0; i <= n; ++i) {
        cin >> a[i];
    }

    bool is_first_term = true;
    for (int i = 0; i <= n; ++i) {
        int power = n - i;
        int coeff = a[i];

        if (coeff == 0) {
            continue;
        }

        // 符号
        if (is_first_term) {
            if (coeff < 0) {
                cout << "-";
            }
        } else {
            if (coeff > 0) {
                cout << "+";
            } else {
                cout << "-";
            }
        }

        // 系数绝对值
        int abs_coeff = abs(coeff);
        if (abs_coeff != 1 || power == 0) {
            cout << abs_coeff;
        }

        // 变量和指数
        if (power > 0) {
            cout << "x";
            if (power > 1) {
                cout << "^" << power;
            }
        }
        
        is_first_term = false;
    }
    
    if (is_first_term) { // 如果所有系数都是0
        cout << 0;
    }
    
    cout << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            a[i] = sc.nextInt();
        }

        boolean isFirstTerm = true;
        for (int i = 0; i <= n; i++) {
            int power = n - i;
            int coeff = a[i];

            if (coeff == 0) {
                continue;
            }

            // 符号
            if (isFirstTerm) {
                if (coeff < 0) {
                    System.out.print("-");
                }
            } else {
                if (coeff > 0) {
                    System.out.print("+");
                } else {
                    System.out.print("-");
                }
            }

            // 系数绝对值
            int absCoeff = Math.abs(coeff);
            if (absCoeff != 1 || power == 0) {
                System.out.print(absCoeff);
            }

            // 变量和指数
            if (power > 0) {
                System.out.print("x");
                if (power > 1) {
                    System.out.print("^" + power);
                }
            }
            
            isFirstTerm = false;
        }

        if (isFirstTerm) { // 如果所有系数都是0
            System.out.print(0);
        }
        
        System.out.println();
    }
}

import sys

def solve():
    n = int(input())
    a = list(map(int, input().split()))

    is_first_term = True
    result_parts = []

    for i in range(n + 1):
        power = n - i
        coeff = a[i]

        if coeff == 0:
            continue

        term = ""
        # 符号
        if is_first_term:
            if coeff < 0:
                term += "-"
        else:
            if coeff > 0:
                term += "+"
            else:
                term += "-"
        
        # 系数绝对值
        abs_coeff = abs(coeff)
        if abs_coeff != 1 or power == 0:
            term += str(abs_coeff)

        # 变量和指数
        if power > 0:
            term += "x"
            if power > 1:
                term += f"^{power}"

        result_parts.append(term)
        is_first_term = False

    if not result_parts:
        print(0)
    else:
        print("".join(result_parts))

solve()

算法及复杂度

算法：模拟
时间复杂度：对于每一组输入，我们需要读取 $n+1$ 个系数，并遍历它们一次。因此，时间复杂度为 $\mathcal{O}(n)$ 。
空间复杂度：需要一个数组存储 $n+1$ 个系数，因此空间复杂度为 $\mathcal{O}(n)$ 。