[Mivik的萌新赛][T1 ygg的题库] 题解

要求构造一个满足 $m$ 个条件的 $n$ 项多项式，每个条件形如多项式在某个点取值为正/负。

$1\le n\le 32$，$1\le m\le 4000$

题目链接

---

思路

Sol. 1

直接做这道题的话会没有思路，我们考虑从另类的角度去切入此题

由于多项式可导且连续，我们发现，在一个取值大于0的点和一个取值小于0的点之间，必定会有一个取值为0的点，但我们并不知道这个取值为0的点是什么？没有关系。此题只需要我们满足题目中给出的全部条件，我们这个多项式长什么样由我们自己决定

因此，我们可以把读入的所有X坐标从小到大排一次序，然后从小到大扫描，每次遇到一个符号和下一个符号不相同的，就另它们的中间点（ $\frac{x+y}{2}$ ）取值为0

最后这个方程可以用高斯消元解决

代码

Sol. 2

考场上发现一些同学是多次随机出这个序列再判断是否合法，如果合法就输出，依旧可以得全分

由于本题数据范围过小，这也不妨为一种正解ww

Sol. 3

（娱乐做法）

构建一个BP网络，第一层有n个结点，第二层一个结点并使用Sigmoid作为激活函数 ，中间连边权值默认随机，然后反复抽样调整网络权值，最终输出答案

代码