C. K-Complete Word(小小的并查集啦~)

永久打开的传送门

\(\color{Pink}{-------------分割-------------}\)

\(n最大有2e5,那么暴力一定不行，找规律\)

\(我们发现第i位的字符一定和第i+k位相等(周期)\)

\(第i位的字符一定和第n-i+1位字符相等(回文)\)

\(那么每次把i,i+k,n-i+1合并到一个集合(并查集)\)

\(最后一定是分成了若干个集合，集合中的元素要相等\)

\(那我们再统计每个集合的元素个数和集合里出现字符最多的字母\)

\(于是我们规定这个集合都变成出现次数最多的那个字母,就好啦\)~~~

\(最后是233ms,还不算太慢吧......\)

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+9;
int pre[maxn],n,k,t,vis[maxn][26];
char s[maxn];
int find(int x){
    return x==pre[x]?pre[x]:pre[x]=find(pre[x]);
}
void join(int q,int w){
    pre[find(q)]=find(w);
}
inline int max(int a,int b){return a>b?a:b;}
int main()
{
    cin>>t;
    while(t--)
    {
        int ans=0;  
        cin>>n>>k>>(s+1);
        for(int i=0;i<=n;i++)    pre[i]=i;   
        for(int i=1;i<=n/2;i++)
        {
            if(i+k<=n)   join(i,i+k);
            join(i,n-i+1);
        }
        for(int i=1;i<=n;i++)
        {
            int num=s[i]-'a';
            vis[find(i)][num]++;
        }
        for(int i=1;i<=n;i++)
        {
            if(pre[i]!=i)   continue;
            int he=0,maxx=0;
            for(int j=0;j<=25;j++)
            {
                he+=vis[i][j];
                maxx=max(maxx,vis[i][j]);
                vis[i][j]=0;//清空为下次做准备 
            }
            ans+=(he-maxx);
        }
        cout<<ans<<endl;
    }
}