CF1279F New Year and Handle Change 题解

· · 题解

题目传送门

前置知识

WQS 二分

解法

不妨将大/小写分开做，分别计算大/小写字符的最小值后然后取 \min，本质是在取若干个区间令其贡献为 0，转移方程比较板。

因具有凸性，故可以使用 WQS 二分求解。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
const ll inf=1000000000000;
ll a[1000010],b[1000010],f[1000010],g[1000010];
char s[1000010];
bool check(ll n,ll m,ll len,ll mid)
{
    for(ll i=1;i<=n;i++)
    {
        f[i]=f[i-1]+a[i];  g[i]=g[i-1];
        if(i-len>=0)
        {
            if(f[i-len]-mid<f[i])
            {
                f[i]=f[i-len]-mid;  g[i]=g[i-len]+1;
            }
            else  if(f[i-len]-mid==f[i])  g[i]=max(g[i],g[i-len]+1);
        }
    }
    return g[n]>=m;
}
ll solve(ll n,ll m,ll len,ll op)
{
    ll l=-inf,r=inf,ans=0,mid;
    for(ll i=1;i<=n;i++)  a[i]=('a'<=s[i]&&s[i]<='z')^op;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(check(n,m,len,mid)==true)
        {
            ans=mid;
            r=mid-1;
        }
        else  l=mid+1;
    }
    check(n,m,len,ans);
    return f[n]+ans*m;
}
int main()
{
// #define Isaac
#ifdef Isaac
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    ll n,m,len;
    cin>>n>>m>>len;  scanf("%s",s+1);
    cout<<((m*len>=n)?0:min(solve(n,m,len,0),solve(n,m,len,1)))<<endl;
    return 0;
}