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

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

每天一句叨叨

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