2019牛客多校第十场 B Coffee Chicken 思维+斐波那契数列
链接：https://ac.nowcoder.com/acm/contest/890/B
来源：牛客网
Dr. JYY has just created the Coffee Chicken strings, denoted as S(n). They are quite similar to the Fibonacci soup --- today's soup is made by mingling yesterday's soup and the day before yesterday's soup:
- S(1)="COFFEE"S(1) = \texttt{"COFFEE"}S(1)="COFFEE";
- S(2)="CHICKEN"S(2) = \texttt{"CHICKEN"}S(2)="CHICKEN";
- S(n) = S(n-2) :: S(n-1), where :: denotes string concatenation.
The length of S(n) quickly gets out of control as n increases, and there would be no enough memory in JYY's game console to store the entire string. He wants you to find 10 contiguous characters in S(n), starting from the kth character.
输入描述:
The first line of input is a single integer T (1≤T≤1000)(1 \leq T \leq 1000)(1≤T≤1000), denoting the number of test cases. Each of the following T lines is a test case, which contains two integers n, k (1≤n≤500,1≤k≤min{∣S(n)∣,1012})(1 \leq n \leq 500, 1 \leq k \leq \min\{|S(n)|, 10^{12}\})(1≤n≤500,1≤k≤min{∣S(n)∣,1012}). |S| denotes the length of string S. 输出描述:
For each test case, print the answer in one line. If there are no enough characters from the kth character, output all characters until the end of the string. 示例1
输入
2
3 4
2 7 输出
FEECHICKEN
N 题目大意:给你一个字符串,这个字符串的组成是由斐波那契数列的规则组成,即目前的字符串为 前两个字符串组合而成 ,题目中给出为 COFFEE 和 CHICKEN 分别为 S1与S2,让你输出 第 n个字符串的第k个字符之后的十个字符
题目思路:
第一步:既然与斐波那契数列的规则一样,那肯定也就与斐波那契数列有关,首先打表发现n>58 这个数列就会超过1e12,而k最多到1e12,n=61第1e12个位置是由(n=59)+(n=60)拼合起来,因为n=59时长度大于1e12,所以61的1e12就为59的1e12,所以我们判断一下,这个数如果为奇数&&大于60,处理的前缀其实与59一样,n如果为偶数前缀与 58一样.所以我们根据这样把n的范围控制到了60以内.
第二步:既然这是斐波那契数列,所以满足斐波那契数列的性质,我们看一下当前的位置 pos,如果当前pos>a[n-2]长度,那么就相当于求 a[n-1]的第k-a[n-2]个数,如果pos<=a[n-2]那就等于求a[n-2]的第pos个数(不懂就自己写几个看一下就好啦)
所以根据这样递推,最终的状态不是1就是2,所以输出此时是第几个字符即可:
具体代码:
#include <bits/stdc++.h>
#define E 2.718
using namespace std;
typedef long long ll;
const ll INF=0x7f7f7f7f;
const int maxn=1e6+8;
const double eps=1e-10;
const ll mod=1000000007;
ll n,m,b;
ll x,y;
ll a[505];
char str[2][15]={".COFFEE",".CHICKEN"};
void restart()
{
a[1]=6;a[2]=7;
for(int i=3;i<=60;i++)
a[i]=a[i-1]+a[i-2];
}
int main()
{
restart();
int T;scanf("%d",&T);
while(T--)
{
scanf("%lld%lld",&n,&m);
ll temp=m;
if(n>=60)
{
if(n%2) n=59;
else n=58;
}
for(ll i=m;i<=a[n]&&i<m+10;i++)
{
x=n,y=i;
while(x!=1&&x!=2)
{
if(y>a[x-2])
{
y-=a[x-2];
x--;
}
else
x-=2;
}
if(x==1) printf("%c",str[0][y]);
else if(x==2) printf("%c",str[1][y]);
}
printf("\n");
}
return 0;
}
总结:这个题能卡三个小时.....对自己能力不行更加肯定了,但不管怎样,既然选择ACM就得走到底,加油,继续刷题!
