首页 > 代码库 > 1sting

1sting

2024-09-09 09:18:25   211人阅读

        You will be given a string which only contains ‘1’; You can merge two adjacent ‘1’ to be ‘2’, or leave the ‘1’ there. Surly, you may get many different results. For example, given 1111 , you can get 1111, 121, 112,211,22. Now, your work is to find the total number of result you can get.
InputThe first line is a number n refers to the number of test cases. Then n lines follows, each line has a string made up of ‘1’ . The maximum length of the sequence is 200.
      OutputThe output contain n lines, each line output the number of result you can get .
Sample Input

3
1
11
11111

Sample Output

1
2
8
自己找规律可得为Fibonacci数列，但递归到已为大位数运算，long long __int64皆不可以，最好的办法为开数组
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=1005;
int a[205][maxn];
int main()
{
  int n,i,j,count,T;
  for(i=0;i<=202;i++)
  {
    for(j=0;j<=1002;j++)
    {
      a[i][j]=0;
    }
  }
  a[1][0]=1;
  a[2][0]=2;
  for(i=3;i<=201;i++)
  {
    for(j=0;j<=1002;j++)
    {
      a[i][j]=a[i][j]+a[i-1][j]+a[i-2][j];
      if(a[i][j]>=10)
      {
        a[i][j]=a[i][j]-10;
        a[i][j+1]=a[i][j+1]+1;
      }
    }
  }
  cin>>T;
  while(T--)
  {
    char b[210];
    cin>>b;
    n=strlen(b);
    for(i=1002;i>=0;i--)
    {
      if(a[n][i]!=0)
      {
        count=i;
        break;
      }
    }
    for(i=count;i>=0;i--)
    {
      cout<<a[n][i];
    }
    cout<<endl;
  }
  return 0;
}

 

1sting


联系
我们