题面：https://codeforces.com/contest/814/problem/C
题意
给定一个长为$n$字符串，给定$q$次query
每次query允许你修改最多$m$个字符，问最长连续的$c$长度是多少
解法
盯着题目看了几十分钟
感觉好像不难
因为一定是要连续的一段 然后想到可能要用滑动窗口
然后调了很长时间，每次都是想改完完整一段
结果WA到自闭
Actually, 滑动窗口是对的，但是没我写的这么复杂
只要从前往后, 左界向前就行了。
然后考虑到query的次数是有限的，如果被算出来过就记录 下次不用再算了
尺取法：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
using namespace std;
const int maxn = 2e3 + 10;
int res[maxn][30];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
// freopen("C:\\Users\\cqj86\\Desktop\\in.txt", "r", stdin);
int n, q;
string s;
cin >> n >> s >> q;
while(q--)
{
int m, fixedm;
string t;
cin >> m >> t;
fixedm = m;
char c = t[0];
if(res[m][c - 'a'])
{
cout << res[m][c - 'a'] << endl;
continue;
}
int l = 0, ans = 0, len = 0;
for(int r = 0; r < n; r++){
if(s[r] != c)
len++;
while(len > m){
if(s[l] != c)
len--;
l++;
}
ans = max(ans, r - l + 1);
}
res[fixedm][c - 'a'] = ans;
cout << ans << endl;
}
return 0;
}
当然也可以用dp来做
其实没想象的那么复杂
令$dp[i][j]$表示能修改$i$个字符最长$j$字符的
然后其实可以从前往后扫一遍，遍历所有的字母所有的$(i, j)$看需要修改多少个字符
每次循环后再更新
因为可能没有被用够那么多的修改，但是显然修改不超过$i - 1$个字符能到达的修改不超过$i$的字符数也能做到。
时间复杂度就是$O(n^2 * 26)$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
using namespace std;
const int maxn = 2e3 + 10;
int res[maxn][30];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
// freopen("C:\\Users\\cqj86\\Desktop\\in.txt", "r", stdin);
int n, q;
string s;
cin >> n >> s >> q;
for(int ch = 0; ch < 26; ch++)
{
for(int i = 0; i < n; i++)
{
int rep = 0;
for(int j = i; j < n; j++)
{
if(s[j] != ch + 'a')
rep++;
res[rep][ch] = max(res[rep][ch], j - i + 1);
}
}
for(int i = 1; i <= n; i++)
res[i][ch] = max(res[i][ch], res[i - 1][ch]);
}
while(q--)
{
int m;
string t;
cin >> m >> t;
m = min(m, n);
char c = t[0];
cout << res[m][c - 'a'] << endl;
}
return 0;
}