Codeforces Round #630 (Div. 2) – K – Complete Word

菜菜的我自上一次WA了第一题直接生气不做了掉绿了之后在艰难的涨分,现在仍然只有青上面一丢丢呜呜呜我好菜。这一场也只做出两题。最近没有像寒假时候那样每天都花大量时间刷题,退步明显TAT。

不过我要吐槽这一次出题人的英语,这个A题我看了一个小时多才读懂到底是什么意思……心态崩崩崩。

C. K-Complete Word

  • time limit per test: 2 seconds
  • memory limit per test: 512 megabytes
    Word $s$ of length $n$ is called $k$-complete if
  • $s$ is a palindrome, i.e. $s_i=s_{n+1−i}$ for all $1≤i≤n$;
  • $s$ has a period of $k$, i.e. $s_i=s_{k+i}$ for all $1≤i≤n−k$.

For example, abaaba is a $3$-complete word, while abccba is not.

Bob is given a word $s$ of length $n$ consisting of only lowercase Latin letters and an integer $k$, such that $n$ is divisible by $k$. He wants to convert $s$ to any $k$-complete word.

To do this Bob can choose some $i$ $(1≤i≤n)$ and replace the letter at position $i$ with some other lowercase Latin letter.

So now Bob wants to know the minimum number of letters he has to replace to convert $s$ to any $k$-complete word.

Note that Bob can do zero changes if the word $s$ is already $k$-complete.

You are required to answer $t$ test cases independently.

Input

The first line contains a single integer $t$ $(1≤t≤10^5)$ — the number of test cases.

The first line of each test case contains two integers $n$ and $k$ $(1≤k<n≤2⋅10^5)$, $n$ is divisible by $k$).

The second line of each test case contains a word $s$ of length $n$.

It is guaranteed that word $s$ only contains lowercase Latin letters. And it is guaranteed that the sum of $n$ over all test cases will not exceed $2⋅10^5$.

Output

For each test case, output one integer, representing the minimum number of characters he has to replace to convert $s$ to any $k$-complete word.

Example

input

4
6 2
abaaba
6 3
abaaba
36 9
hippopotomonstrosesquippedaliophobia
21 7
wudixiaoxingxingheclp

output

2
0
23
16

Note

In the first test case, one optimal solution is aaaaaa .

In the second test case, the given word itself is $k$-complete.

题意

给定一个长度为 n 的字符串,要求修改最少的位数,使其为回文串且周期为 k

思路

【转化问题】
我好蠢暴力题都不会做了……其实我觉得我就是没有能够想到,整个字符串是回文串且周期为 k 可以转化为 n / k 个周期每个周期内都为回文串
【贪心】
转化完之后很愚蠢的暴力就好啦,也称得上是贪心吧。

cnt[i][j] 表示每个周期的第 i 位与第 k-i-1 位字母为 j + 'a' 的数量之和,其中 $i \in [0,(k-1)/2], j \in [0,26)$。遍历一遍就可以统计了,统计的时候注意判断回文串中心是一个还是两个字母,如果是一个的话不要重复统计。

然后就是对于 cnt 第一维进行遍历,找到出现数量最大的字母并记录下来,每个周期的该位置及其对称位置都应该是这个字母,如果不是那么算入答案内。

代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;
char str[MAXN];
int cnt[MAXN][26];

int main() {
    // freopen("in.txt", "r", stdin);
    int T; scanf("%d", &T);
    for(int t=1; t<=T; t++) {
        int n, k; scanf("%d %d %s", &n, &k, str);

        // memset(cnt, 0, sizeof(cnt));
        for(int i=0; i<k; i++) for(int j=0; j<26; j++) cnt[i][j] = 0;
        for(int i=0; i<n/k; i++) {
            for(int j=0; j<=(k-1)/2; j++) {
                cnt[j][str[i*k+j]-'a']++;
                if((k & 1) && j == (k - 1) / 2) continue;
                cnt[j][str[i*k+k-j-1]-'a']++;
            }
        }
        
        int ans = 0;
        for(int i=0; i<=(k-1)/2; i++) {
            int mx = 0, ch = -1;
            for(int j=0; j<26; j++) {
                if(mx < cnt[i][j]) {
                    mx = cnt[i][j];
                    ch = j;
                }
            }
            
            int now = n / k - cnt[i][ch] + n / k - cnt[k-i-1][ch];
            if((k & 1) && i == (k - 1) / 2) now /= 2;
            ans += now;
        }
        printf("%d\n", ans);
    }
    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇