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

发布于 2019-08-21  1564 次阅读


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<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<cstring>
#include<unordered_map>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
typedef long double ld;
const ll maxn = 1e12;

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;
}

愿风指引你的道路,愿你的刀刃永远锋利。