P1737 旷野大计算

· · 题解

Update on 2024-2-23/17:10 修改了部分笔误

Update on 2024-2-28/15:58 Latex修复

题目链接：P1737 [NOI2016] 旷野大计算

题目大意：用取反，位移，等操作，以及非常玄学的 S 函数来完成一些任务，为什么不用冯诺依曼的存储程序思想，差评！

其中 S(x) 函数为 \frac{1}{1+e^{-x}}，我们要充分利用它的一些性质。

还有三个非常好用但要扣分的节点：比较节点、MAX 节点、乘法节点。

Task 1

输入：a,b

输入限制：\lvert a \rvert, \lvert b \rvert \le 10^9，小数部分不超过 9 位。

输出：-2a-2b

满分行数：6 行

难度：送分

显然我们要对样例优化，我们可以可以将两个数的取反和乘 2，放在一起，这样就刚好 6 行。

代码如下：


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

Task 2

输入：a

输入限制：\lvert a \rvert \le 10^9，小数部分不超过 9 位。

输出：\dfrac{1}{1+e^{17a}}

满分行数：6 行

难度：送分

注意到 17=2^4+1，我们可以用位移做优化，要记得取反，代码如下：

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

Task 3

输入：a

输入限制：\lvert a \rvert \le 10^9，小数部分不超过 9 位。

输出：\begin{cases}-1 & a \lt 0 \\ 0 & a = 0 \\ 1 & a \gt 0\end{cases}

满分行数：6 行

难度：大众

我们连 if，else 都没有，肯定不能用正常方式构造了。

首先我们可以用比较节点，与 0 比较得 6 分。

如何造 0?

可以用 a-a 然后比较大小。

别急，我们阅读阅读题面：

每个跳蚤的计算能力都是有限的，他们仅可以精确到十进制小数点后 90 位，超过的部分将会被四舍五入。同理，上述表格中的操作数 c 的小数部分也不能超过 90 位。另外，左移节点和右移节点中的操作数 k 必须是非负整数，且不能超过 10^4。

但是：

你构造的计算机的输出中的某个值与预期的输出值相差超过 10^{-9}，则认为你的输出不正确，得 0 分。

为啥精确了 90 位，SPJ 却只判 10^{-9} 的误差呢？

当然是因为跳蚤国王只看前 9 位啦！

而且为什么大部分测试点，都没有体现精确度这个东西，而且从表面上看 S 函数除了 \text{Task 2} 上有用外好像并没有大用。

要是出题人真的想没事找事的话为啥不是 S(x)=ax^2+bx+c 呢？

为啥不是 114514^x 呢？

为啥不是 \varphi(x) 呢？

这时我们需要关注 S 函数了。

$$ \lim_{x \to \infty} S(x)=1 $$ $$ \lim_{x \to -\infty} S(x)=0 $$ 有没有一种可能我们可以通过 $S$ 函数的极限来取分段函数。 什么意思呢？ 举个栗子（也就是这个点）：我们把 $a$ 放大无穷大倍（这里当然只用刚好取足够大。），丢进 $S$ 函数 里，那我们是不是得到了一个分段函数： $$ S(x \times \infty )= \begin{cases} 1 & x > 0 \\ \frac{1}{2} & x = 0 \\ 0 & x < 0 \end{cases} $$ 当然我们这里的 $\infty$ 可以用位移解决，这里我们需要乘上足够大的数，来接近于 $0$ 或 $1$。 然后我们把这个函数乘上 $2$ 再减去 $1$，就得到了我们想要的了。 ``` I < 1 50 S 2 < 3 1 C 4 -1 O 5 ``` ### Task 4 输入：$a

输入限制：\lvert a \rvert \le 10^9，小数部分不超过 9 位。

输出：\lvert a \rvert

满分行数：14 行

难度：较难

看得出来从这个点开始，做法就越来越复杂了。

我们知道 a 的绝对值是一个分段函数：

\lvert a \rvert=\begin{cases} -a & a<0 \\0 & a=0\\a & a>0 \end{cases}

那我们肯定要用和 \text{Task 3} 差不多的方法来进行构造。

可问题来了，我们 S 函数的极限 0 \text{，} 1 与-a \text{，} a 没有半毛钱关系，就算做也免不了乘法或取大小呀！

那怎么办呢？

是时候运用一下导数了。

什么是导数？

导数是对一个函数某一处的增长率，我们可以简单地认为这是函数的增长速度，从几何意义上来讲它的含义是函数图像上某一点的切线的斜率。

一般来讲我们会把 f(x) 的导数记为 {f}'(x)

{f}'(x)=\lim_{\Delta x \to 0}\frac{f(x+\Delta x)-f(x)}{\Delta x}

我们可以算出 {S}'(x)=\frac{e^{-x}}{(1+e^{-x})^2}，在 0 处取值 \frac{1}{4}。

这时我们可以轻易得写出一条 S 函数在 (0,\frac{1}{2}) 处的一条切线：y=\frac{1}{4}x+\frac{1}{2}

声明：为表示方便，下称这条切线为 f(x)。

如果我们的 a 越接近 0 那么 S(a) 就会越接近 f(a)。

而我们如果得知某一处 f(x) 的值，我们就可以得出 x 的值。

我们就可以从 S(x) \to x。

这样我们就可以在将 x 丢进 S(x) 后再将 x 还原出来。

但我们还需要分段。

运用 \text{Task 3} 的方法，我们把 T(x)=S(x \times 2^q) 加进 S 里：

S(\frac{x}{2^k}+T(x)\times2^p)=\begin{cases}1&x>0\\\frac{x}{4\times 2^k}+\frac{1}{2}& x<0\end{cases}

解释：如果 x>0 那么 T(x)\times2^p 的贡献就为极大值,得到 S 的极限。

如果 x<0 那么 T(x)\times2^p 的贡献为 0，剩下的 \frac{x}{2^k} 由于非常接近 0 而非常接近 f(x)。

都让 x 出现在了分段函数的解析式上了，肯定会简单不少：

接着我们减去 \frac{1}{2} 然后乘上 4 \times 2^k=2^{k+2}：

2^{k+2}(S(\frac{x}{2^k}+T(x)\times2^p)-\frac{1}{2})=\begin{cases}2^{k+1}&x>0\\x& x<0\end{cases}

可是那个 2^{k+1} 好丑啊！可减掉会把 x 一起减掉的。

那我们可以减去 T(x)\times2^p 那么：

2^{k+2}(S(\frac{x}{2^k}+T(x)\times2^p)-\frac{1}{2})-T(x)\times2^p=\begin{cases}2^{k+1}-T(x)\times2^p&x>0\\x& x<0\end{cases}

我们不妨令 p=k+1 这样我们就得到了一个函数（下文称 M(x)）使得：

M(x)=\begin{cases} 0 & x>0\\ x &x<0 \end{cases}

我们把它乘上 -2 在加上 x 这样不就得到了：

-2M(x)+x=\begin{cases}x & x>0\\ -x & x<0\end{cases}

好耶！

还有个小问题：

T(x)\times2^p= \begin{cases} 2^p &x>0\\ 2^{p-1} &x=0\\ 0 & x<0 \end{cases}

如果 x 等于 0 时减去 T(x)\times2^p 就少减了。

我们可以对 x 加上一个很小的数如 10^{-10} 这样就可以把 0 当正数处理当然减去也行。

可这样就 15 行了。

我们把 -2M(x)+x 展开：

-2(2^{k+2}(S(\frac{1}{x^k}+T(x)\times2^p)-\frac{1}{2})-T(x)\times2^p)+x= -2^{k+3}(S(\frac{1}{x^k}+T(x)\times2^p)-\frac{1}{2})+2T(x)\times2^p+x

我们可以让 p=k+2 这样就可以少一个乘 2。

答案就是：

T(x)=S((x+10^{-10})\times2^q) -2^{k+3}(S(\frac{1}{x^k}+T(x)\times2^p)-\frac{1}{2})+T(x)\times2^p+x

代码如下（k,q,p 取的值是紫钦大佬的，下面大部分都是这样，膜拜！）

I
C 1 0.0000000001
< 2 41
S 3
< 4 180
> 1 178
+ 6 5
S 7
C 8 -0.5
< 9 181
- 10
+ 11 5
+ 12 1
O 13

Task 5

输入：a_1, \dots, a_{32}

输入限制：a_1, \dots, a_{32} \in \{0, 1\}

输出：把 a_1, \dots, a_{32} 从左到右看成一个二进制整数，高位在左低位在右，输出该整数的值。

满分行数：95 行

难度：送分

又是一道送分点，每一位都向都左移一下，加一起就行。只要别干移 0 位这种无意义的事就行。

代码如下：

for(int i=1;i<=32;++i) printf("I\n");
for(int i=1;i<=31;++i) printf("< %d %d\n",i,32-i);
printf("+ 63 32\n");
for(int i=33;i<=63;++i) printf("+ %d %d\n",i,i+31);
printf("O 94");

Task 6

输入：a

输入限制：0 \le a \lt 2^{32}，a 为整数。

输出：输出 32 个整数，从高位到低位输出 a 的二进制表示（不足 32 位的在高位补 0）。

满分行数：190 行

难度：大众

又搞 0 和 1 自然而然想到 S 函数。

我们如何判断呢？

我们可以用和手动计算差不多的方法来算，但还得倒序，很难受，下面说一种从高位到低位取的方法。

我们先取最高位：

先将 a 减去 2^{31}，如果这一位为 1，这时应该为正数，否则为负数，判正负，这不就是 \text{Task 3} 吗？这里左移 41 位，丢进 S 里，得 S(2^{41}(a-2^{31}))=S(2^{41}a-2^{72})，然后我们输出结果，当然还有可能遇到 S(0)=\frac{1}{2} 的情况，我们要加上10^{-10}，根据跑出来的 S 减去这一位。

当然我们发现左移41位，可以提前做，但我们要提前跑出 2^{42} 到 2^{72} 的值，用 checker 跑，也可以 Python，还可以用 __int128。

当然加上10^{-10}也可以提前做。

对于最后一位，我们只需右移 41 位就求了出来。

细细一算，取一位需要 6 行，而刚好 190=31 \times 6+4

但我们刚刚的方法却多了一行。

我们需要优化循环外的一行，我们可以把加上10^{-10}优化掉。

对于每次减去第一个减去 2 的幂的操作，我们少减去 10^{-10}\times 2^{41}\approx 220 这样就优化掉了一行。

因为当为 0 的时候，我们应该是判定这一位为 1，所以该减去 220。

代码如下：

printf("I\n");
printf("< 1 41\n");
for(int i=31,row=3;i>=1;i--,row+=6){
    printf("C %d -",row-1);
    cout<<str[i]<<endl;
    printf("S %d\n",row);
    printf("O %d\n",row+1);
    printf("- %d\n",row+1);
    printf("< %d %d\n",row+3,i+41);
    printf("+ %d %d\n",row-1,row+4);
}
printf("> 188 41\n");
printf("O 189\n");

这里的 str[i] 就不公开了，因为 2^{42} 到 2^{72} 的数太多了。

Task 7

输入：a,b

输入限制：0 \le a, b \lt 2^{32}，a,b 均为整数。

输出：a \oplus b

满分行数：605 行

难度：较难

首先我们知道，我们得对 a,b 转换二进制，结果还得转换回去，实际做异或的行数只有 226 行。差不多一个位的异或用 7 行。

我们先看异或的运算规则：

a \oplus b= \begin{cases} 0 &0\oplus 0, 1\oplus 1\\ 1 &0\oplus 1, 1\oplus 0 \end{cases}

我们的一个位，只有 7 行，我们应该如何构造呢？

我们可以先对 a,b 相加：

a + b= \begin{cases} 0 &0\oplus 0\\ 1 &0\oplus 1, 1\oplus 0\\ 2 &1\oplus 1 \end{cases}

你家异或长这样啊？！

别急我们可以对我们可以用 S 函数，来判断大小，具体操作如下：

S(2^p(a + b-0.5))= \begin{cases} 0 &0\oplus 0\\ 1 &0\oplus 1, 1\oplus 0\\ 1 &1\oplus 1 \end{cases} S(2^p(a + b-1.5))= \begin{cases} 0 &0\oplus 0\\ 0 &0\oplus 1, 1\oplus 0\\ 1 &1\oplus 1 \end{cases}

我们惊奇的发现我们把上面两个式子相减不就得到了吗？

但我们又发现这样写要 8 行。

我们可以只用上面的一个式子：

a+b-2S(2^p(a+b-1.5))=\begin{cases} 0 &0\oplus 0\\ 1 &0\oplus 1, 1\oplus 0\\ 0 &1\oplus 1 \end{cases}

就只要 7 行啦！还剩 2 行，估计是因为出题人怕我们不会减去 220 这个优化方式吧！（出题人人还怪好的嘞！）

代码太长了我给出异或的部分：

for(int i=?,j=1;j<=32;j++,i+=?)printf("+ %d %d\n",i,i+?);
for(int i=?,j=1;j<=32;j++,i++)printf("C %d -1.5\n",i);
for(int i=?,j=1;j<=32;j++,i++)printf("< %d 41\n",i);
for(int i=?,j=1;j<=32;i++,j++)printf("S %d\n",i);
for(int i=?,j=1;j<=32;j++,i++)printf("< %d 1\n",i);
for(int i=?,j=1;j<=32;j++,i++)printf("- %d\n",i);
for(int i=?,j=1;j<=32;j++,i++)printf("+ %d %d\n",i,i-?);

这里的参数需和你的代码匹配。

Task 8

输入：a

输入限制：\lvert a \rvert \le 10^9，小数部分不超过 9 位。

输出：\dfrac{a}{10}

满分行数：7 行

难度：奇门淫技

可以用乘法节点，得 6 分。

我们知道：

\frac{1}{10}=2^{-4}+2^{-5}+2^{-8}+2^{-9}+......

只要加足够多就可以接近答案了，但 7 个节点完全不够用。

这时我们要用 \text{Task 4} 的方法了。

还记得那条切线 y=\frac{1}{4}x+\frac{1}{2} 吗？

我们也可以找到一个数 \gamma 使得 {S}'(\gamma)=\frac{1}{10}。

\frac{e^{-x}}{(1+e^{-x})^2}=\frac{1}{10}

不妨令 e^{-x}=\beta

\frac{\beta}{(1+\beta)^2}=\frac{1}{10}

解得 \beta=4 \pm \sqrt{15}

我们用 4- \sqrt{15} 吧。

所以 \gamma=-\ln{(4-\sqrt{15})}=\ln(4+\sqrt{15})

算出来之后，我们可以写出一条在此处的切线：y=\frac{1}{10}(x-\gamma)+S(\gamma)

我们知道当 x 非常接近 \gamma 时，S(x) 将非常接近这条切线。

那么我们不妨求出 S(\frac{x}{2^k}+\gamma) 由于 \frac{x}{2^k} 很小，那么我们可以认为 S(\frac{x}{2^k}+\gamma)=\frac{1}{10}(\frac{x}{2^k}+\gamma-\gamma)+S(\gamma)=\frac{1}{10\times2^k}x+S(\gamma)

那么我们减去 S(\gamma) 再乘上 2^k 就得到了 \frac{1}{10}。

答案就是 (S(\frac{x}{2^k}+\gamma)-S(\gamma))\times 2^k

用计算器计算出 \gamma= 2.0634370688955605467272811726201。

再用 checker 算出 S(\gamma)= 0.887298334620741688517926539978236773937633025540819832675154107295416657242528255923059519。

代码如下：

I
> 1 178
C 2 2.0634370688955605467272811726201
S 3
C 4 -0.887298334620741688517926539978236773937633025540819832675154107295416657242528255923059519
< 5 178
O 6

Task 9

输入：a_1, \dots, a_{16}

输入限制：\lvert a_1 \rvert, \dots, \lvert a_{16} \rvert \le 10^9，小数部分不超过 9 位。

输出：输出 16 个实数，表示 a_1, \dots, a_{16} 从小到大排序后的结果。

满分行数：3000 行

难度：最难

首先这些计算节点太单一了，比汇编还要单一，我们也只能用冒泡排序等简单的排序了。

我们如何对两个数交换呢？

w=a+b
p=w-a
q=w-p

假如我们不要交换呢？

w=a+b
p=w-b
q=w-p

那假如我说 若 a<b 就交换否则就不交换呢？

w=a+b
p=w-min(a,b)=a+b-(min(a-b,0)+b)=a-min(a-b,0)
q=w-p

为啥要写成这样的样子呢？

我们是不是在 \text{Task 4} 得到过：

M(x)=\begin{cases} 0 & x>0\\ x &x<0 \end{cases}=\min(0,x)

这不刚好吗？

用一个数组来记录每个变量的位置，然后倒序输出即可。

代码如下：

int pos[20]={},row=16;
for(int i=1;i<=16;i++)pos[i]=i;
for(int i=1;i<=16;i++)printf("I\n");
for(int i=1;i<=16;i++){
    for(int j=1;j+i<=16;j++){
        printf("+ %d %d\n",pos[j],pos[j+1]);
        printf("- %d\n",pos[j+1]);
        printf("+ %d %d\n",pos[j],row+2);
        printf("C %d 0.00000000001\n",row+3);
        printf("< %d 41\n",row+4);
        printf("S %d\n",row+5);
        printf("< %d 179\n",row+6);
        printf("> %d 178\n",row+3);
        printf("+ %d %d\n",row+7,row+8);
        printf("S %d\n",row+9);//10
        printf("C %d -0.5\n",row+10);
        printf("< %d 180\n",row+11);
        printf("- %d\n",row+7);
        printf("+ %d %d\n",row+12,row+13);
        printf("- %d\n",row+14);
        printf("+ %d %d\n",pos[j],row+15);
        pos[j]=row+16;
        printf("- %d\n",row+16);
        printf("+ %d %d\n",row+1,row+17);
        pos[j+1]=row+18;
        row+=18; 
    }
}
for(int i=16;i>=1;i--)printf("O %d\n",pos[i]);

Task 10

输入：a,b,m

输入限制：0 \le a, b \lt 2^{32}，1 \le m \lt 2^{32}，a,b,m 均为整数。

输出： a \times b 除以 m 的余数。

满分行数：2000 行

难度：较难

先讲乘法：

显然有了前面的铺垫我们可以用二进制拆分的形式来计算。

我们可以将 b 的第 i 位和 2^ia 相乘。

现在问题变成构造函数：

a \times b=\begin{cases} 0 & b=0\\ a & b=1 \end{cases}

这和 \text{Task 4} 差不多。

我们可以用和 \text{Task 4} 差不多的方法：

S(\frac{x}{2^k}+2^p(b-1))=\begin{cases}0 &b=0\\ \frac{1}{2^{k+2}}x+\frac{1}{2}& b=1\end{cases}

一样令 p=k+1 得：

2^{k+2}(S(\frac{x}{2^k}+2^p(b-1))-\frac{1}{2})-2^p(b-1)=\begin{cases}0 &b=0\\ x& b=1\end{cases}

现在就解决啦！

接着是取模：

我们可以用做减法我们不妨将 2^0m,2^1m,.....2^{63}m 算出来，再从高往低地去减，就得到了答案。

代码如下：

printf("I\nI\nI\n");
printf("< 2 41\n");
for(int i=31,j=5;i>=1;i--,j+=14){
    if(i==31)printf("C %d -",j-1);
    else printf("C %d -",j-10);
    cout<<str[i]<<endl;
    printf("S %d\n",j);
    printf("- %d\n",j+1);
    printf("< %d %d\n",j+2,i+41);
    if(i==31)printf("+ %d %d\n",j-1,j+3);
    else printf("+ %d %d\n",j-10,j+3);
    printf("C %d -1\n",j+1);
    printf("< %d 151\n",j+5);
    printf("> 1 %d\n",150-i);
    printf("+ %d %d\n",j+7,j+6);
    printf("S %d\n",j+8);
    printf("C %d -0.5\n",j+9);
    printf("< %d 152\n",j+10);
    printf("- %d\n",j+6);
    printf("+ %d %d\n",j+12,j+11);
}
printf("> 429 41\n");
printf("C 439 -1\n");
printf("< 440 151\n");
printf("> 1 150\n");
printf("+ 442 441\n");
printf("S 443\n");
printf("C 444 -0.5\n");
printf("< 445 152\n");
printf("- 441\n");
printf("+ 446 447\n");
printf("+ 18 448\n");
for(int i=1,j=32,k=449;i<=30;i++,j+=14,k+=1)printf("+ %d %d\n",j,k);
printf("C 479 0.00000000001\n");
    for(int i=64,j=481;i>=0;i--,j+=15){
    printf("< 3 %d\n",i);
    printf("- %d\n",j);
    printf("+ %d %d\n",j+1,j-1);
    printf("< %d 41\n",j+2);
    printf("S %d\n",j+3);
    printf("C %d -1\n",j+4);
    printf("< %d 151\n",j+5);
    printf("> %d 150\n",j+1);
    printf("+ %d %d\n",j+7,j+6);
    printf("S %d\n",j+8);
    printf("C %d -0.5\n",j+9);
   printf("< %d 152\n",j+10);
    printf("- %d\n",j+6);//12
    printf("+ %d %d\n",j+12,j+11);
    printf("+ %d %d\n",j+13,j-1);
}
printf("O 1455\n");

总结

  2. 细心！细心！ 细心！

  3. 脑洞！脑洞！脑洞！