Znzryb's Blog
0%

第七届CRH - i人和e人

Posted on Edited on

AC代码

赛时AC，主要就是记录一下

主要思路就是通过一次遍历得到以1位置为准的到达所需魔法数cntK[N]以及魔法数最远到达点ktomax[N]

由于都是相对于一位置的，魔法数可以互相加减。

从i点能够到达的最远点即是ktomax[k+cntK[i]]（前提是s[i]==‘想统计的字符’），那么长度就是ktomax[k+cntK[i]]-i+1，这就是lans（local ans）的由来

核心代码就是这一段，其他的代码就是重复，初始化，以及防止加出去=0了

1
2
3
4
5
6
7
if(s[i]=='i') {
    ll lans=ktomax[k+cntK[i]]-i+1;
    ans=max(ans,lans);
}else {
    ll lans=ktomax[k+cntK[i]-1]-i+1;
    ans=max(ans,lans);
}
1
2
3
for(int i=chK+1;i<=2*k;++i) {   // 你说你有更多的k？没问题，但是到达距离是一样的
        ktomax[i]=ktomax[chK];
 }

cntI是没有用的变量，不过因为

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
#include <cstdio>
#include <cctype>

using namespace std;
typedef long long ll;
const ll N=2e5+7;
string s;
ll k,ans;
ll ktomax[N],cntK[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>s;
    cin>>k;
    ll chK=0,cntI=0;
    for(int i=0;i<s.size();++i) {   //判断i序列
        if(s[i]=='i') {
            ++cntI;
        }else {
           chK+=1;
            ++cntI;
        }
        ktomax[chK]=i,cntK[i]=chK;
    }
    for(int i=chK+1;i<=2*k;++i) {   // 你说你有更多的k？没问题，但是到达距离是一样的
        ktomax[i]=ktomax[chK];
    }
    for(int i=0;i<s.size();++i) {
        if(s[i]=='i') {
            ll lans=ktomax[k+cntK[i]]-i+1;
            ans=max(ans,lans);
        }else {
            ll lans=ktomax[k+cntK[i]-1]-i+1;
            ans=max(ans,lans);
        }
    }

    memset(ktomax,0,sizeof(ktomax));    // 重置
    memset(cntK,0,sizeof(cntK));
    chK=0,cntI=0;

    for(int i=0;i<s.size();++i) {   //判断e序列
        if(s[i]=='e') {
            ++cntI;
        }else {
            chK+=1;
            ++cntI;
        }
        ktomax[chK]=i,cntK[i]=chK;
    }
    for(int i=chK+1;i<=2*k;++i) {   // 你说你需要更多的k？没问题，但是到达距离是一样的
        ktomax[i]=ktomax[chK];
    }
    for(int i=0;i<s.size();++i) {
        if(s[i]=='e') {
            ll lans=ktomax[k+cntK[i]]-i+1;
            ans=max(ans,lans);
        }else {
            ll lans=ktomax[k+cntK[i]-1]-i+1;
            ans=max(ans,lans);
        }
    }
    cout<<ans<<endl;
    return 0;
}
// AC https://oj.saikr.com/problem/detail/1851

心路历程（WA，TLE，MLE……）

之前的做法只想了从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
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstring>

using namespace std;
typedef long long ll;
string s;
ll k;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>s;
    cin>>k;
    ll ans=0;
    ll chK=k,cntI=0,cntE=0;
    for(int i=0;i<s.size();++i) {   //判断i序列
        if(s[i]=='i') {
            ++cntI;
            ans=max(ans,cntI);
        }else {
            if(chK<=0) {
                ans=max(ans,cntI);
                cntI=0,chK=k;
            }else {
                chK-=1;
                ++cntI;
                ans=max(ans,cntI);
            }
        }
    }
    chK=k,cntI=0,cntE=0;
    for(int i=0;i<s.size();++i) {   //判断i序列
        if(s[i]=='e') {
            ++cntE;
            ans=max(ans,cntE);
        }else {
            if(chK<=0) {
                ans=max(ans,cntE);
                cntE=0,chK=k;
            }else {
                chK-=1;
                ++cntE;
                ans=max(ans,cntE);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}