[NOI2016] 旷野大计算(挖坑不填)

前言

阴间人做阴间题

手搓计算机

感觉很有意思,来看一看。

无论如何,这是一道数学题,因此我可能一时半会做不出来了,慢慢填坑吧。

题意

有一个存储空间,每一位都储存一个实数。

现将第 \(i\) 位的数记为 \(x_i\),每位有一个计算结点,这个计算结点的结果会输出到该位置。

名称 操作符(类型) 操作数 计算结果
输入节点 I 从输入缓冲区读入一个实数作为 \(x_t\)
输出节点 O \(i\) \(x_t = x_i\),并将 \(x_t\) 输出
加法节点 + \(i,j\) \(x_t = x_i+x_j\)
偏移节点 C \(i,c\) \(x_t=x_i+c\)
取反节点 - \(i\) \(x_t=-x_i\)
左移节点 < \(i,k\) \(x_t=x_i\cdot 2^k\)
右移节点 > \(i,k\) \(x_t=x_i\cdot 2^{-k}\)
S 型节点 S \(i\) \(x_t=s(x_i)\) (Sigmoid 函数)
比较节点 P \(i,j\) \(x_t = \begin{cases}-1 &x_i<x_j\\ 0 &x_i=x_j\\1 &x_i>x_j\end{cases}\)
Max 节点 M \(i,j\) \(x_t = \begin{cases}x_i &x_i > x_j\\x_j &x_i \leq x_j\end{cases}\)
乘法节点 * \(i,j\) \(x_t=x_i \cdot x_j\)

使用后三个结点会倒扣分,为了得满分不能使用。

其中,\(s(x)\) 的定义如下:(\(e\) 为自然常数,其值约为 \(2.718281828459045\ldots\))

\[s\left ( x \right )=\frac{1}{1+e^{-x}} \]

现给定如下十个任务,使用一定数量的结点来完成这些任务。

1

输入两个数 \(a,b\),输出 \(-2a-2b\),要求不超 \(6\) 个计算结点。

输入占 \(2\),输出占 \(1\),还剩 \(3\)。

加起来左移一位然后取反即可。

I
I
+ 1 2
< 3 1
- 4
O 5

2

输入一个数 \(a\),输出 \(\dfrac{1}{1 + e^{17a}}\),要求不超 \(6\) 个计算结点。

输入占 \(1\),输出占 \(1\),还剩 \(4\)。

使用 \(s(x)\) 可以计算 \(\dfrac{1}{1 + e^{-x}}\) 那么只需要三步搞出 \(-17a\)。

\(-17a = -(a \cdot 2^4 + a)\),恰好三步。

I
< 1 4
+ 1 2
- 3
S 4
O 5

3

输入一个数 \(a\),输出:

\[\large \operatorname{sign}(a) = \begin{cases}&-1 &a < 0\\&0 &a = 0\\&1 &a > 0\end{cases} \]

要求不超 \(6\) 个计算结点。

输入占 \(1\),输出占 \(1\),还剩 \(4\)。

现在可以发现这道题最难的部分一是没有条件判断,二是没有常量。

首先思考如何造出常量 :

\(0\) 可以用右移 \(10000\) (\(10^4\) 是题面给出右移最大可行值) 来得到,然后用偏移操作可以得到任意常量了。

符号函数的一个可行实现方式是 \(\dfrac{a}{|a|}\) 但是这里并没有绝对值和除法。

于是正负不同输出不同只能靠 Sigmoid 函数实现,观察函数图像 :

[NOI2016] 旷野大计算(挖坑不填)

可以发现减个 \(0.5\) 误差就非常之小了。

于是把原数扩大许多倍,正负不变,得到的值就很接近 \(1,0-1\) 了。

然后乘以 \(2\) 让精度溢出即可。

I
< 1 100
S 2
C 3 -0.5
< 4 1
O 5

4

输入一个数 \(a\),输出 \(|a|\),要求不超 \(14\) 个计算结点。

输入占 \(1\),输出占 \(1\),还剩 \(12\)。

然后如果用 #3 做法加上乘法是能过的,但是过于 \(naive\)。

然后是一个更加 \(naive\) 的想法,如果判断大于零就不取反,否则取反。显然有条件判断的都是无法达成的。

我们大力百度 Sigmoid 函数,发现 :

\[\large S'(x) = \frac{e^{-x}}{(1 + e^{-x})^2} = S(x)(1 - S(x)) \]

这个导数的性质就非常奇妙 NOI数学竞赛

上一篇:系统监控工具-glances


下一篇:郭冬临到底喝了多少水?