[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作为激活函数 ,中间连边权值默认随机,然后反复抽样调整网络权值,最终输出答案

代码

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

https://mivik.gitee.io/2019/solution/miviknewbie-t1/

作者

Mivik

发布于

2019-11-10

更新于

2021-05-31

许可协议

评论