HDU 1865 1sting 斐波那契数列 + 大数加法

题目：

http://acm.hdu.edu.cn/showproblem.php?pid=1865

题意：

给定一个长度不超过200的只有1的字符串，可以把相邻的两个1合并为2，问合并后有多少种不同的字符串

思路：

很容易发现答案是斐波那契数列，只不过200项会溢出，所以要用大数

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <cmath>
#include <queue>
using namespace std;

typedef long long ll;
const int N = 210;
char arr[N][N];
void add(char *s,char *s1,char *s2)
{
    int len1 = strlen(s1),len2 = strlen(s2);
    reverse(s1,s1 + len1);
    reverse(s2,s2 + len2);
    int t = 0;
    for(int i = 0; i < len1 || i < len2; i++)
    {
        t += i < len1 ? s1[i]-'0' : 0;
        t += i < len2 ? s2[i]-'0' : 0;
        s[i] = t % 10 + '0';
        t /= 10;
    }
    if(t) s[max(len1,len2)] = t + '0';
    int len = strlen(s);
    reverse(s,s + len);
    reverse(s1,s2 + len2);
}
void table()
{
    memset(arr,0,sizeof arr);
    arr[1][0] = '1',arr[2][0] = '2';
    for(int i = 3; i <= 200; i++)
        add(arr[i],arr[i-2],arr[i-1]);
// for(int i = 1; i <= 200; i++)
// printf("%sn",arr[i]);
}
int main()
{
    int t;
    table();
    scanf("%d",&t);
    while(t--)
    {
        char str[N];
        scanf("%s",str);
        int len = strlen(str);
        printf("%sn",arr[len]);
    }
    return 0;
}

（编辑：温州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!