多项式输出【牛客tracker 每日一题】

多项式输出时间限制1 秒空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述给定一元n nn次多项式f ( x ) a n x n a n − 1 x n − 1 ⋯ a 1 x a 0 , f(x) a_n x^n a_{n-1} x^{n-1} \dots a_1 x a_0,f(x)an​xnan−1​xn−1⋯a1​xa0​,其中a n ≠ 0 a_n \ne 0an​0系数a i ( 0 ≤ i ≤ n ) a_i\ (0 \le i \le n)ai​(0≤i≤n)满足− 100 ≤ a i ≤ 100 -100 \le a_i \le 100−100≤ai​≤100。请按如下规则将多项式输出为字符串从高次到低次依次输出系数为0 00的项完全省略对于次数大于等于1 11的项若其系数为1 11或− 1 -1−1则省略系数的绝对值1 11常数项即使为1 11或− 1 -1−1也应完整输出次数为0 00仅输出常数次数为1 11输出x xx次数≥ 2 \ge 2≥2输出x^k输出的第一个非零项即最高次项若系数为正不输出前导加号后续正系数项前需加负系数项加-。输入描述第一行输入整数n ( 1 ≤ n ≤ 100 ) n\ (1 \le n \le 100)n(1≤n≤100)表示多项式次数。第二行输入n 1 n 1n1个整数a n , a n − 1 , … , a 0 a_n, a_{n-1}, \dots, a_0an​,an−1​,…,a0​依次为n nn次项到0 00次项常数项的系数。输出描述在一行输出格式化后的多项式字符串。示例 1输入5 100 -1 1 -3 0 10输出100x^5-x^4x^3-3x^210示例 2输入3 -50 0 0 1输出-50x^31说明截图中示例 2 的输出行被页面底部截断此处按题面规则补全− 50 x 3 -50x^3−50x3与常数项1 11之间需要号。数据范围与提示1 ≤ n ≤ 100 1 \le n \le 1001≤n≤100− 100 ≤ a i ≤ 100 -100 \le a_i \le 100−100≤ai​≤100a n ≠ 0 a_n \ne 0an​0最高次项系数一定不为0 00本题为纯模拟题逐项处理时注意以下几点首个输出项不加正号之后的项正数补、负数自带-系数为± 1 \pm 1±1且次数≥ 1 \ge 1≥1时省略数字1 11但常数项必须写出次数为1 11时写作x次数为0 00时只写系数次数≥ 2 \ge 2≥2时写作x^k系数为0 00的项直接跳过但要留意“该项是否为第一个输出项”的标志位不要错乱。解题思路本题是字符串格式化模拟问题。给定一元n nn次多项式的各项系数从高次到低次需要按照题目规定的输出规则将其转换为标准的多项式字符串。规则包括从高次到低次输出、省略零系数项、处理系数± 1 \pm 1±1的简写、正确表示次数以及符号的添加。由于n ≤ 100 n \le 100n≤100直接逐项处理即可时间复杂度极低。1. 问题等价转化输入给出n nn和n 1 n1n1个整数a n , a n − 1 , … , a 0 a_n, a_{n-1}, \dots, a_0an​,an−1​,…,a0​分别对应x n , x n − 1 , … , x 0 x^n, x^{n-1}, \dots, x^0xn,xn−1,…,x0的系数。输出要求从最高次项开始依次处理到常数项。系数为0 00的项完全跳过。对于次数≥ 1 \ge 1≥1的项若系数为1 11或− 1 -1−1省略数字1 11常数项即使为± 1 \pm 1±1也要完整输出。次数为0 00只输出常数次数为1 11输出x次数≥ 2 \ge 2≥2输出x^k。第一个输出的非零项若为正系数不加前导后续正系数项前加负系数项前加-。2. 算法实现读入与存储读入n nn然后按从高次到低次的顺序读入n 1 n1n1个系数存入数组b其中b[i]表示x i x^ixi的系数注意读入顺序与下标对应b[n]是最高次b[0]是常数项。处理最高次项根据b[n]的符号输出符号正数不输出负数输出-。若|b[n]| 1输出系数的绝对值否则为1 11或− 1 -1−1省略数字。输出x。若n 1 n 1n1输出^n。处理中间项i n − 1 i n-1in−1到1 11若b[i] 0跳过。根据b[i]的符号输出或-。若|b[i]| 1输出系数的绝对值否则省略数字。输出x。若i 1 i 1i1输出^i。处理常数项i 0 i 0i0若b[0] 0不输出。若b[0] 0输出和b[0]。若b[0] 0输出-和-b[0]。输出换行。3. 复杂度分析时间复杂度只需一次遍历所有系数O ( n ) O(n)O(n)。n ≤ 100 n \le 100n≤100运算量极小。空间复杂度存储系数数组O ( n ) O(n)O(n)空间消耗可忽略。总结本题是纯模拟题关键在于准确实现输出规则中的每一个细节零系数跳过、± 1 \pm 1±1的省略、次数的表示以及符号的正确添加。通过按项逐一判断和处理可以清晰、无误地生成符合要求的多项式字符串。代码结构简单适合作为模拟类题目的练习。代码简要说明数组b存储系数b[i]对应x i x^ixi的系数。最高次项处理单独处理因为不需要前导。循环处理中间项从n − 1 n-1n−1到1 11判断系数是否为0 00输出符号和系数绝对值再输出x及次数。常数项处理单独判断正负并输出。使用printf进行格式化输出注意负数的绝对值处理。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;scanf(%lld,n);ll b[n1];for(ll in;i0;i--)scanf(%lld,b[i]);if(b[n]0)printf();elseif(b[n]0)printf(-);if(b[n]1){printf(%lld,b[n]);}elseif(b[n]-1){printf(%lld,-b[n]);}if(b[n]!0)printf(x);if(b[n]!0n1)printf(^%lld,n);for(ll in-1;i1;i--){if(b[i]0)printf();elseif(b[i]0)printf(-);if(b[i]1){printf(%lld,b[i]);}elseif(b[i]-1){printf(%lld,-b[i]);}if(b[i]!0)printf(x);if(b[i]!0i1)printf(^%lld,i);}if(b[0]0)printf(%lld,b[0]);elseif(b[0]0)printf(-%lld,-b[0]);return0;}