如何获取更多Homework2性能分？

为了获得更多的性能分，个人目前想到了以下注意点：

Homework2与Homework1还是有不少相似之处的，因此在上次作业中的这些性能提升点，此次依然有效——

• 表达式之间不含空格
• 如果存在正项，则表达式以正项为首项（且省略）
• 合并同类项
• 函数指数部分为0时不输出
• 非常数项：系数为1时不输出，系数为-1时仅保留负号
• 指数为1时不输出
• 0项不输出

而也有一些此次作业中新出现的抢分点：

• x**2以x*x形式输出
• $sin^2(x)+cos^2(x)=1$
• $sin^2(x)-cos^2(x)=1-2cos^2(x)$

其中三角函数的化简较为复杂。

前者，我们注意到，对于形如

$$a*x^i*sin^j(x)*cos^k(x)$$

的项，能够以此规则化简的只有两种形式——

$$a*x^i*sin^{j+2}(x)*cos^{k-2}(x)$$

$$a*x^i*sin^{j-2}(x)*cos^{k+2}(x)$$

化简后两项合并为——

$$2*a*x^i*sin^{j-2}(x)*cos^{k-2}(x)$$

因此我们可以遍历容器并检查邻项是否存在，从而化简；而后者，在j=2|k=2时是肯定可以提升性能分的，方法与$sin^2(x)+cos^2(x)=1$的类似。

当然，个人觉得除非针对后两点构造数据，其出现的机率并不大，是否要为了性能分牺牲性能也是一个问题。

也求有想法的大佬交流下更好的方法与隐藏的内卷点(～￣▽￣)～

为了获得更多的性能分，个人目前想到了以下注意点：

Homework2与Homework1还是有不少相似之处的，因此在上次作业中的这些性能提升点，此次依然有效——

• 表达式之间不含空格
• 如果存在正项，则表达式以正项为首项（且省略）
• 合并同类项
• 函数指数部分为0时不输出
• 非常数项：系数为1时不输出，系数为-1时仅保留负号
• 指数为1时不输出
• 0项不输出

而也有一些此次作业中新出现的抢分点：

• x**2以x*x形式输出
• $sin^2(x)+cos^2(x)=1$
• $sin^2(x)-cos^2(x)=1-2 cos^2(x)$

其中三角函数的化简较为复杂。

前者，我们注意到，对于形如$a*x^i*sin^j(x)*cos^k(x) $ 的项，能够以此规则化简的只有两种形式——

$$a\*x^i\*sin^{j+2}(x)\*cos^{k-2}(x)$$

$$a\*x^i\*sin^{j-2}(x)\*cos^{k+2}(x)$$

化简后两项合并为——$2\*a\*x^i\*sin^{j-2}(x)\*cos^{k-2}(x)$

因此我们可以遍历容器并检查邻项是否存在，从而化简；而后者，在j=2|k=2时是肯定可以提升性能分的，方法与$sin^2(x)+cos^2(x)=1$的类似。

当然，个人觉得除非针对后两点构造数据，其出现的机率并不大，是否要为了性能分牺牲性能也是一个问题。

也求有想法的大佬交流下更好的方法与隐藏的内卷点(～￣▽￣)～

既然无法贪心，只好搜索。

dfs，每次找到可合并的两个项去合并，然后回溯，不断记录最短答案，其中，两个项合并的次数(即合并之后的系数)要满足至少要用完其中一个项。

改完dfs发现要T（爆栈），就把每次dfs前的答案扔进set判重，即记忆化。

合并的话一开始只考虑了sin(x)2+cos(x)2=1然后用1−sin(x)2=cos(x)2以拆分常数项 和不含sin(x)sin(x)或cos(x)cos(x)的项来体现。后来发现速度很快但效果不好。

在队友丁总对我的指导下，我把1−sin(x)2=cos(x)2放进了dfs，成为合并两个项的新选择。

关于极端数据爆栈，卡住dfs次数和程序运行时间即可。最终性能分满分。

正常随机数据或项数不多的数据可以随便跑完，评论区里面的数据应该都能搜完。

欢迎大佬们批评指正，本数学弱鸡，码力选手只能想到这种暴力做法，写了快10k的优化类，累死。

note

这是一篇从Hexo迁移的文章，创建于2020-03-05 08:30:59