第七届CRH - i人和e人 · znzryb
## AC代码
赛时AC，主要就是记录一下
主要思路就是通过一次遍历得到以1位置为准的到达所需魔法数`cntK[N]`以及魔法数最远到达点`ktomax[N]`
由于都是相对于一位置的，魔法数可以互相加减。
从i点能够到达的最远点即是`ktomax[k+cntK[i]]`（前提是s[i]=='想统计的字符'），那么长度就是`ktomax[k+cntK[i]]-i+1`，这就是lans（local ans）的由来
核心代码就是这一段，其他的代码就是重复，初始化，以及防止加出去=0了
```cpp
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);
}
```
```cpp
for(int i=chK+1;i<=2*k;++i) { // 你说你有更多的k？没问题，但是到达距离是一样的
ktomax[i]=ktomax[chK];
}
```
cntI是没有用的变量，不过因为
[](https://oj.saikr.com/problem/detail/1851/submit)
```cpp
#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位置出发的情况
```cpp
#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;
}
```