题解 | #多项式输出#

题目链接

题目描述

给定一元 $n$ 次多项式 $P(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0$ ，其中 $a_n \neq 0$ ，系数 $a_i \in [-100, 100]$ 。请按如下规则将多项式输出为字符串：

从高次到低次依次输出。
系数为 0 的项完全省略。
当系数为 1 或 -1 且次数 $>0$ 时，省略系数的绝对值 1。
次数为 0 仅输出常数；次数为 1 输出 x；次数 $>1$ 输出 x^次数。
首项若系数为正，不输出前导 +；后续正系数项前需加 +，负系数项加 -。

输入描述

第一行输入整数 $n$ ，表示多项式次数。第二行输入 $n+1$ 个整数，依次为各项系数 $a_n, a_{n-1}, \dots, a_0$ 。

输出描述

在一行中输出格式化后的多项式字符串。

样例

输入

5
100 -1 1 -3 0 10

输出

100x^5-x^4+x^3-3x^2+10

解题思路

本题的核心是根据一系列复杂的规则拼接字符串。为了正确处理各项的符号（+ 或 -）以及系数和指数的显示，我们可以从高次项到低次项遍历所有系数，并使用一个标志位来判断当前项是否为要输出的“首项”。

算法步骤：

读入多项式的次数 $n$ 和 $n+1$ 个系数。
设置一个布尔标志位 $is\_first\_term = \text{true}$ ，用于标记即将输出的第一个非零项。
从高到低遍历每一项（次数 $i$ 从 $n$ 到 0）： a. 获取当前项的系数 $a_i$ 。 b. 如果系数 $a_i$ 为 0，则直接跳过当前项。 c. 处理符号： - 如果 $is\_first\_term$ 为 true： - 如果 $a_i < 0$ ，输出一个负号 -。 - 此时无论系数正负，都已经处理完符号，可以将 $is\_first\_term$ 置为 false。 - 如果 $is\_first\_term$ 为 false： - 如果 $a_i > 0$ ，输出 +。 - 如果 $a_i < 0$ ，输出 -。 d. 处理系数的绝对值： - 获取系数的绝对值 $|a_i|$ 。 - 如果 $|a_i| \neq 1$ 或者当前是常数项（ $i=0$ ），则输出 $|a_i|$ 。 e. 处理变量和指数： - 如果次数 $i > 0$ （不是常数项）： - 输出 x。 - 如果次数 $i > 1$ ，输出 ^ 和次数 $i$ 。
遍历完成后，如果 $is\_first\_term$ 仍然为 true（意味着所有系数都为0），则需要额外输出一个 0。（根据题意 $a_n \neq 0$ ，此情况主要用于代码的鲁棒性）。

这种方法通过一个简单的标志位，将复杂的首项符号逻辑与后续项的逻辑分离开，使得代码结构清晰。

代码

c++
java
python

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

using namespace std;

int main() {
    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 coeff = a[i];
        int degree = n - i;

        if (coeff == 0) continue;

        // 处理符号
        if (coeff > 0 && !is_first_term) {
            cout << "+";
        }
        if (coeff < 0) {
            cout << "-";
        }
        
        // 处理系数绝对值
        int abs_coeff = abs(coeff);
        if (abs_coeff != 1 || degree == 0) {
            cout << abs_coeff;
        }

        // 处理变量和指数
        if (degree > 0) {
            cout << "x";
            if (degree > 1) {
                cout << "^" << degree;
            }
        }
        is_first_term = false;
    }

    if (is_first_term) { // 如果所有系数都是0
        cout << "0";
    }
    cout << '\n';

    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 is_first_term = true;

        for (int i = 0; i <= n; i++) {
            int coeff = a[i];
            int degree = n - i;

            if (coeff == 0) continue;

            // 处理符号
            if (coeff > 0 && !is_first_term) {
                System.out.print("+");
            }
            if (coeff < 0) {
                System.out.print("-");
            }
            
            // 处理系数绝对值
            int abs_coeff = Math.abs(coeff);
            if (abs_coeff != 1 || degree == 0) {
                System.out.print(abs_coeff);
            }

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

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

# -*- coding: utf-8 -*-

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

is_first_term = True
result = []

for i in range(n + 1):
    coeff = a[i]
    degree = n - i
    
    if coeff == 0:
        continue

    term_str = ""
    
    # 处理符号
    if is_first_term:
        if coeff < 0:
            term_str += "-"
    else:
        if coeff > 0:
            term_str += "+"
        else:
            term_str += "-"
    
    is_first_term = False
    
    # 处理系数绝对值
    abs_coeff = abs(coeff)
    if abs_coeff != 1 or degree == 0:
        term_str += str(abs_coeff)
        
    # 处理变量和指数
    if degree > 0:
        term_str += "x"
        if degree > 1:
            term_str += f"^{degree}"
            
    result.append(term_str)

if not result: # 如果所有系数都是0
    print("0")
else:
    print("".join(result))

算法及复杂度

算法：模拟、字符串拼接
时间复杂度：我们需要遍历 $n+1$ 个系数，对每个系数进行常数次判断和字符串操作。因此，总时间复杂度为 $O(n)$ 。
空间复杂度：我们用一个数组存储 $n+1$ 个系数，因此空间复杂度为 $O(n)$ 。