2019牛客多校10 B题_算法日常[12/100]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

## python3

lf = [0, 6, 7]
## 一千多项的时候远远超过了10^12+7的
for _ in range(1000) :
    lf.append(lf[-2] + lf[-1])
    ## if _ == 999:
    ##     print(If[-1])

def f(x, s) :
    if x == 1 :
        return "COFFEE"[s]
    if x == 2 :
        return "CHICKEN"[s]
    if s >= lf[x-2] :
        return f(x - 1, s - lf[x - 2])
    else :
        return f(x - 2, s)

for _ in range(eval(input())) :
    n, s = map(int, input().split())
    s -= 1
    ## 从s到min(s+10,lf[n]), 用中括号括起来生成列表
    r = [f(n, t) for t in range(s, min(s + 10, lf[n]))]
    print(''.join(r))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
ll len[505];
string ans;
int T,n;ll k;

char f(int x,ll k){
    if(x==1) return "COFFEE"[k];
    if(x==2) return "CHICKEN"[k];
    if(k>=len[x-2]) return f(x-1,k-len[x-2]);
    else return f(x-2,k);
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    len[1] = 6,len[2] = 7;
    ll mx = 1e13;
    /*这里最好不要break,否则会造成数组的部分是0值，除非先赋值为mx
    (当然也可以使用C++AC代码二的特殊提前处理去使用break)
    但是可以通过min控制数值大小，以免引发数据溢出错误
    可以使用min的原因是，k不会到很大的数据范围
    然后递归的时候是一样的,最终也是递归到x==1,x==2
    是按照题中斐波那契递归回去的，所以不会出错*/
    for(int i=3;i<=500;i++){
        len[i] = min(len[i-2]+len[i-1],mx);
    }
    for(cin>>T;T--;){
        cin>>n>>k;
        k-=1;
        ans.clear();
        ll tn = min(k+10,len[n]);
        for(ll i=k;i<tn;i++){
            ans += f(n,i);
        }
        cout<<ans<<endl;
    }

    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int maxn = 100000 + 5;

ll len[505];
string str[3];

string dfs(int x, ll a, ll b) {
    /*substr的第二个参数是长度*/
    if(x <= 2) return str[x].substr(a-1, b);
    if(a+b-1 <= len[x-2]) return dfs(x-2, a, b);
    if(a > len[x-2]) return dfs(x-1, a-len[x-2], b);
    /*分段后..x-1可以直接从1开始了*/
    return dfs(x-2, a, len[x-2]-a+1) + dfs(x-1, 1, b-(len[x-2]-a+1));
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    str[1] = "COFFEE"; str[2] = "CHICKEN";
    len[1] = 6, len[2] = 7;
    ll mx = 1e17;
    for(int i = 3; i <= 500; i++) {
        /*前缀和*/
        len[i] = len[i-1] + len[i-2];
        /* i=80就会跳出*/
        if(len[i] > mx) {/*cout<<i<<endl;*/break;}
    }
    int T; cin >> T;
    while(T--) {
        int n; ll k;
        cin >> n >> k;
        int x;
        /*提前给x降低大小，所以就可以前面使用break，并且减少递归的次数*/
        for(x = 1; x <= n; x++) {
            if(len[x] >= k+10) break;
        }
        if(x == n+1) cout << dfs(x-1, k, min(10ll, len[x]-k+1)) << endl;
        else {
            if((n-x)%2) x++;
            cout << dfs(x, k, min(10ll, len[x]-k+1)) << endl;
        }
    }

    return 0;
}