EOJ刷题记录第十弹

F - 借仙书 EOlymp - 2524

题目

Goran希望在仙界图书馆借一本书。这本书在仙界图书馆分为了两版发行，分别是a版和b版。这本书非常热门，图书馆的存量也非常大，并且摆放时也有规律：第0号书柜放的是a版，第1号书柜放的是b版，对于第k(k>1)个柜子，书的摆放方式就是重复将它前边两个书柜的排放方式，例如前几个书柜的顺序为:a,b,ab,bab,abbab,bababbab,abbabbababbab,…
当Goran在第N号书柜中选择其中的第k本书时，请你帮他判断这本书究竟是a版还是b版。（书柜从0开始编号，书柜中的书从1开始编号）

数据输入
第1行一个整数T，表示接下来Goran要选T次书。
接下来有T行，每行2个由空格分隔的整数N,K,表示Goran在第N号书柜选择第K本书

1≤T≤100
1≤N≤50
k不超过当前书柜中书的数量，并且k≥1

数据输出
输出有T行，每行输出字符a或b，表示对于Goran每次选的书，这本书是a版还是b版

样例
输入样例
4
0 1
1 1
3 2
7 7
输出样例
a
b
a
a

思路

一开始尝试直接将所有字符串存下来后直接查找，发现程序运行没反应。当测试了斐波那契fib[50]，是一个$10^{10}$级别的数，需要long long。如果直接存string显然会溢出。

于是思考下能不能直接用$dp[i][j]$来表示第i个的第$k$个是什么，这样思考的话$k$是个很大的值，也不成。

由此想到直接找数学规律，斐波那契数列。传入$n, k$。讨论第$k$位是属于$f[n - 2]$ 还是$f[n - 1]$。

常用的斐波那契函数忘记直接return结果，导致结果错了，注意注意！！

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 50;
LL f[N];

char fib(int n, int k)
{
    if(n == 0)
        return 'a';
    if(n == 1)
        return 'b';

    if(k <= f[n - 2])
        return fib(n - 2, k);
    else
        return fib(n - 1, k - f[n - 2]);
}

int main()
{
    f[0] = 1, f[1] = 1;
    for(int i = 2; i < N; i ++)
        f[i] = f[i - 1] + f[i - 2];

    int T;
    cin >> T;
    while(T --)
    {
        int n, k;
        cin >> n >> k;
        cout << fib(n, k) << endl;
    }
}