AcWing 6123. 哞叫时间

题目

博主解题思路：

首先熟读题目后，发现要求的是，一段定长字符串中的abb形式的定长字串，如果定长字串的数量大于等于F的话，那么就可以列为一组答案，值得注意的是，字符串中可能存在至多一个字符与原始字符串不用，也就是说，可以在字串中更改一个字符，如果字符更改后的关联的定长字串的数量能大于等于F，那么也可以列入答案当中，那么思路就很明显了，首先，我们定义一个cnt数组，用来统计原字符串中的定长字串数量，再依次改变原字符串中的每一个字符，共有25种更改情况，每次改变字符，都会改变三个定长字串，如：

值得注意的是，每次我们更改字符之前，我们将原来的关联的三个字串数量-1，这样子我们修改之后，得到新字串，加入到字串数量中，才能有效的判断是否出现了有效的答案字串，不然就会多加1，在改变字符之后，对应的三个新字串数量加一，判断是否有答案字串，如果有答案字串，那么就标记一下（开辟一个新的数组来记录答案字串），更新完之后，再减去字串数量-1，最后恢复现场，将原字符放回原位，并更新原字串数量，这样子就能达到至多只有一个字符改变的效果，最后统计答案字串数量，并输出答案子串

说实话这个题目难度对目前的我来说难度还是比较大，但是搞懂本题之后，对我的思维拓展还是比较大，模拟题目或者需要重复执行类似操作的题目，可以开辟一个更新函数来重复操作，直观并且更为简洁

答案：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66


import java.util.Scanner;

public class Main{
    private static final int N = 20010;  // N 设为静态常量
    private static final int M = 26;
    private static Integer n;
    private static Integer m;

    private static char[] s;

    private static int[][] cnt=new int[M][M];
    private static boolean[][] ans=new boolean[M][M];

    public static void main(String agrs[]){
        Scanner sc=new Scanner(System.in);
        n =sc.nextInt();
        m=sc.nextInt();
        sc.nextLine();
        String S=sc.nextLine();
        s=S.toCharArray();
        //先将字符转换为数字
        for (int i = 0; i < s.length; i++) s[i]-='a';
        //先统计原字符串中的哞叫可能
        update(0,n-1,1);
        for (int i = 0; i < n; i++) {
            char t=s[i];
            update(i-2,i+2,-1);
            for (int j = 0; j < 26; j++) {
                if (j!=t){
                    s[i]= (char) j;
                    update(i-2,i+2,1);
                    update(i-2,i+2,-1);
                }
            }
            s[i]=t;
            update(i-2,i+2,1);
        }
        int res=0;
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26 ; j++) {
                if (ans[i][j]) res++;
            }
        }
        System.out.println(res);
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26 ; j++) {
                if (ans[i][j]) {
                    System.out.println(String.format("%c%c%c", (char) (i + 'a'), (char) (j + 'a'), (char) (j + 'a')));
                }
            }
        }

    }

    public static void update(int l,int r,int v){
        l=Math.max(l,0);
        r=Math.min(r,n-1);
        for (int i = l; i+2 <= r ; i++) {
            char a=s[i],b=s[i+1],c=s[i+2];
            if(a!=b&&b==c){
                cnt[a][b]+=v;
                if (cnt[a][b]>=m) ans[a][b]=true;
            }
        }
    }
}