1332C.md

C. K-Complete Word

Link

Solution

画画图可以发现如果要得到满足条件的字符串只需要让长度为k的子串也为回文串就行，于是问题就变成使得长度为k且不重叠的子串为回文串且所有这种回文子串都相同的最小代价。

接下来把待处理字符串想成一个(n/k)*k的二维字符矩阵，于是问题就转化成使得这个二维字符矩阵每一列上的字符都相同且每一列和每k-i-1列字符也相同所要付出的最小代价。

alpha[i][j]表示第i列字符j出现的次数，将alpha[i][0-26]和alpha[k-i-1][0-26]累加得到的是第i列和第k-i-1列所有字符出现的次数，累加的同时选出最大出现次数，累加和减去最大出现次数就是第i列上的最小代价，为了避免讨论奇偶将i从0-k处理后最终结果除以2即可。

Code

int alpha[maxn][26];

int main(int argc, char **argv) {
    int n, k, t;
    string s;
    cin >> t;
    while (t--) {
        cin >> n >> k >> s;
        int ans = 0;
        for (int i = 0; i < k; i++)for (int j = 0; j < 26; j++)alpha[i][j] = 0;
        for (int i = 0; i < n; i++)alpha[i%k][s[i] - 'a']++;
        for (int i = 0; i < k; i++) {
            int cnt = 0, maxv = 0;
            for (int j = 0; j < 26; j++) {
                cnt += alpha[i][j] + alpha[k - i - 1][j];
                maxv = max(maxv, alpha[i][j] + alpha[k - i - 1][j]);
            }
            ans += (cnt - maxv);
        }
        cout << ans / 2 << endl;
    }
    return 0;
}