[dfs] 2019牛客暑期多校训练营（第十场） Coffee Chicken

 1 #include<bits/stdc++.h>
 2 typedef long long ll;
 3 using namespace std;
 4 const ll inf=1e12+10;      ///这是一个坑点，inf要设为1e12+10，因为k最大是1e12，又要输出10位，所以极限要比1e12大10
 5 const int amn=5e2+5;
 6 ll s[amn];
 7 char ans1[]="COFFEE",ans2[]="CHICKEN";
 8 char find(ll n,ll k){
 9     if(n==1)return ans1[k-1];       ///这里k-1是因为ans数组从0开始，而k从1开始
10     if(n==2)return ans2[k-1];
11     if(k>s[n-2])return find(n-1,k-s[n-2]);      ///如果k要往右边搜索，则k要减去前面的s[n-2]才能得到s[n-1]的相对位置，注意这里要加返回才能从最底层一直返回到最顶层，不然就只是在最底层返回到上一层
12     else return find(n-2,k);                    ///如果向左边搜索就直接下传
13 }
14 int main(){
15     int T;
16     ll n,k;
17     s[1]=6,s[2]=7;
18     for(int i=3;i<=500;i++)s[i]=s[i-2]+s[i-1]<=inf?s[i-2]+s[i-1]:inf;   ///预处理s数组，是每种字符串的长度
19     scanf("%d",&T);
20     while(T--){
21         scanf("%lld%lld",&n,&k);
22         for(ll i=k;i<k+10&&i<=s[n];i++)printf("%c",find(n,i));printf("\n"); ///一个个输出，到10个或超过了字符串总长度就停止
23     }
24 }
25 /**
26 s[1]="COFFEE",s[2]="CHICKEN",s[n]由s[n-2]和s[n-1]连接而成，注意s[n-2]在s[n-1]的前面
27 问长度为s[n]的字符串，从第k个字符开始的连续10个字符是多少（如果还未有10个字符但到达字符串末尾时要停止）
28 s[n]=s[n-2]+s[n-1],类似斐波那契数列，现在要看k是在s[n-2]上还是s[n-1]上，所以想到用k在s[n-2]和s[n-1]上搜索，如果k小于等于s[n-2]就向s[n-2]搜索，否则
29 就向s[n-1]搜索，但注意s[n-1]只是长度而不是位置，而k是原s[n]中的总位置，所以向子串搜索时
30 要减去多余的位置才能在子串的长度中搜索所以k-s[n-2]才能得到在s[n-1]中的长度，也就是它的相对位置
31 注意有一个坑点，inf要设为1e12+10，因为k最大是1e12，又要输出10位，所以极限要比1e12大10
32 **/