基础算法-模拟：多项式输出

1.前言首先明确一点基础 ! 简单基础算法说明这个算法适用性较广是学习较难算法的基石但并不代表它所对应的题目是简单题。基础算法包括排序算法模拟高精度枚举前缀和查分双指针二分贪心递归离散化递归初阶分治DFSBFS等很多算法。在学习这些算法之前需要具备1.C、C基本语法等2.STL中的库函数3.数据结构知识在之前我们学过了很多的排序算法所以在基础算法篇不会讲解排序算法主要结合题目来讲解思路从而得到算法算法基础篇没一篇博客仅仅只讲一个题目从而更加深入理解该算法的含义。2.模拟算法解释模拟一词顾名思义就是题目让你做什么你就做什么考察的是将思路转化成代码能力这类题一般较为简单属于竞赛中的签到题。而在学习语法中接触到的题目大多为模拟题。3.P1067【NOIP普及组】多项式输出题目链接P1067 [NOIP 2009 普及组] 多项式输出 - 洛谷解法根据提议模拟即可分类讨论分的越详细越不会出现bug。如何输出我们可以把每一项单独输出也就是说我们可以用循环进行每一项的输出。把每一项拆分出来得到由四个部分组成符号 、 数 、 x 、指数次数。由于x是不变的所以我们只需要关心三个部分符号数次数。符号有两种情况正号和负号此时可以分情况讨论我们观察发现如果第一项是正号则不需要输出直接输出后面的数字即可否则其他情况下都要输出类似于这种形式int a, n; cin n; cin a; if (a 0) continue; if (a 0) cout -; else { if (i ! n) { cout ; } }当然这是没有写入循环的情况如果补全可以有这种形式#includeiostream using namespace std; int main() { int n; cin n; for (int i n; i 0; i--) { int a; cin a; if (a 0) continue; if (a 0) cout -; else { if (i ! n) cout ; } } return 0; }对于数我们也需要分情况讨论为0的情况已经在循环开始时判断出来了不用在讨论了对于数这一项我们主要分析是否为1的情况其次还要记得先取绝对值aabs(a)因为之前符号已经输出了这个数输出的时候必须为正数如果为1我们还需要判断是否为末项因为如果不是末项这个1可以省略通过i是否为0判断如果是末项则需要输出1不能省略。完善代码变成这样#includeiostream using namespace std; int main() { int n; cin n; for (int i n; i 0; i--) { int a; cin a; //符号 if (a 0) continue; if (a 0) cout -; else { if (i ! n) cout ; } //数 a abs(a); if (a ! 1 || (a 1 i 0)) cout a; } return 0; }这里我们可以把a不为1 和a为1且为末项情况一起讨论因为这样都要保证这个数正常输出如果看不懂也可以按照刚刚的思路多写一下if-else语句。最后是次数次数为0则什么都不输出次数为1则省略^1否则输出^i通过完善该逻辑得到最终代码#includeiostream using namespace std; int main() { int n; cin n; for (int i n; i 0; i--) { int a; cin a; //符号 if (a 0) continue; if (a 0) cout -; else { if (i ! n) cout ; } //数 a abs(a); if (a ! 1 || (a 1 i 0)) cout a; //次数 if (i 0) continue; else if (i 1) cout x; else cout x^ i; } return 0; }提交评测完成该题