GitBook

这里写图片描述 这里写图片描述

对于由所有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)种可能。

所以可以使用斐波那契数列的思路写 因为数字太大 所以需要使用字符串模拟

#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