蓝桥杯|历届真题:子串分值和

jupiter
2022-03-20 / 0 评论 / 618 阅读 / 正在检测是否收录...
温馨提示:
本文最后更新于2022年03月20日,已超过707天没有更新,若内容或图片失效,请留言反馈。

1.题目

【问题描述】
对于一个字符串$S$,我们定义S的分值$f(S)$为$S$中恰好出现一次的字符个数。例如$f(aba)=1,f(abc)=3,f(aaa) = 0$。
现在给定一个字符串$S[0..n-1]$(长度为n),请你计算对于所有S的非空子串$S[i..j](0 \leq i \leq j \lt n)$,$f(S[i..j])$的和是多少。
【输入格式】
输入一行包含一个由小写字母组成的字符串S。
【输出格式】
输出一个整数表示答案。
【样例输入】

ababc

【样例输出】

21

【样例说明】

子串,f值
a,1
ab,2
aba,1
abab,0
ababc,1
b,1
ba,2
bab,1
babc,2
a,1
ab,2
abc,3
b,1
bc,2
c,1

【评测用例规模与约定】
对于20%的评测用例, $1 \leq n \leq 10$;
对于40%的评测用例, $1 \leq n \leq 100$;
对于50%的评测用例, $1 \leq n \leq 1000$;
对于60%的评测用例, $1 \leq n \leq 10000$;
对于所有评测用例, $1 \leq n \leq 100000$;

2. 题解

2.1 思路分析

思路1:暴力求解(50分)
    首先需要写一个计算子串得分的函数
        1.统计各个字符出现的次数
        2.得到只出现一次的字符数
    然后遍历所有的子串并对其得分进行求和

思路2:动态规划(50分)
    考虑子串之间的关系,即新增一个字符对子串得分的影响,从避免重复统计字符出现次数导致耗时

思路3:考虑每个位置的字符只出现一次的子串总数(100分)
用 pre[i] 记录第 i 位置上的字母上一次出现的位置,用 next[i] 记录第 i 位置上的字母下一次出现的位置;
那么往左最多能延伸到 pre[i] + 1,其到第 i 个字母一共有 i - pre[i] 个字母;
同理往右最多能延伸到 next[i] - 1,其到第 i 个字母一共有 next[i] - i 个字母;
二者相乘,就是该 i 位置上的字符只出现一次的子串总数
具体可以结合上述输入输出例子思考。

2.2 代码实现

  • 思路1:暴力求解
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);
    public static int getScore(String str){
        int score = 0;
        char[] strChars = str.toCharArray();
        int[] charCounter = new int[26];
        for (int i = 0; i < 26; i++)charCounter[i]=0;

        for (int i = 0; i < strChars.length; i++) {
          charCounter[(int)(strChars[i]-'a')]++;
        }

        for (int i = 0; i <26 ; i++) {
            if(charCounter[i]==1)score++;
        }
        return score;
    }
    
    public static void main(String[] args) {
        String str = scanner.next();
        char[] strChars = str.toCharArray();
        int scoreSum = 0;
        for (int i = 0; i < strChars.length; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = i; j < strChars.length; j++) {
                sb.append(strChars[j]);
                scoreSum+=getScore(sb.toString());
            }
        }
        System.out.println(scoreSum);
    }
}
// 简化子串得分求解
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);
    
    public static void main(String[] args) {
        String str = scanner.next();
        int len = str.length();
        char[] strChars = str.toCharArray();

        int scoreSum = 0;

        for (int i = 0; i < strChars.length; i++) {
            Set<Character> set1 = new HashSet<>(); //统计所有字符串
            Set<Character> set2 = new HashSet<>();//统计不止出现一次的字符串
            for (int j = i; j < strChars.length; j++) {
                if(set1.contains(strChars[j])){
                    set2.add(strChars[j]);
                }
                set1.add(strChars[j]);
                scoreSum+= set1.size()-set2.size();
            }
        }
        System.out.println(scoreSum);
    }
}
  • 思路2:动态规划
// 40分 会爆内存
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        String str = scanner.next();
        char[] strChars = str.toCharArray();
        int[][] dp = new int[str.length()][str.length()];
        int scoreSum = 0;
        for (int i = 0; i < str.length(); i++) {
            for (int j = 0; j < str.length();j++) {
                if(j<i){
                    dp[i][j] = 0;
                }else if(j==i){
                    dp[i][j] = 1;
                }else {
                    int startIndex = str.substring(i,j).indexOf(strChars[j]);
                    if(startIndex!=-1){//旧的子包含待加入字符
                        int endIndex = str.substring(i,j).lastIndexOf(strChars[j]);
                        if(startIndex==endIndex){//旧的子串只包含1个待加入字符
                            dp[i][j]=dp[i][j-1]-1;
                        }else {//旧的子串包含多个个待加入字符,之前已进行了-1操作,无需再减
                            dp[i][j]=dp[i][j-1];
                        }
                    }else {//旧的子不包含待加入字符
                        dp[i][j]=dp[i][j-1]+1;
                    }
                }
                scoreSum += dp[i][j];
            }
        }

        System.out.println(scoreSum);
    }
}
// dp优化 避免爆内存 还是50分
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);
    public static void main(String[] args) {
        String str = scanner.next();
        int len = str.length();
        char[] strChars = str.toCharArray();
        int lastDpstate = 0;
        int scoreSum = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len;j++) {
                if(j<i){
                    lastDpstate=0;
                }else if(j==i){
                    lastDpstate = 1;
                }else {
                    int startIndex = str.substring(i,j).indexOf(strChars[j]);
                    if(startIndex!=-1){//旧的子串包含待加入字符
                        int endIndex = str.substring(i,j).lastIndexOf(strChars[j]);
                        if(startIndex==endIndex){//旧的子串只包含1个待加入字符
                            lastDpstate=lastDpstate-1;
                        }
                    }else {
                        lastDpstate=lastDpstate+1;
                    }
                }
                scoreSum += lastDpstate;
            }
        }

        System.out.println(scoreSum);
    }
}
  • 思路3:考虑每个位置的字符只出现一次的子串总数
// 60分
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        String str = scanner.next();
        char[] strChars = str.toCharArray();
        int scoreSum = 0;

        for (int i = 0; i < strChars.length; i++) {
            int nextIndex = str.substring(i+1).indexOf(strChars[i]); //下一个strChars[i]字符的位置
            nextIndex = nextIndex==-1? strChars.length : nextIndex+i+1;

            int preIndex = str.substring(0,i).lastIndexOf(strChars[i]);////前一个strChars[i]字符的位置

            scoreSum += (nextIndex-i)*(i-preIndex);
        }

        System.out.println(scoreSum);
    }
}
// 优化 100分
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        String str = scanner.next();
        char[] strChars = str.toCharArray();
        int len = strChars.length;
        int scoreSum = 0;

        int[] pre = new int[len];
        int[] next = new int[len];

        Arrays.fill(pre,-1);
        Arrays.fill(next,len);


        // 求解next[i]
        for (int i = 0; i < len; i++) {
            for (int j = i+1; j < len; j++) {
                if(strChars[i]==strChars[j]){
                    next[i]=j;
                    break;
                }
            }
        }

        // 求解pre[i]
        for (int i = 0; i < len; i++) {
            for (int j = i-1; j>=0; j--) {
                if(strChars[i]==strChars[j]){
                    pre[i]=j;
                    break;
                }
            }
        }
        
        // 计算得分和
        for (int i = 0; i < len; i++) {
            scoreSum += (next[i]-i)*(i-pre[i]);
        }

        System.out.println(scoreSum);
    }
}

2.3 提交结果

  • 思路1:暴力求解
评测点序号评测结果得分CPU使用内存使用下载评测数据
1正确10.0078ms22.17MB输入 输出
2正确10.00109ms22.19MBVIP特权
3正确10.00109ms22.19MBVIP特权
4正确10.0093ms24.36MBVIP特权
5正确10.00359ms233.1MBVIP特权
6运行超时0.00运行超时281.0MBVIP特权
7运行超时0.00运行超时283.3MBVIP特权
8运行超时0.00运行超时435.0MBVIP特权
9运行超时0.00运行超时282.5MBVIP特权
10运行超时0.00运行超时282.6MBVIP特权
  • 思路2:动态规划
评测点序号评测结果得分CPU使用内存使用下载评测数据
1正确10.0078ms22.17MB输入 输出
2正确10.00109ms22.19MBVIP特权
3正确10.00109ms22.19MBVIP特权
4正确10.0093ms24.36MBVIP特权
5正确10.00359ms233.1MBVIP特权
6运行超时0.00运行超时281.0MBVIP特权
7运行超时0.00运行超时283.3MBVIP特权
8运行超时0.00运行超时435.0MBVIP特权
9运行超时0.00运行超时282.5MBVIP特权
10运行超时0.00运行超时282.6MBVIP特权
  • 思路3:考虑每个位置的字符只出现一次的子串总数
评测点序号评测结果得分CPU使用内存使用下载评测数据
1正确10.00109ms22.40MB输入 输出
2正确10.0046ms22.40MBVIP特权
3正确10.0078ms22.41MBVIP特权
4正确10.0093ms22.39MBVIP特权
5正确10.0078ms22.44MBVIP特权
6正确10.00125ms23.34MBVIP特权
7正确10.00125ms26.62MBVIP特权
8正确10.00140ms26.70MBVIP特权
9正确10.00109ms26.51MBVIP特权
10正确10.00171ms26.66MBVIP特权

参考资料

  1. http://lx.lanqiao.cn/problem.page?gpid=T2858
  2. 蓝桥杯试题 历届试题 子串分值和
0

评论 (0)

打卡
取消