题解：P15029 [UOI 2021 II Stage] 酷子串

· · 题解

我们一定要学会看算法标签。

题意简述

给定一个长度为 n 的字符串 s，更改其中不超过 k 个字符，构造一个长度尽可能长的子串，满足所有在偶数位置和奇数位置上的字符分别相同。

思路分析

对于一个长度为 len 的子串，记奇数位置上出现次数最多的字符次数为 cnt1_a，偶数位置上出现次数最多的字符次数为 cnt2_a。

那么最少需要修改的次数为 len - (cnt1_a + cnt2_a)。如果最少修改次数 \le k，那么这个子串就是可行的。

实现方式

注意到算法标签写了双指针。

我们维护 [l, r]，表示当前考虑的子串。

使用两个计数器数组分别记录区间中奇数位置和偶数位置的字符出现次数，不断向右移动右指针 r，将新字符加入区间。

对于每个区间，计算需要的最小修改次数，如果最小修改次数 >k，则向右移动左指针 l，直到满足条件或区间为空。

移动左指针时，需要更新计数器，并且要注意区间内奇偶位置会发生翻转。

每次找到一个可行区间后，更新最大长度。

代码

#include<bits/stdc++.h>
using namespace std;
char s[5002026];
int s1[5002026];
int cnt1[26],cnt2[26];
int l,ans=-1;
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    scanf("%s",s);
    //转换为数字方便计算
    for(int i=0;i<n;++i){
        s1[i]=s[i]-'a';
    }
    for (int r=0;r<n;++r){
        //统计次数
        if((r-l)%2==0){
            cnt1[s1[r]]++;
        }else{
            cnt2[s1[r]]++;
        }
        //收缩左边界
        while(l<=r){
            int max1=0,max2=0;
            for (int i=0;i<26;++i){
                if(cnt1[i]>max1) max1=cnt1[i];
                if(cnt2[i]>max2) max2=cnt2[i];
            }
            int len=r-l+1;
            if(max1+max2>=len-k){
                break;
            }
            cnt1[s1[l]]--;
            swap(cnt1,cnt2);//交换奇偶位置
            l++;
        }
        ans=max(ans,r-l+1);
    }
    printf("%d",ans);//愉快输出
    return 0;
}

完结撒花QwQ。