题解：P14082 「CZOI-R7」割 II

zcEscortJ · 2026-07-24 11:40:58 · 题解

推式子题。

对于分段操作，我们可以把分 k 段看作是将 k-1 个板子插在了字符与字符之间，总共 n-1 个空位中。相邻两个板子之间是一段，最左边和最右边的板子到字符串两端是一段。

现在我们往里面插板子。考虑什么样的插法可以改变贡献。首先，一块板子插在两个不同的字符之间，那么总贡献不变。这是因为即使左右两段处于同一区间内，他们各自也算一个不同的连续字段。此时将两段隔开不会影响彼此的记数。

相反，如果板子插在了两个相同字符中，就多出了 1 的贡献。证明是类似的。在一段中，这两个字符所在的极大连续子段只会记一次贡献，而分成两段后，左右都会分别记一次贡献。

这有什么用呢？

注意到改变一块板子的位置最多只会变化 1 的贡献，这就意味着我们可以通过改变块板子的位置来凑出最大值到最小值之间所有的贡献值。因此答案就是最大值减最小值 +1。

要使总贡献最小，就要尽可能地把板子往不同的字符中插。而要使贡献最大，就要把板子尽可能的往相同的字符中插。通过遍历求出上述两种空隙，设第一种空数量为 A，第二种为 B，原来有 num 个极长连续子段（不操作时的答案），那么就有最大值为 num+\min(k,B)，后面的 \min(B,k) 代表最多能将多少板子插进第一种空。最小值为 num+\max(k-A,0)，后面的 \max(k-A,0) 表示至少要将多少板子被迫插进两边字符不同的空。最后，我们得到答案：

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n , k ;
    cin >> n >> k ;
    string s ;
    cin >> s ;
    if( k >= n ) 
    {
        cout << 0 ;
        exit(0) ;
    }
    s = " " + s ;
    int sum = 0 , c = 26 , B = 0 , A = 0 ;
    for( int i = 1 ; i <= n ; i ++ )
    {
        if( c != s[i]-'a' )
        {
            c = s[i]-'a' ;
            if( i > 1 ) A ++ ;
        }
        else B ++ ;
    }
    cout << min(B,k) - max(k-A,0) + 1 ;
    return 0;
}