【题目描述】
把一个长度为n的字符串,分成(2 * k + 1)份小非空字符串。其中第i 个小字符串与第2 * k + 1 - i个字符串对称(abc与cba对称),问能不能做到;
【输入格式】
第一行输入一个整数 t (1 <= t <= 100),表示测试组数;
每组样例的第一行分别为 n, k (1 <= n <= 100, 0 <= k <= n / 2), 分别为字符串长度 n 和 题干所描述的参数 k;
第二行为一个长度为 n 的字符串;
【输出格式】
对于每组样例,如果能做到,输出“YES”, 如果不能做到, 输出“NO”;
【解题思路】
(1)要求所分成的小字符串非空,故 n >= 2 * k + 1, 而题目所给的范围不一定满足这一条件,比如n = 2 * k的情况,因此要特判;
(2)对字符串对称的要求本质是回文;
(3)关于对称长度k以及a_k + 1的理解:从最左开始遍历,要求左右对称的部分长度大于等于k即可,中间部分的对称性不做要求,只要求非空;
(4)在解题的时候理解了对称即回文,理解了n、k大小关系,但没有注意到a_k+1的作用,类似能否做到的题,一般思路都是找最容易做到的情况是怎样的,然后判断是否满足,比如此处,只要有k位满足就可以做到,类似问题还有the sum of the odds;
【正确代码】
1 #include <iostream> 2 3 using namespace std; 4 5 const int N = 110; 6 7 char a[N]; 8 9 int flag(char a[], int n, int k) 10 { 11 int flag = 1; 12 for (int i = 0, j = n - 1; i < k; i ++, j --) 13 if(a[i] != a[j]){ 14 flag = 0; 15 break; 16 } 17 return flag; 18 } 19 20 int main() 21 { 22 int t; 23 scanf("%d", &t); 24 25 while(t --) 26 { 27 int n, k; 28 scanf("%d%d", &n, &k); 29 scanf("%s", a); 30 if(n < 2 * k + 1) puts("NO"); 31 else 32 { 33 if(flag(a, n, k)) puts("YES"); 34 else puts("NO"); 35 } 36 } 37 return 0; 38 }