算法
(字符串处理,模拟) $O(n)$
从前往后依次处理每一项,依次考虑符号、系数、x、x的次数:
- 如果系数是0,则直接continue;
- 如果不是第一个非零项,且系数是正的,则输出
'+'
;如果系数是负的,则无条件输出'-'
; - 如果系数的绝对值不是1,或者是常数项,则输出系数的绝对值;
- 如果次数不为0,则输出x
- 如果次数大于1,则输出次数
时间复杂度
每个数会被处理一次,因此总时间复杂度是 $O(n)$。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
bool is_first = true;
for (int i = n; i >= 0; i -- )
{
int a;
cin >> a;
if (!a) continue;
if (!is_first && a > 0) printf("+");
else if (a < 0) printf("-");
if (abs(a) != 1 || !i) printf("%d", abs(a));
if (i) printf("x");
if (i > 1) printf("^%d", i);
is_first = false;
}
return 0;
}
个人觉得这题一点一点模拟才是正解(\滑稽)
没错,这就是一道赤裸裸的模拟题hh