题目信息

平台：牛客
题目：多项式输出
难度：简单
时间限制：1 秒 / 空间限制：256M

题目描述

给定一元次多项式

其中，系数满足。

请按如下规则将多项式输出为字符串：

从高次到低次依次输出；
系数为的项 完全省略；
对于次数大于等于的项，若其系数为或，则省略系数的绝对值（常数项即使为或也应完整输出）；
次数为仅输出常数；次数为输出 x；次数输出 x^k；
输出的第一个非零项（即最高次项）若系数为正，不输出前导加号；后续正系数项前需加 +，负系数项加 -。

输入描述

第一行输入整数，表示多项式次数。

第二行输入个整数，依次为次项到次项（常数项）的系数。

输出描述

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

初步思路

这题本质是按次数从高到低拼接字符串，不涉及任何复杂算法。

1. 次数与下标的对应关系

输入的系数顺序就是 an, an-1, ..., a1, a0，所以第 i 个系数（下标从 0 开始）对应的次数为：

因此直接顺序遍历数组即可，天然满足从高次到低次的要求，不需要排序。

2. 每一项按四步拼装

对每个非零系数，依次做四件事：

步骤	处理内容	依据规则
① 判零跳过	`value == 0` 时 `continue`	系数为 0 的项完全省略
② 输出符号	用 `first` 标记是否为第一个非零项	最高次项为正不加前导 `+`
③ 输出系数	`power > 0` 且绝对值为 1 时省略	省略系数绝对值 1
④ 输出变量	`x` / `x^k` / 常数	按次数决定格式

3. 符号处理：用 `first` 标记

这是本题最容易出错的地方。符号规则看似复杂，用一个 first 布尔量就可以统一：

if (first) {
    if (value < 0) answer += "-";  // 最高次项为正：不输出任何符号
    first = false;                 // 之后无论跳过多少个 0，都不再进入该分支
} else {
    answer += (value > 0) ? "+" : "-";
}

关键点：first 是在输出第一个非零项之后才置为 false。中间即使连续跳过多个零系数项，first 状态也不会被破坏，所以不会出现「+x^2 + x」这种多余的加号。

4. 系数 1 的省略条件

题目要求「次数」才允许省略系数，而常数项必须完整输出。所以判断必须带上 power 条件：

if (power == 0) {
    answer += to_string(absoluteValue);   // 常数项：1 和 -1 也要完整输出
} else {
    if (absoluteValue != 1) {             // 非常数项：绝对值为 1 时省略系数
        answer += to_string(absoluteValue);
    }
    // ... 输出 x 和次数
}

例如 -x^2 + x 中的 -1x^2，常数位置的 +1 却不能省略成 +。

5. 进阶写法：边读边处理

前面的实现先把个系数存进数组，再遍历输出。但注意一个关键事实：

输入顺序恰好就是输出顺序。读到第个系数时，就已知它对应次项，可以立刻决定这一项怎么写。

因此那个系数数组是多余的，可以边读边处理，空间复杂度降到（不计输出字符串）。

两种写法对比

维度	先存后处理	边读边处理
时间复杂度
空间复杂度	（系数数组）	****（仅答案字符串）
代码结构	两段循环	读与写合并在同一循环
适用场景	需要复用系数时	本题这种「流式」输入

C++ 实现：

#include <iostream>
#include <string>

using namespace std;

int main() {
    // 边读边写：输入顺序即输出顺序，无需存储系数数组
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    string ans;
    bool first = true;

    for (int i = 0; i <= n; ++i) {
        int value;
        cin >> value;

        int power = n - i;

        if (value == 0) {
            continue;
        }

        if (first) {
            if (value < 0) {
                ans += "-";
            }
            first = false;
        } else {
            ans += (value > 0) ? "+" : "-";
        }

        int absoluteValue = abs(value);

        if (power == 0) {
            ans += to_string(absoluteValue);
        } else {
            if (absoluteValue != 1) {
                ans += to_string(absoluteValue);
            }
            ans += "x";
            if (power >= 2) {
                ans += "^" + to_string(power);
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

关于「边读边写会不会慢」

常见疑问是：不缓存结果、每读一个就写一次，速度会不会下降？

cout 本身是带缓冲的，只有 endl 或 flush 才会强制刷新缓冲区。上面代码用的是 '\n' 而非 endl，写入几乎全在内存缓冲区完成，并不会每一步都落盘。

真正需要注意的是另一件事——cin 默认与 cout 绑定（tie）。当读写交替时，cin 会在每次读取前先 flush 输出流，反复冲刷缓冲区导致变慢。所以上面代码显式加了两行：

ios::sync_with_stdio(false);  // 断开与 C stdio 的同步
cin.tie(nullptr);             // 解除 cin 对 cout 的自动绑定

结论：边读边处理不会因为缺少缓存而变慢，反而省掉了系数数组，代码也更简洁。

算法分析

核心：按次数从高到低顺序拼接字符串
技巧：用 first 标记统一处理前导符号，用 power 区分常数项与非常数项
时间复杂度：，每个系数处理一次
空间复杂度：（存系数数组与结果字符串）；采用边读边处理可降至

代码实现

以下给出 C++、Python、Java、Go、Rust 五种语言的实现，逻辑完全一致。切换上方的标签即可对比。

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

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> coefficients(n + 1);

    for (int i = 0; i <= n; ++i) {
        cin >> coefficients[i];
    }

    string ans;
    bool first = true;

    for (int i = 0; i <= n; ++i) {
        int value = coefficients[i];
        int power = n - i;

        if (value == 0) {
            continue;
        }

        int absoluteValue = abs(value);

        if (first) {
            if (value < 0) {
                ans += "-";
            }
            first = false;
        } else {
            ans += (value > 0) ? "+" : "-";
        }

        if (power == 0) {
            ans += to_string(absoluteValue);
        } else {
            if (absoluteValue != 1) {
                ans += to_string(absoluteValue);
            }

            ans += "x";

            if (power >= 2) {
                ans += "^" + to_string(power);
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

import sys


def main() -> None:
    # 按空白切分全部输入，兼容系数写在同一行或分多行的情况
    data = list(map(int, sys.stdin.buffer.read().split()))

    n = data[0]
    coefficients = data[1:n + 2]

    parts: list[str] = []
    first = True  # 标记是否还未输出过任何非零项

    for i, value in enumerate(coefficients):
        power = n - i  # 输入从高次到低次，次数 = n - i

        if value == 0:
            continue  # 系数为 0 的项完全省略

        if first:
            if value < 0:
                parts.append("-")  # 最高次项为正时不输出前导加号
            first = False
        else:
            parts.append("+" if value > 0 else "-")

        magnitude = abs(value)

        if power == 0:
            # 常数项：即使为 ±1 也必须完整输出
            parts.append(str(magnitude))
        else:
            if magnitude != 1:
                # 非常数项：绝对值为 1 时省略系数
                parts.append(str(magnitude))
            parts.append("x")
            if power >= 2:
                parts.append("^" + str(power))

    print("".join(parts))


if __name__ == "__main__":
    main()

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.StringJoiner;

public class Main {

    public static void main(String[] args) throws IOException {
        // 按空白切分全部输入，兼容系数写在同一行或分多行的情况
        List<Integer> numbers = new ArrayList<>();
        for (String token : new String(System.in.readAllBytes()).split("\\s+")) {
            if (!token.isEmpty()) {
                numbers.add(Integer.parseInt(token));
            }
        }

        int n = numbers.get(0);

        // 输入系数顺序为 a_n, a_{n-1}, ..., a_0，与数组下标一一对应
        int[] coefficients = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            coefficients[i] = numbers.get(i + 1);
        }

        StringJoiner joiner = new StringJoiner("");
        boolean first = true; // 标记是否还未输出过任何非零项

        for (int i = 0; i <= n; i++) {
            int value = coefficients[i];
            int power = n - i; // 输入从高次到低次，次数 = n - i

            if value == 0 {
                continue; // 系数为 0 的项完全省略
            }

            if first {
                if (value < 0) {
                    joiner.add("-"); // 最高次项为正时不输出前导加号
                }
                first = false;
            } else {
                joiner.add(value > 0 ? "+" : "-");
            }

            int magnitude = Math.abs(value);

            if power == 0 {
                // 常数项：即使为 ±1 也必须完整输出
                joiner.add(Integer.toString(magnitude));
            } else {
                if (magnitude != 1) {
                    // 非常数项：绝对值为 1 时省略系数
                    joiner.add(Integer.toString(magnitude));
                }
                joiner.add("x");
                if (power >= 2) {
                    joiner.add("^" + power);
                }
            }
        }

        System.out.println(joiner);
    }
}

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	// 用 Fscan 按空白读取，兼容系数写在同一行或分多行的情况
	reader := bufio.NewReader(os.Stdin)

	var n int
	if _, err := fmt.Fscan(reader, &n); err != nil {
		return
	}

	coefficients := make([]int, n+1)
	for i := 0; i <= n; i++ {
		if _, err := fmt.Fscan(reader, &coefficients[i]); err != nil {
			return
		}
	}

	var builder strings.Builder
	first := true // 标记是否还未输出过任何非零项

	for i := 0; i <= n; i++ {
		value := coefficients[i]
		power := n - i // 输入从高次到低次，次数 = n - i

		if value == 0 {
			continue // 系数为 0 的项完全省略
		}

		if first {
			if value < 0 {
				builder.WriteString("-") // 最高次项为正时不输出前导加号
			}
			first = false
		} else {
			if value > 0 {
				builder.WriteString("+")
			} else {
				builder.WriteString("-")
			}
		}

		magnitude := value
		if magnitude < 0 {
			magnitude = -magnitude
		}

		if power == 0 {
			// 常数项：即使为 ±1 也必须完整输出
			builder.WriteString(strconv.Itoa(magnitude))
		} else {
			if magnitude != 1 {
				// 非常数项：绝对值为 1 时省略系数
				builder.WriteString(strconv.Itoa(magnitude))
			}
			builder.WriteString("x")
			if power >= 2 {
				builder.WriteString("^" + strconv.Itoa(power))
			}
		}
	}

	fmt.Println(builder.String())
}

use std::io::{self, Read, Write};

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();

    // 按空白切分：第一项是次数 n，其后 n+1 项是系数
    let numbers: Vec<i32> = input
        .split_whitespace()
        .map(|token| token.parse::<i32>().unwrap())
        .collect();

    let n = numbers[0] as usize;
    let mut output = String::new();
    let mut first = true;

    for i in 0..=n {
        let value = numbers[i + 1];
        let power = n - i; // 输入从高次到低次，次数 = n - i

        if value == 0 {
            continue; // 系数为 0 的项完全省略
        }

        if first {
            if value < 0 {
                output.push('-'); // 最高次项为正时不输出前导加号
            }
            first = false;
        } else {
            output.push(if value > 0 { '+' } else { '-' });
        }

        let magnitude = value.abs();

        if power == 0 {
            // 常数项：即使为 ±1 也必须完整输出
            output.push_str(&magnitude.to_string());
        } else {
            if magnitude != 1 {
                // 非常数项：绝对值为 1 时省略系数
                output.push_str(&magnitude.to_string());
            }
            output.push('x');
            if power >= 2 {
                output.push('^');
                output.push_str(&power.to_string());
            }
        }
    }

    print!("{}", output);
    io::stdout().flush().unwrap();
}

测试与验证

输入	输出	说明
`5` / `100 -1 1 -3 0 10`	`100x^5-x^4+x^3-3x^2+10`	官方样例 1：含系数 `-1`、`1`、`0`
`3` / `-50 0 0 1`	`-50x^3+1`	官方样例 2：最高次项为负，常数项 `1` 不省略
`1` / `-1 1`	`-x+1`	边界：一次项系数 `-1` 省略，常数项 `1` 保留

C++、Python、Java、Go 四种实现均已在本地编译运行，三个用例输出完全一致；Rust 版本因本机未安装 rustc 未实测，代码逻辑与其余四种保持相同。

总结与反思

次数决定格式，符号决定连接符。把「输出符号」和「输出系数」拆成两个独立步骤，是本题最清晰的写法，避免了条件嵌套。
first 必须在输出首个非零项后才置 false；若在循环开头就置位，前导 + 会残留。
易错点：常数项的 ±1 不能省略系数，与非常数项的判断条件区分开。
易错点：power 用 n - i 计算，而非直接用 i，否则输出会变成低次到高次。
整体是一次线性遍历，无需任何数据结构，属于「模拟 + 字符串拼接」类题目。
若追求更优的空间复杂度，可利用「输入顺序即输出顺序」这一特点改为边读边处理，；此时记得加 cin.tie(nullptr) 解除读写绑定。

TK的小站

牛客每日一题-多项式输出

题目信息

题目描述

输入描述

输出描述

初步思路

1. 次数与下标的对应关系

2. 每一项按四步拼装

3. 符号处理：用 `first` 标记

4. 系数 1 的省略条件

5. 进阶写法：边读边处理

两种写法对比

关于「边读边写会不会慢」

算法分析

代码实现

测试与验证

总结与反思

ttkqwe

牛客每日一题-多项式输出

题目信息

题目描述

输入描述

输出描述

初步思路

1. 次数与下标的对应关系

2. 每一项按四步拼装

3. 符号处理：用 first 标记

4. 系数 1 的省略条件

5. 进阶写法：边读边处理

两种写法对比

关于「边读边写会不会慢」

算法分析

代码实现

测试与验证

总结与反思

ttkqwe

3. 符号处理：用 `first` 标记