问题描述
问题分析
对于由所有1构成的字符串而言，用f(n)表示其长度为n时的可能数，有以下的情形：
长度为1时，即“1”，无法合并，只有,1种可能；
长度为2时，即“11”，只有一种合并方法，字符串可以变为“11”，或“2”，有2种可能;
长度为n时，它的长n-1的串与1连接有f(n-1)种情况，或者它的第n-1个1与第n个1合并为2，有f(n-2)种可能，合计有f(n-2)+f(n-1)种可能。
所以可以使用斐波那契数列的思路写
因为数字太大
所以需要使用字符串模拟
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include<stdio.h>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
string F[1020]= {"0","1","2"};
string add(string a,string b) {
a="0"+a;
int la=a.length();
int lb=b.length();
for(int i=1; i<=la; i++) {
if(lb-i>=0)
a[la-i]+=b[lb-i]-'0';
if(a[la-i]-'0'>9) {
a[la-i]-=10;
a[la-i-1]++;
}
}
while(a[0]=='0')
a.erase(0,1);
return a;
}
int main() {
for(int i=3; i<1002; i++) {
F[i]=add(F[i-1],F[i-2]);
}
int T;
scanf("%d",&T);
while(T--) {
char s[220];
scanf("%s",&s);
cout<<F[strlen(s)]<<endl;
}
return 0;
}
|
题目地址:【杭电】[1865]1sting