题目描述

难度分:$1846$

输入$n(1 \leq n \leq 3 \times 10^5)$，$m(1 \leq m \leq 10^9)$，$k$和长为$n$的字符串$s$，只包含小写字母o和x。
保证至少有一个x，保证$1 \leq k \leq s.count(x) \times m$。

将$s$重复$m$次，得到字符串$t$。例如abc重复$3$次得到abcabcabc。
请你修改$t$中的恰好$k$个x。修改后，输出$t$中最长连续o的长度。

输入样例$1$

10 1 2
ooxxooooox

输出样例$1$

9

输入样例$2$

5 3 4
oxxox

输出样例$2$

8

输入样例$3$

30 1000000000 9982443530
oxoxooxoxoxooxoxooxxxoxxxooxox

输出样例$3$

19964887064

算法

滑动窗口

这个题纯思维难度，想通了写起来就非常简单，不然就坐牢。让$s$从$0$索引开始，先遍历一遍$s$将所有x的位置都存入$pos$数组，其长度为$cntX$。

可以推出一个公式，如果要将前$k$个x改成o，能够得到的最长连续o的长度为

$[\frac{k}{cntX}] \times n+pos[k \% cntX]$

其中$[.]$是对$.$进行下取整操作，第一项的$[\frac{k}{cntX}]$表示能将多少段完整的$s$中的所有x变成o，将它们都变成o之后就能有长度为$[\frac{k}{cntX}] \times n$的o。最后还剩下$k \%cntX$个x要改成o，它可以产生长度为$pos[k \% cntX]$的o，即索引$pos[k \% cntX]$（不包括）前面的所有位置都可以是o。

接下来滑动窗口，让$k$不断递增代入上面的公式，每次只需要减去窗口左端点x的位置$p$，就能够得到$p+1$到当前x位置的长度，再减去当前x（减$1$）就得到了下一个包含$k$个x的最大窗口长度，公式为：

$[\frac{k}{cntX}] \times n+pos[k \% cntX]-pos[i]-1$，$pos[i]$是上一个窗口左端点x的位置。

复杂度分析

时间复杂度

相当于遍历了两遍$s$串规模的数组，时间复杂度为$O(n)$。

空间复杂度

开辟了一个数组存储$s$中x的所有索引，额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long LL;

const int N = 300010;
int n, m;
LL k;
char s[N];

int main() {
    scanf("%d%d%lld", &n, &m, &k);
    scanf("%s", s);
    vector<int> pos;
    for(int i = 0; i < n; i++) {
        if(s[i] == 'x') pos.push_back(i);
    }
    int cntX = pos.size();
    LL ans = min((LL)n*m, k/cntX*n + pos[k % cntX]);
    for(int i = 0; i < cntX; i++) {
        k++;
        LL res = min((LL)n*m, k/cntX*n + pos[k % cntX]) - pos[i] - 1;
        ans = max(ans, res);
    }
    printf("%lld", ans);
    return 0;
}