自动搬运

查看原文

来自洛谷，原作者为

	revenger **

搬运于2025-08-24 21:37:42，当前版本为作者最后更新于2017-03-26 17:04:44，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一道找规律的好题【雾

在只有一个环n的时候，我们要拆下来这个环，就要装上环n-1，拆掉n，再拆掉n-1；

装上和拆掉一个环的步数是相同的。设t(n)表示对一个环n进行操作(拆下或者安上)需要的步数，可以得出t(n)=2*t(n-1)+1,t(1)=1

再归纳总结一下，t(n)=2^n -1;

再观察有两个环的情况：我们设有环a,b(a>b)被连上，在拆下a之前我们一定会安装b，而安装b所需要的步数是t(b)，当b原本就被连接的情况下，我们就能从总步数中省下操作b的步数，所以总步数应为t(a)-t(b)。

观察有三个环的情况：设有环a,b,c(a>b>c)被连上，观察环a,b:根据上一条，原本的步数t(a)中省下了对b进行操作的步数，这里对b进行操作的步数本应为t(b),但是观察b,c我们发现:根据上一条，因为有了c的存在，导致此次对b的操作步数从t(b)变为了t(b)-t(c)。综合一下发现，对三个环a,b,c进行操作所需要的步数为t(a)-(t(b)-t(c))=t(a)-t(b)+t(c)。

对以上进行总结，能够推导出对于若干个环a,b,c,d,e,……(a>b>c>d>e>……)进行操作的步数应为t(a)-t(b)+t(c)-t(d)+t(e)……

预处理一下t数组，然后从后往前按照-和+的变化进行计算。

n<=1000，2^1000-1需要用高精度进行计算。

附代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct st{
    int a[1000];
    int len;
}t[1001],ans;
int f[1001],s[1001],n,x,m;
#define max(a,b) a>b?a:b
st rol(st x)
{
    st c=x;
    for(int i=c.len;i;i--)
    {
        c.a[i]<<=1;
        if(c.a[i]>9)
        c.a[i+1]++,c.a[i]-=10; 
    }
    if(c.a[c.len+1]) c.len++;
    return c;
}
st add(st x,st y)
{
    st c=x;
    c.len=max(c.len,y.len); 
    for(int i=1;i<=c.len;i++)
    {
        c.a[i]=c.a[i]+y.a[i];
        if(c.a[i]>9)
        c.a[i+1]++,c.a[i]-=10;
    }
    if(c.a[c.len+1]) c.len++;
    return c;
}
st sub(st x,st y)
{
    st c=x;
    for(int i=1;i<=c.len;i++)
    {
        c.a[i]-=y.a[i];
        if(c.a[i]<0)
        c.a[i]+=10,c.a[i+1]--;
    }
    while(!c.a[c.len]) c.len--;
    return c; 
}
void print(st x)
{
    for(int i=x.len;i>=1;i--)
    printf("%d",x.a[i]);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&f[i]);
        if(f[i]) m=i;
    }
    x=2;
    for(int i=m;i;i--)
    if(f[i])
    {
        s[i]=x;
        x^=1;
    }
    t[1].len=t[1].a[1]=1;
    for(int i=2;i<=m;i++)
    {
        t[i]=rol(t[i-1]);
        t[i].a[1]++;
    }
    ans=t[m];
    for(int i=m-1;i;i--)
    {
        if(s[i]==2)
        ans=add(ans,t[i]);
        if(s[i]==3)
        ans=sub(ans,t[i]);
    }
    print(ans);
}