题解：AT_abc300_f [ABC300F] More Holidays

模拟赛的最后一题，赛时没做出来，听了讲解后会了来写个题解。

### 思路

看到 $M$ 和 $K$ 的范围，就知道不能遍历这两个。

考虑找到一个区间，使得里面所有的 `x` 都可以被变成 `o`。左边界从 $1$ 枚举到 $N$，再通过改变右边界来找到满足条件的区间。注意到肯定不能对处理后的字符串进行操作，于是不难想到将原字符串中 `x` 的数量映射到处理后的字符串，再通过本次需要改变的 `x` 的数量调整右边界。

是不是有点熟悉？对于右边界的处理其实就是一个二分答案，接着不难想到本次需要改变的 `x` 的数量可以用前缀和来计算。首先设本次枚举的左端点为 $l$，右端点为 $mid$，前缀和数组为 $S$，则从头到 $r$ 一共有 $S_N\times\lfloor\frac{mid}{N}\rfloor+S_{mid\mod N}$ 个 `x` 需要修改。要求从 $l$ 到 $mid$ 要修改的 `x` 的个数直接用上面那个数减去 $S_{l-1}$ 即可。

时间复杂度 $\mathcal{O}(n\log n)$，可以通过。

:::warning[注意]
十年 OI 一场空，不开 **long long** 见祖宗。
:::

### solution

```cpp line-numbers
#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(int i = a;i<=b;i++)
using namespace std;
inline __int128 read(){__int128 x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-'){f=-1;}c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return f*x;}
inline void write(__int128 x){if(x<0){putchar('-');x=-x;}if(x>9)write(x/10);putchar(x%10+'0');}
int sum[300005];//前缀和数组
ll res = -1,n,m,k;
bool check(ll mid,ll l){
	ll c = 1ll*sum[n]*(mid/n)+sum[mid%n]-sum[l-1];
	return c<=k;
}
int main(){
	n = read();
	m = read();
	k = read();
	string s;
	cin>>s;
	s = " "+s;//加一个空格方便处理
	For(i,1,n){
		if(s[i]=='x') sum[i] = sum[i-1]+1;
		else sum[i] = sum[i-1];
	}
	For(i,1,n){
		ll l = i+1,r = n*m,ans;
		while(l<=r){
			ll mid = (l+r)/2;
			if(check(mid,1ll*i)){
				l = mid+1;
				ans = mid;
			}
			else{
				r = mid-1;
			}
		}
		res = max(res,ans-i+1);
	}
	write(res);
	return 0;
}
```

正在渲染内容...