自动搬运

查看原文

来自洛谷，原作者为

	tx344 AFOer

搬运于2025-08-24 22:18:55，当前版本为作者最后更新于2023-01-16 22:19:01，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

[eJOI2019] 塔

题面

从序列中选择一段连续序列，将序列和加入序列，求最小操作次数生成 $n$。

分析

初看感觉没什么思路。

1. 先考虑每次操作都选择整个序列

多次操作后序列为：

我们能发现 $a_i=2^{i-2}\ (i>1)$。

2. 试着对于某次操作不选择整个序列

随便选择一次操作，

这个序列只是将原序列中的 $8$（即第 $4$ 次操作）变为：

后面的操作还是选择整个序列。

我们发现，当 $a_5$ 减少了 $1$，$a_{6+i}$ 就会减少 $2^i$。

换句话说，当 $a_{n-i-1}$ 减少了 $1$，$a_n$ 就能减少 $2^i$。

那么我们是不是可以只令 $n$ 以前的某些数减少 $1$（即不选择 $a_1$）就可以让 $a_n$ 变为我们想要的数。

所以我们对于任意一次操作，只用考虑从 $a_1$ 或 $a_2$ 开始选择整个序列

3. 实现

例如：

我们要得到 $59$，那么肯定使 $64$ 变为 $59$ 最优。

让 $64$ 变为 $59$ 就要让 $64$ 减少 $5$。

等同于让 $64$ 减少 $(2^2+2^0)$。

所以从 $64$ 往前看，只要让第 $4$ 和 $6$ 次操作都不选择整个序列（即不选择 $a_1$），而其他操作还是选择整个序列就可以得到 $59$。

所以我们先让每次操作都选择整个序列，对于要得到的数 $q$，只用先求出将哪个数变成 $q$，再将 $2^t-q$ 二进制分解一下，确定哪几次操作不选择 $a_1$。

4. 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n,m,now,t,ans[70];
signed main()
{
//	freopen("tower.in","r",stdin);
//	freopen("tower.out","w",stdout);
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld",&n);m=1;
		if(n==1){puts("0");continue;}
		t=1;ans[1]=1;
		while(m<n)
		{
			t++;
			ans[t]=1;
			m<<=1;
		}
		n=m-n;
		now=t-1;
		printf("%d\n",t);
		while(n)
		{
			if(n&1)ans[now]=2;
			now--;
			n>>=1;
		}
		for(int i=1;i<=t;i++)printf("%d %d\n",ans[i],i);
	}
}