[eJOI2019] 塔

tx344 · 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);
    }
}