Codeforces | 1496A Split it!

【题目描述】

  把一个长度为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 }

 

Codeforces | 1496A Split it!

上一篇:《MySQL必知必会》整理


下一篇:get 和post 区别