题目描述
Charles 将一个字符串的优良分数定义为,在 1≤i≤N/2 的范围内,满足 Si≠SN−i+1 的 i 的数量(索引从 1 开始)。
例如,字符串 CABABC 的优良分数为 2,因为 S2≠S5 并且 S3≠S4。
Charles 给了 Ada 一个长度为 N 的由大写字母构成的字符串 S,并让她将其转换为一个优良分数为 K 的字符串。
每次操作,Ada 都可以将字符串中的任意一个字符转换为任意一个大写字母。
请你帮助 Ada 确定,将给定字符串 S 转换为优良分数为 K 的字符串,所需要的最少操作次数。
输入格式
第一行包含整数 T,表示共有 T 组测试数据。
每组数据第一行包含两个整数 N 和 K。
第二行包含一个长度为 N 的由大写字母构成的字符串 S。
输出格式
每组数据输出一个结果,每个结果占一行。
结果表示为 Case #x: y,其中 x 为组别编号(从 1 开始),y 为所需最少操作次数。
数据范围
全部数据:1≤T≤100,0≤K≤N/2。
测试点 1 (小数据测试点):1≤N≤100。
测试点 2 (大数据测试点):最多不超过 10 组数据满足,1≤N≤2×105,其余数据满足,1≤N≤100。
样例
输入样例:
2
5 1
ABCAA
4 2
ABAA
输出样例:
Case #1: 0
Case #2: 1
样例解释
对于测试数据 1,给定字符串的优良分数刚好为 1,所以不需要任何操作。
对于测试数据 2,将索引 1 处的字符改为 B 即可。
算法1
(遍历统计) $O(n)$
时间复杂度
参考文献
python3 代码
T = int(input())
for t in range(1, T + 1):
[n, k] = [int(x) for x in input().split()]
s = input()
cnt = 0
for i in range(n // 2):
cnt += (s[i] != s[n-1-i])
print("Case #{}: {}".format(t, abs(cnt - k)) )
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T; cin >> T;
for (int t = 1; t < T + 1; t ++)
{
int n; cin >> n;
int k; cin >> k;
string s; cin >> s;
int cnt = 0;
for (int i = 0; i < n / 2; i ++)
if (s[i] != s[n-1-i])
cnt ++;
cout << "Case #" << t << ": " << abs(cnt - k) << endl;
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla