ABC300F分类讨论二分容斥尺取周期思维简单动脑筋

二分查找：

#include <stdio.h>
#define N 300050
long long n, m, i, j, k, l, r, x, p, ans, c[N];
char s[N];
int main(){
    scanf("%lld%lld%lld%s", &n, &m, &k, s+1);
    for(i=1; i<=n; i++){
        c[i] = c[i-1] + (s[i] == 'x');
    }
    for(i=0; i<n; i++){//枚举起点
        l = i+1, r = m*n;
        while(l < r){//二分查找结尾
            p = l+r+1 >> 1;
            x = c[n]-c[i]+c[n]*(p/n-1)+c[p%n];//(i, p]的x数量
            if(x <= k) l = p;
            else r = p - 1;
        }
        if(r-i > ans) ans = r-i;
    }
    printf("%lld\n", ans);
    return 0;
}

分类讨论：

#include <bits/stdc++.h>
#define N 300050
using namespace std;
long long n, m, i, j, k, x, y, c, ans, a[N], b[N], v[N];
char s[N];
int main(){
    scanf("%lld%lld%lld%s", &n, &m, &k, s+1);
    for(i=1; i<=n; i++){
        if(s[i] == 'x') b[x++] = i-1;//从左往右消除x个x，长度增加i-1
        v[i] = v[i-1] + (s[i] == 'x');
    }
    a[x] = b[x] = n, x = 0;
    for(i=n; i>=1; i--){
        if(s[i] == 'x') a[x++] = n-i;//从右往左消除x个x，长度增加n-i
    }
    for(i=0, j=1; i<n; i++){
        while(j<=n && v[j]-v[i]<=k) j++;
        ans = max(ans, j-1-i);
    }//在一个周期之内，尺取计算
    if(m > 1){//跨越两个周期
        for(i=0; i<=x&&i<=k; i++){//枚举左边周期消除x数量
            y = k - i, c = 1 + y/x + (y%x>0);
            if(y/x == m) ans = n*m;
            else if(y/x == m-1){//右端无周期
                ans = max(ans, a[i]+y/x*n);
                ans = max(ans, y/x*n+b[i]);
            }//右端周期还可以消除y%x个x
            else ans = max(ans, a[i]+y/x*n+b[y%x]);
        }
    }
    printf("%lld\n", ans);
    return 0;
}