搜索到
1
篇与
的结果
-
蓝桥杯|历届真题:子串分值和 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特权参考资料http://lx.lanqiao.cn/problem.page?gpid=T2858蓝桥杯试题 历届试题 子串分值和
