题解 B3753 堆栈计算机

· · 题解

思路一

我们需要使栈中所有元素之和为 n，再全部加起来即可。
最简单的方法是直接往栈中放 n 个 1，似乎一个点都过不了。
为了使操作次数尽可能少，我们需要最大化单次的收益。收益指让栈中的元素之和增加了多少。

第一次操作一定是操作 \mathtt{1}，因为此时栈中还没有数字。 如果之后我们重复依次执行操作 \mathtt{dup} 和 \mathtt{add}，那么执行 2x 次操作后，栈中的数字变成了 2^x。

将 n 拆成二进制，再按照上述方法制作二进制下 n 的每一位的数字即可。

能够获得 60\% 的分数。

代码和提交记录

#include<bits/stdc++.h>
#define lowbit(x) (x&-x)
using namespace std;
int n;
bool f=1;
void make(int x){
    puts("1");
    while((x>>1)>0){
        x>>=1;
        puts("dup");
        puts("add");
    }
}

int main(){
    scanf("%d",&n);
    while(n){
        make(lowbit(n));
        if(f)f=0;
        else puts("add");
        n-=lowbit(n);
    }
    return 0;
}

思路二

先看一个例子。

输入：

6

我们的代码会从 1 开始制作 2，再从 1 开始制作 4，最终加起来得到结果。

如果我们将制作出的 2 进行 \mathtt{dup}，再在复制的 2 的基础上制作 4，那么就可以省去一部分步骤。
这时我突然想到了快速幂的思想。我们一个变量记录栈顶元素，不停地对其进行 \mathtt{dup} 和 \mathtt{add}，如果二进制的 n 在这一位是 1，那就把它额外复制一遍留着，最终把所有保留的加起来即可。

代码和提交记录

#include<bits/stdc++.h>
#define lowbit(x) (x&-x)
using namespace std;
int n;
int x=1;
int cnt=-1;
bool f=1;

int main(){
    scanf("%d",&n);
    puts("1");
    while(x<n){
        cnt+=bool(x&n);//记录一下最终要加几个数
        if(x&n)puts("dup");//赋值保存下来
        n-=n&x;//将这一位变为0
        x<<=1;
        if(x<=n)puts("dup\nadd");//继续增长
    }
    while((cnt--)>=0)puts("add");
    return 0;
}