Round A 2021 - Kick Start 2021

K-Goodness String

Problem

Charles defines the goodness score of a string as the number of indices \(i\) such that \(S_i\neq S_{N-i+1}\) where \(1\leq i \leq N/2\) (\(1\)-indexed).For example,the string CABABC has a goodness score of \(2\) since \(S_2\neq S_5\) and \(S_3\neq S_4\).

Charles gave Ada a string \(S\) of length \(N\), consisting of uppercase letters and asked her to convert it into a string with a goodness score of \(K\). In one operation, Ada can change any character in the string to any uppercase letter. Could you help Ada find the minimum number of operations required to transform the given string into a string with goodness score equal to \(K\)?

Input

The first line of the input gives the number of test cases, \(T\). \(T\) test cases follow.

The first line of each test case contains two integers \(N\) and \(K\). The second line of each test case contains a string \(S\) of length \(N\), consisting of uppercase letters.

Output

For each test case, output one line containing Case #\(x\): \(y\), where \(x\) is the test case number (starting from \(1\)) and \(y\) is the minimum number of operations required to transform the given string \(S\) into a string with goodness score equal to \(K\).

Limits

Memory limit: 1 GB.
\(1\leq T \leq100.\)
\(0\leq K\leq N/2.\)

Test Set 1

Time limit: 20 seconds.
\(1\leq N\leq 100.\)

Test Set 2

Time limit: 40 seconds.
\(1\leq N\leq 2×10^5\) for at most \(10\)? test cases.
For the remaining cases, \(1\leq N\leq 100.\)

Sample Input :

2
5 1
ABCAA
4 2
ABAA

Sample Output:

Case #1: 0
Case #2: 1

In Sample Case #1, the given string already has a goodness score of \(1\). Therefore the minimum number of operations required is \(0\).

In Sample Case #2, one option is to change the character at index \(1\) to B in order to have a goodness score of \(2\). Therefore, the minimum number of operations required is \(1\).

题目解读：

? 给你若干字符串，定义一个“goodness”值，即字符串中对称不相等的字符数。让你求出需要几步才能使其变为要求“goodness”值的字符串。每一步只能是“goodness”改变1.

AC代码

#include <iostream>
#include <cmath>

using namespace std;
char s[20001];

int solve(int len,char s[],int k) {
    int x = 0,ans = 0;
    for (int i=0;i<len/2;i++)
        if (s[i]!=s[len-i-1]) x++; //这里因为字符串从s[0]开始，故s[i]对应s[len-i-1]。
	return abs(x-k);    
}

int main() {
    int n,len,k;
    cin >> n;
    for (int i=1;i<=n;i++) {
        cin >> len >> k;
        cin >> s;
        cout << "Case #" << i << ": " << solve(len,s,k) << endl;
    }
    return 0;
}

KicK Start 2021 Round A 1