[牛客暑期多校第十场][递归]B-Coffee Chicken

https://ac.nowcoder.com/acm/contest/890/B

给你两个字符串
s[1]=”COFFEE” s[2]=”CHICKEN”
s[i]=s[i-2]+s[i-1]
给你 i 和 k
输出i的第k之后的10个字符 不足10个有几个输出几个
递归 k最大为1e12
s[i]=s[i-2]+s[i-1] 可以判断第k个字符要么属于前半段 要么属于后半段
我们写一个函数 取的是单个字符

#include
#include
#include
#include
#include
#include
#include
#include
#include

const string s[2] = { “COFFEE”,”CHICKEN” };
ll f[505];

char getans(int n, ll k) {
for (; n > 2;) {
if (f[n - 2] >= k) n -= 2;//k在n-2部分 前半部分 更新n
else {
k -= f[n - 2];//在后半段 减去前半段的长度
n–;//更新n
}
}
return s[n - 1][k - 1];
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
f[1] = 6;
f[2] = 7;
for (int i = 1; i <= 500; i++) {
if (i > 2) {
f[i] = min((ll)(1e12 + 20), f[i - 1] + f[i - 2]);
}
}
int t;
cin >> t;
while (t–) {
int n;
ll k;
cin >> n >> k;
for (int i = 1; i <= 10; i++) {
if (k + i - 1 <= f[n]) {//在字符串范围内
putchar(getans(n, k + i - 1));
}
}
puts(“”);
}
return 0;
}