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

发表于 更新于 分类于 阅读次数：
2019牛客多校10 B题,斐波那契数列递归构造字符串的思维题 C++由于容易数据溢出，所以必须加限制，否则会造成数据溢出的错误，昨晚WA了两个小时的血的教训 不用去刻意讨好谁，因为只有做自己，才配得上最棒的人生

2019牛客多校10 B题

题目

2019牛客多校10 B题
B_1

B_2

题解思路

B_A

(详见代码注释)

C++由于容易数据溢出，所以必须加限制，否则会造成数据溢出的错误，昨晚WA了两个小时的血的教训

k不会到很大的数据范围(限制在了k<10^12)

然后递归的时候是一样的,最终也是递归到x==1,x==2

是按照题中斐波那契递归回去的，所以不会出错

AC代码

写了python版之后去写C++版本的，结果一直WA了整整2个多小时，眼睛痛，所以决定明天早起再看看哪里出错了并给出C++版的AC代码(第二天已经更新)

Python3版

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
# 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))

C++AC代码1_与题解思路相同的

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

C++AC代码2

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

每天一句叨叨

不用去刻意讨好谁，因为只有做自己，才配得上最棒的人生