题意:电脑机器翻译,1会翻译成0 1,0会翻译成1 0,问现在有一个数字1在n步后有这段序列中存在多少对0。


我们先来找下规律

1

01

1001

01101001

1001011001101001

......

我们可以发现,当前位置n成对的0都来自于两个地方:

1、n-2中1的个数

2、n-2中00的个数

找到规律后打个表就好了。

不过这里要注意,给出的n达到了1000,2^1000这个数就很大了,所以我们要使用大数计算,然后我捡了两个大数计算方法,用的string,不会报错,很万幸!


代码:

Memory: 2208 KB
Time: 0 MS
Language: G++
Result: Accepted

(用C++编译竟然报错,用G++编译才过,很尴尬。。。)


#include <iostream>
#include <algorithm>
#define MAX 1010
using namespace std;
string sum(string s1,string s2)
{
    if(s1.length()<s2.length())
    {
        string temp=s1;
        s1=s2;
        s2=temp;
    }
    int i,j;
    for(i=s1.length()-1,j=s2.length()-1;i>=0;i--,j--)
    {
        s1[i]=char(s1[i]+(j>=0?s2[j]-'0':0));   //注意细节
        if(s1[i]-'0'>=10)
        {
            s1[i]=char((s1[i]-'0')%10+'0');
            if(i) s1[i-1]++;
            else s1='1'+s1;
        }
    }
    return s1;
}
string Multiply(string s,int x)  //大数乘以整形数
{
    reverse(s.begin(),s.end());
    int cmp=0;
    for(int i=0;i<s.size();i++)
    {
        cmp=(s[i]-'0')*x+cmp;
        s[i]=(cmp%10+'0');
        cmp/=10;
    }
    while(cmp)
    {
        s+=(cmp%10+'0');
        cmp/=10;
    }
    reverse(s.begin(),s.end());
    return s;
}
int main()
{
    int n;
    string num[MAX],ans[MAX];
    num[1]='1';
    for(int i=2;i<MAX;i++)num[i]=Multiply(num[i-1], 2);
    ans[1]='0';ans[2]='1';
    for(int i=3;i<MAX;i++)ans[i]=sum(num[i-2], ans[i-2]);
    while(cin>>n){
        cout<<ans[n]<<endl;
    }
    return 0;
}