- K-优字符串
题目描述
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
(无)
时间复杂度
。。。。。。
参考文献
。。。。。。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int t,k,n,m; //不需讲解
char c[200001];
cin>>t;//输入
for(int i=1;i<=t;i++){//循环到t
m=0;//记录
cin>>n>>k>>c+1;//输入
for(int i=1;i<=n/2;i++)//循环到n/2
if(c[i]!=c[n-i+1])//核心
m++;
printf("Case #%d: %d\n",i,abs(k-m));//输出k-m的绝对值
}
return 0;//完成
}
记得点赞。。。。。。
这个OJ也有题解?
addd
为什么是不相等时就m++
e,我也不知道
作为ikun这能不知道?不匹配的对数统计出来,然后减去需要达到的不匹配对数,就是操作数
e,有没有可能这只是我懒得回答他QAQ
1.两年前的问题
2.我根本没看题和代码QAQ
点赞乃成功,呵呵