题解：P1737 [NOI2016] 旷野大计算

· · 题解

Task 1

给定 a,b，输出 -2a-2b。6 行。

提取公因式变成 -2(a+b)，可以用加法代替乘 2。

Task 2

给定 a，求 \dfrac{1}{1+e^{17a}}。6 行。

乘 17 拆成右移 4 加自己，然后取反调用 S 即可。

Task 3

给定 a，求 \text{sign}(a)。6 行。

注意到题目的精度限制远小于计算节点的精度限制，这启示我们可以使用极限的思想。

下文中我们使用 \text{inf} 替代一个足够大的值。具体取什么需要代入每个 task 算一下使得不会爆范围。

注意到 \lim_{x\to \infty}S(x)=0,S(0)=\dfrac{1}{2},\lim_{x\to \infty}S(x)=1，可以得到 g(x)=S(x\cdot \text{inf})=\begin{cases}0 & x<0\\ \dfrac{1}{2} & x=0\\ 1 & x>0\end{cases}。此时 \text{sign}(x)=2g(x)-1 就做完了。

Task 4

给定 a，求 |a|。14 行。

因为输入不超过 9 位，我们可以制造 eps=10^{-10} 的偏差使得没有 a=0 的情况。

通过 Task 3 的启发，我们完全可以构造一个函数 x+g(x)\cdot \text{inf} 使得 x<0 仍然是 x，否则是 \text{inf}。

这有什么好处？代入 S 就会发现 x<0 是 S(x) 否则是 1。

但是如果这么做我们就需要一个从 S(x) 还原回 x 的方法，在减掉 g(x)\cdot \text{inf} 后我们就得到了 \min(x,0)=\begin{cases}x & x<0\\ 0 & x=0\end{cases}。

对 S 求导，有 S'(x)=\dfrac{e^{-x}}{(1+e^{-x})^2}，代入 x=0 得到 S'(0)=\dfrac{1}{4}，我们可以认为 S(\dfrac{x}{\text{inf}})=\dfrac{1}{4}\times \dfrac{x}{\text{inf}}+\dfrac{1}{2}。

这样就可以从 S(x) 还原回 x 了。

最后 |x|=-2\min(x,0)+x 就做完了。

适当优化一下。

Task 5

输入 32 个二进制位上的值，转成数。95 行。

没啥好说的，优化一下 i=0 的右移就行了。

Task 6

输入数，转成 32 个二进制位上的值。190 行。

从高到低做，事实上我们只需要返回 [x\ge 2^i]。

前面的 Task 3&4 已经教会大家 S 函数的打开方法了，直接求 S((x-2^i+10^{-10})\cdot \text{inf})。

精细实现一下，一开始就加上 \text{eps} 并乘上 \text{inf}。

Task 7

输入 a,b，求 a 异或 b。605 行。

利用 Task 5&6，只需要做 a,b\in \{0,1\} 的情况。

转成 a+b-[a+b\ge 2]2，这个类似 Task 6 直接用 S 就可以了。

Task 8

输入 a，求 \dfrac{a}{10}。7 行。

求出一个点 p 满足 S'(p)=\dfrac{1}{10}，则答案是 \dfrac{S(p+\dfrac{x}{\text{inf}})-S(p)}{\text{inf}}。

解出来 p=\ln(4+\sqrt{15})。

Task 9

输入长度为 16 的序列，排序。3000 行。

考虑朴素的排序方法：

for(int i=0;i<16;++i)for(int j=i+1;j<16;++j)if(a[i]>a[j])swap(a[i],a[j]);

只需要求 \min(a,b)=a+\min(0,b-a)，这个在 Task 4 已经会做了。

Task 10

给定 a,b,m，求 ab\bmod m。2000 行。

一个自然的想法是使用快速幂的思想，这样我们需要实现在 a\in\{0,1\} 时的 ab。这里假定 b\ge 0。

注意到 ab=\min(a\cdot \text{inf},b)，套用前面的做法。

这个做法可能需要轻微卡一下常数。