题解 P2438 【[SDOI2005]解环】
一道找规律的好题【雾
在只有一个环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);
}