注册登录

Coffee Chicken （斐波那契字符串）

S(1) = {"COFFEE"}S(1)="COFFEE";
S(2) = {"CHICKEN"}S(2)="CHICKEN";
S(n) = S(n-2) :: S(n-1)

1 ≤ n ≤500,1 ≤ k ≤ min{∣S(n)∣,10^12 }

给n和k 求出S(n)从第k位开始往后的10的字符

递归定位，枚举10个位

using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
const int maxn=505;
const ll N=1e12+10;
ll f[maxn];
string s[550];
int num;
void solve(int n,ll k) {
    if(n==1) cout<<s[1][k-1];
    else if(n==2) cout<<s[2][k-1];
    else {
        if(k>f[n-2]) solve(n-1,k-f[n-2]);
        else if(k<=f[n-2]) solve(n-2,k);
    }
}
int main( ) {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t;
    cin>>t;
    f[1]=6; f[2]=7;
    for(int i=3;i<=500;i++) f[i]=min(f[i-1]+f[i-2],N);
    s[1]="COFFEE"; s[2]="CHICKEN";
    while(t--) {
        int n; ll k;
        cin>>n>>k;
//        cout<<f[n]<<endl;
        num=0;
        for(ll i=k;i<min(f[n]+1,k+10);i++) solve(n,i);
        cout<<endl;
    }
    return 0;
}
知识兔
计算机