UVA_763
这个AC得有点晕晕乎乎的，我只是找到了一个可行的方式可以构造出来结果。
首先我们可以看到，input的序列实际上代表着每一个斐波那契数的数量0或者1，那么它们之间的运算应该也满足斐波那契通项的运算f(n)=f(n-1)+f(n-2)。在纸上画了一下，发现对于任意一个局部而言，也就两种形式的运算。
①例如001+010=100，或者写成011=100，这个就对应着f(n-1)+f(n-2)=f(n)。
②例如0100+0100=1001，或者写成0200=1001，这个就对应这f(n)+f(n)=f(n)+f(n-1)+f(n-2)=f(n+1)+f(n-2)。当然这个式子根据0200中2所在位置的不同表现的形式略有不同，可以分三种情况，2在最后1位（即代表1的个数），2在倒数第二位（即代表2的个数），以及在其他的位置，具体的运算形式类似，就不一一写了。
根据上面的分析，我们可以先将input的两个序列相加，然后不断得从后向前扫描数组并做上述两种转换运算，由于两种操作都是不可逆的，必然在某一时刻序列就不再进行变化了，这时就是最终结果了。
顺便再说一下，我们要把数组开多大呢？实际上最大的结果就是前100个fibonacci数的和的2倍，而S(n)=F(n+2)-1，所以最后结果一定不会超过110位的。
#include<stdio.h>
#include<string.h>
#define MAXD 150
char a[MAXD], b[MAXD];
int ans[MAXD];
void solve()
{
int i, j, k;
memset(ans, 0, sizeof(ans));
k = strlen(a) - 1;
for(i = k, j = 0; i >= 0; i --, j ++)
ans[j] += a[i] - '0';
k = strlen(b) - 1;
for(i = k, j = 0; i >= 0; i --, j ++)
ans[j] += b[i] - '0';
for(;;)
{
for(i = 0; i < 110; i ++)
{
if(ans[i] && ans[i + 1])
{
-- ans[i];
-- ans[i + 1];
++ ans[i + 2];
break;
}
else if(ans[i] > 1)
{
ans[i] -= 2;
if(i == 0)
++ ans[i + 1];
else if(i == 1)
{
++ ans[i + 1];
++ ans[i - 1];
}
else
{
++ ans[i + 1];
++ ans[i - 2];
}
break;
}
}
if(i == 110)
break;
}
for(i = 110; i > 0; i --)
if(ans[i])
break;
for(; i >= 0; i --)
printf("%d", ans[i]);
printf("\n");
}
int main()
{
int t = 0;
while(scanf("%s%s", a, b) == 2)
{
if(t ++)
printf("\n");
solve();
}
return 0;
}