自动搬运

查看原文

来自洛谷，原作者为

	WsW_ 欢迎入群872763867||题解求赞！题解看不懂请私信

搬运于2025-08-24 21:14:50，当前版本为作者最后更新于2023-09-26 23:24:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路一

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

• 操作 $\mathtt{1}$，收益为 $1$。
• 操作 $\mathtt{dup}$，收益为 $top$。
• 操作 $\mathtt{add}$，收益为 $0$。

第一次操作一定是操作 $\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;
}