【题解】论一条咸鱼闲起来能多咸之旷野大计算 ——litble

于由litble发布

有一条咸鱼又菜又颓，今天的空气中间弥漫着一股睡眠的气息，所以咸鱼做了一下著名的 “旷野大计算”。

test1

非常简单。

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

test2

非常简单。

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

test3

可以利用一下精度的性质。
我们可以将这个 a 乘以一个很大很大的数，这样，如果它是 0，那么 S 一下的结果就是 0.5，如果它大于 0，那么 S 一下就是 1，如果小于 0 就是 0.
然后脑补一下怎么把这三个结果处理成-1,0,1 的形式就成了。

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

test4

MAYA 这是人做的点吗？Orz VFK 太强啦！
考虑利用一下求导的基本手法（虽然咸鱼不会求导），得知当 x 的绝对值非常小时，s(x) 可以近似看作 $\frac{x}{4}+0.5$。
假定这个性质在这个 test 里面是会被用到的，人类的第六感告诉我们，负数要用这个性质的可能性更大。所以我们先尝试构造一个数 $p$，使得当 x 为正的时候，$p$非常大（因为这个非常大一般构造为 $2^{k_1}$的形式，所以我们姑且认为此时 $p=2^{k_1}$）。而 x 为负的时候，$p=0$。
然后我们令 $y=s(\frac{x}{2^{k_2}}+p)$，这样当 x 为正的时候，$y=1$，否则 $x=0.5+\frac{x}{2^{k_2+2}}$。
这有什么好处呢？$(0.5-y)*2^{k_2+3}=-2x$，于是我们就把负数这部分搞完了。
而如果 x 是正数的话，这样操作以后的结果就是：$-2^{k_2+2}$，我们就要试图把这个东西搞掉。
想起有一个数在 x 为负数时是 0 而在 x 是正数时不是，那就是 $p$，所以我们加上一个 p 要使得 $-2^{k_2-2}=0$。
那么使得 $k_1=k_2+2$即可。
至于 $p$怎么构造呢，VFK 给出的代码已经说了：

In(x);
p=S((x+1e-30)<<500)<<152;//加上 1e-30 是为了处理 0
y=S((x>>150)+p);
r=x+((-y+0.5)<<153)+p;
Out(r);

呃，所以答案就是这样的，能构造出来真是太强了吧：

I
C 1 0.000000000000000000000000000001
< 2 500
S 3
< 4 152
> 1 150
+ 5 6
S 7
- 8
C 9 0.5
< 10 153
+ 1 11
+ 12 5
O 13

test5

比较简单，直接模拟就好。注意不要进行无效操作（比如将 $a_{32}$左移 0 位啦）

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int main()
{
    freopen("nodes5.out","w",stdout);
    puts("I"),puts("< 1 31");
    for(RI i=2;i<32;++i) {
        puts("I");
        printf("< %d %d\n",3*(i-1),32-i);
        printf("+ %d %d\n",3*i-4,3*i-2);
    }
    puts("I"),puts("+ 92 93"),puts("O 94");
    return 0;
}

test6

思路：每次计算一下 $S((x-2^{k})*2^{500})$，就可以获得 0 和 1。
但是每次都左移 500 位非常浪费节点，可以一开始将 x 左移 500 位，然后每次用高精度算出 $2^{500+k}$。
这样我们每次求一位，要 C 一次，S 一次,O 一次。然后继续变形 x，减去其最高位，假设这一位是 t（t=0 或 1), 那就是要左移一次 t, 一次 t，x 再加上一次-t，一共要进行 6 次操作。
注意到最后一位可以直接将 x 右移 500 位变回来然后输出，就可以节约一点点操作，正好 190 个节点。
但是这样写了会 WA，因为如果某一次 $x==2^{k}$，那么就算乘极大数最后结果也是 0，$S(0)=0.5$。
所以我们要把 $2^{k}$稍微弄小一点点，这样如果 $x==2^{k}$算出来就是 1 了。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
struct node{int len,t[1000];}a[33];
void mul(int o) {
    int ys=0;
    for(RI i=1;i<=a[o].len;++i) {
        a[o].t[i]=a[o].t[i]*2+ys;
        ys=a[o].t[i]/10,a[o].t[i]%=10;
    }
    if(ys) a[o].t[++a[o].len]=ys;
}
void print(int o) {
    for(RI i=a[o].len;i>=1;--i) printf("%d",a[o].t[i]);
    puts("");
}
int main()
{
    freopen("nodes6.out","w",stdout);
    a[1].len=1,a[1].t[1]=1;
    for(RI i=1;i<=501;++i) mul(1);
    for(RI i=2;i<=31;++i) a[i]=a[i-1],mul(i);
    puts("I");
    puts("< 1 500");
    for(RI i=31;i>=1;--i) {
        int k=(32-i)*6-4;a[i].t[60]=0;
        printf("C %d -",k),print(i);
        printf("S %d\n",k+1);
        printf("O %d\n",k+2);
        printf("- %d\n",k+2);
        printf("< %d %d\n",k+4,i+500);
        printf("+ %d %d\n",k+5,k);
    }
    puts("> 188 500");
    puts("O 189");
    return 0;
}

test7

思路：首先使用上面那种方法，将两个数的二进制转化出来。由于不用输出，所以一共消耗 316 个节点，剩余平均每次异或可以使用 9 个节点。
观察什么叫做异或，发现当这两位加起来为 1 的时候，结果为 1。加起来为 2 或者为 0，结果都是 0. 设这个和为 y.
那么怎么把这个 2 搞成 0 呢？显然我们是要利用 2 比较大这个性质，让某一个东西去减去 y.
那么就是用 S 构造一个当输入 1 和 2 的时候输出 1，否则输出 0 的东西。
也就是求一下 $S((y-0.5)\times 2^{500}) \times 2-y$。
数一下发现正好是 9 次操作，由于左移 0 位没有意义之类的，我们还可以节约几次操作呢。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
struct node{int len,t[1000];}a[33];
void mul(int o) {
    int ys=0;
    for(RI i=1;i<=a[o].len;++i) {
        a[o].t[i]=a[o].t[i]*2+ys;
        ys=a[o].t[i]/10,a[o].t[i]%=10;
    }
    if(ys) a[o].t[++a[o].len]=ys;
}
void print(int o) {
    for(RI i=a[o].len;i>=1;--i) printf("%d",a[o].t[i]);
    puts("");
}
int main()
{
    freopen("nodes7.out","w",stdout);
    int now=0,las=0;
    a[1].len=1,a[1].t[1]=1;
    for(RI i=1;i<=501;++i) mul(1);
    for(RI i=2;i<=31;++i) a[i]=a[i-1],mul(i);
    puts("I"),puts("I");
    puts("< 1 500"),puts("< 2 500"),now=4;
    for(RI i=31;i>=1;--i) {
        a[i].t[60]=0;
        int k1=(i==31?3:(30-i)*10+9),k2=(31-i)*10+4;
        printf("C %d -",k1),print(i),++now;
        printf("S %d\n",now),++now;
        printf("- %d\n",now),++now;
        printf("< %d %d\n",now,i+500),++now;
        printf("+ %d %d\n",now,k1),++now;
        printf("C %d -",k2),print(i),++now;
        printf("S %d\n",now),++now;
        printf("- %d\n",now),++now;
        printf("< %d %d\n",now,i+500),++now;
        printf("+ %d %d\n",now,k2),++now;
    }
    puts("> 309 500"),puts("> 314 500"),now=316;
    for(RI i=31;i>=0;--i) {
        int k1=(i==0?315:(31-i)*10+6),k2=(i==0?316:(32-i)*10+1);
        printf("+ %d %d\n",k1,k2),++now;
        printf("C %d -0.5\n",now),++now;
        printf("< %d 500\n",now),++now;
        printf("S %d\n",now),++now;
        printf("+ %d %d\n",now,now),++now;
        printf("- %d\n",now-4),++now;
        printf("+ %d %d\n",now,now-1),++now;
        if(i!=0) printf("< %d %d\n",now,i),++now;
        if(i!=31) printf("+ %d %d\n",las,now),++now;
        las=now;
    }
    printf("O %d\n",las);
    return 0;
}

test8

呃，根据求导的特性，当 x 很小的时候，拟合一种斜率，使得 $\frac{S(x)-S(0)}{x}=0.1$，就可以很方便地解决该题。
那么我们把 x 除以一个很大的数，然后再加上一个数 k，现在我们求使得 $\frac{S(k)-S(0)}{k}=0.1$成立的 k，就可以近似算出 $0.1k+0.1 \times \frac{x}{2^{d}}$了。
如何求这个 k 呢？考虑利用 checker 三分法求解。
虽然这样理论可行，但是我太菜了愣是搞了一个小时没搞出来，所以偷偷抄了洛谷的题解 QAQ

I
> 1 96
C 2 -0.962423650119206894995517826848736846270368668771321039322036337680327735216443548824018858
S 3
C 4 -0.276393202250021030359082633126872376455938164038847427572910275458947907436219510058558559
< 5 95
O 6

test9

使用冒泡排序。
比较两个数 a,b，使小的在前，大的在后，出题人已经构造了一种方法：

t=a+b;
a=min(b-a,0)+a;
b=t-a;

然后这个 min(x,0)的做法可以参照第 4 个测试点：

p=S((x+1e-30)<<500)<<152;
y=S((x>>150)+p);
r=((y-0.5)<<152)-p;

嗯，就是这样。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int b[20],now,BAS=16;
int main()
{
    freopen("nodes9.out","w",stdout);
    for(RI i=1;i<=BAS;++i) puts("I"),b[i]=i,++now;
    for(RI i=1;i<BAS;++i)
        for(RI j=1;j<=BAS-i;++j) {
            int t,x,p,y,r,ka;
            printf("+ %d %d\n",b[j],b[j+1]),++now,t=now;//t
            printf("- %d\n",b[j]),++now,ka=now;//-a
            printf("+ %d %d\n",b[j+1],ka),++now,x=now;//b-a
            printf("C %d 0.00000000000000000000000000001\n",x),++now;
            printf("< %d 500\n",now),++now;
            printf("S %d\n",now),++now;
            printf("< %d 152\n",now),++now,p=now;//p
            printf("> %d 150\n",x),++now;
            printf("+ %d %d\n",now,p),++now;
            printf("S %d\n",now),++now,y=now;
            printf("C %d -0.5\n",y),++now;
            printf("< %d 153\n",now),++now;
            printf("- %d\n",p),++now;
            printf("+ %d %d\n",now,now-1),++now;
            printf("> %d 1\n",now),++now,r=now;//r
            printf("+ %d %d\n",r,b[j]),++now,b[j]=now;
            printf("- %d\n",now),++now;
            printf("+ %d %d\n",t,now),++now,b[j+1]=now;
        }
    for(RI i=1;i<=BAS;++i) printf("O %d\n",b[i]);
    return 0;
}

test10

考虑用一个类似于快速幂的 “快速乘” 来实现。
那么首先把 b 转化为 2 进制，然后如果这一位是 1，就加上 $a \times 2^k$。
考虑用一个类似于 test4 的方法来实现这个功能。
设 bk 为 b 的第 k 位，先算出 y=S((bk-1)&lt;&gt;150));，如果 bk=0，则 y=0, 否则 $y=\frac{a}{2^{152}}+\frac{1}{2}$。
然后算 r=(y*2-bk)&lt;&lt;151，这样如果 bk=0 就是 0，否则就是 a，就可以很方便地计算了。
至于取模，可以利用 test3 的那个函数，$a-m \times 2^k$大于 0 时等于 1，否则等于 0. 然后等于 1 时减 $m \times 2^k$，否则减 0，利用以上操作实现。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
struct node{int len,t[1000];}a[33];
void mul(int o) {
    int ys=0;
    for(RI i=1;i<=a[o].len;++i) {
        a[o].t[i]=a[o].t[i]*2+ys;
        ys=a[o].t[i]/10,a[o].t[i]%=10;
    }
    if(ys) a[o].t[++a[o].len]=ys;
}
void print(int o) {
    for(RI i=a[o].len;i>=1;--i) printf("%d",a[o].t[i]);
    puts("");
}
int ka,kb,kc,re,now,BAS=31;
int b[35];
void prework() {
    puts("< 2 500"),++now;
    for(RI i=BAS;i>=1;--i) {
        a[i].t[60]=0;
        printf("C %d -",now),print(i),++now;
        printf("S %d\n",now),++now,b[i]=now;
        printf("- %d\n",now),++now;
        printf("< %d %d\n",now,i+500),++now;
        printf("+ %d %d\n",now,now-4),++now;
    }
    printf("> %d 500\n",now),++now,b[0]=now;
}
void mul() {
    for(RI i=0;i<=BAS;++i) {
        int t;
        printf("C %d -1\n",b[i]),++now;
        printf("< %d 500\n",now),++now;
        printf("> %d 150\n",ka),++now;
        printf("+ %d %d\n",now,now-1),++now;
        printf("S %d\n",now),++now;
        printf("+ %d %d\n",now,now),++now;
        printf("- %d\n",b[i]),++now;
        printf("+ %d %d\n",now,now-1),++now;
        printf("< %d 151\n",now),++now,t=now;
        if(re) printf("+ %d %d\n",re,t),++now;
        re=now;
        printf("+ %d %d\n",ka,ka),++now,ka=now;
    }
}
void mo() {
    for(RI i=BAS*2+1;i>=0;--i) {
        int orz,t;
        printf("< %d %d\n",kc,i),++now,t=now;
        printf("+ %d %d\n",re,now),++now;
        printf("C %d 0.5\n",now),++now;
        printf("< %d 500\n",now),++now;
        printf("S %d\n",now),++now,orz=now;

        printf("C %d -1\n",orz),++now;
        printf("< %d 500\n",now),++now;
        printf("> %d 150\n",t),++now;
        printf("+ %d %d\n",now,now-1),++now;
        printf("S %d\n",now),++now;
        printf("+ %d %d\n",now,now),++now;
        printf("- %d\n",orz),++now;
        printf("+ %d %d\n",now,now-1),++now;
        printf("< %d 151\n",now),++now;
        printf("+ %d %d\n",re,now),++now,re=now;
    }
    printf("O %d\n",re);
}
int main()
{
    freopen("nodes10.out","w",stdout);
    a[1].len=1,a[1].t[1]=1;
    for(RI i=1;i<=501;++i) mul(1);
    for(RI i=2;i<=31;++i) a[i]=a[i-1],mul(i);
    puts("I"),puts("I"),puts("I"),ka=1,kb=2;
    puts("- 3"),kc=now=4;
    prework();mul();mo();
    return 0;
}

总结

  1. 哈哈哈哈我没疯放开我我怎么可能做一道旷野造计算机就疯了呢哈哈哈哈
  2. litble 真的是闲的蛋疼。
  3. 巧妙利用减大的数会比较小，减小的数会比较大的性质。
  4. 扯清楚每次操作的上一个节点是什么很重要。
  5. 巧妙利用 S 的性质。
  6. 真爱生命，远离旷野大计算。
分类： 文章

litble

苟...苟活者在淡红的血色中，会依稀看见微茫的希望

1 条评论

songlc · 2018年11月3日 9:52 下午

huaji

回复

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注