Problem
codeforces.com/contest/814/problem/C
Reference
Markdown Syntax MaHua
Meaning
给定一串长为 n 的只有小写字母的字符串，q 个询问。 对每一个询问，给出字母 c 和最多的使用次数 m，表示最多将原串中 m 个位置的字符替还为 c。 求替换后的串中，最长的全为 c 的子串的长度。
Analysis
因为是连续的，就考虑将邻近的只有 c 的片段连起来。 预初理出每个字母的片段，然后用尺取枚举将哪些片连起来。 注意一些细节的处理。
Code
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N =
1500;
struct seq
{
int st, ed;
seq() {}
seq(
int a,
int b): st(a), ed(b) {}
int len()
{
return ed - st;
}
};
char s[N+
2];
vector<seq> g[
26];
int solve(
int x,
int m,
int n)
{
int res = min(m, n), tmp =
0;
for(
int l=
0, r=
0, add, e=g[x].size(); l<e; )
{
if(l == r)
{
if(++r >= e)
{
res = max(res,
g[x][l].len() + min(m, g[x][l].st + n-g[x][l].ed));
break;
}
if(m >= g[x][r].st - g[x][l].ed)
{
m -= g[x][r].st - g[x][l].ed;
tmp = g[x][r].st - g[x][l].ed + g[x][l].len() + g[x][r].len();
++r;
}
else
{
res = max(res,
g[x][l].len() + min(m, g[x][l].st + n-g[x][l].ed));
++l;
}
continue;
}
while(r < e && m >= g[x][r].st - g[x][r-
1].ed)
{
m -= g[x][r].st - g[x][r-
1].ed;
tmp += g[x][r].st - g[x][r-
1].ed + g[x][r].len();
++r;
}
if(m >
0)
add = min(m, g[x][l].st + n-g[x][r-
1].ed);
else
add =
0;
res = max(res, tmp + add);
if(l +
1 < e)
{
if(l +
1 != r)
{
m += g[x][l+
1].st - g[x][l].ed;
tmp -= g[x][l+
1].st - g[x][l].ed + g[x][l].len();
}
++l;
}
else
break;
}
return res;
}
int main()
{
int n, q;
scanf(
"%d %s %d", &n, s, &q);
for(
int i=
0, j; i<n; i=j)
{
for(j=i+
1; j<n && s[j]==s[i]; )
++j;
g[s[i]-
'a'].push_back(seq(i, j));
}
for(
int m; q--; )
{
char c;
scanf(
"%d %c", &m, &c);
printf(
"%d\n", solve(c-
'a', m, n));
}
return 0;
}
