[NOIP 2009 普及组] 多项式输出

知识点

字符串构造、分类讨论

解题思路

从最高次到常数项扫描，跳过系数0。根据是否为第一项输出正负号；非零次且绝对值为1时省略系数；指数1只写x，指数大于1写x^次数，常数项只写数字。

正确性说明

按次数递减逐项处理，跳过的恰是零项。每个非零项的符号、系数、变量与指数分别按规则唯一确定，拼接顺序正确，不会多出加号或空格。

易错点

常数1不能省略；第一项负号仍要输出；指数0、1特别处理；代码兼容零多项式输出0。

复杂度

时间O(n)加输出长度，空间O(1)额外状态。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;bool first=true;for(int k=n;k>=0;k--){int c;cin>>c;if(!c)continue;if(c<0)cout<<'-';else if(!first)cout<<'+';int v=abs(c);if(k==0||v!=1)cout<<v;if(k){cout<<'x';if(k>1)cout<<'^'<<k;}first=false;}if(first)cout<<0;cout<<'\n';}