🍒5.经典必做大题系列
🚀5.1k倍区间
题目链接：k倍区间https://www.lanqiao.cn/problems/97/learning/
之所以会说这道题，是因为这道题在蓝桥杯中的大题中算简单的。力扣甚至有和它一样的原题（而且只是mid的难度）。只不过有一点区别，但是做法几乎是完全一样的。首先和大家讲明一个定理——同余定理
同予定理——想要 b - a为 k 的倍数，只需要确保 b 和 a 模 k 相同即可
掌握了这个定理，我们就能去分析题目了。首先要找子数组，肯定要想到利用前缀和数组去查找（没想到的要反省了）。当在前缀和数组中遍历到第i个时，此时获得arr[i]%k的值，此时i的左边（也就是[0,i-1]区间）我们取为j，如果arr[j]%k==arr[i]%k，说明[j,i]这个区间和是k的倍数。根据以上写出代码
import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class k倍区间 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int N=sc.nextInt(); int k=sc.nextInt(); //注意要用long数组,数据量较大 long[] arr=new long[N+1]; //Map前面也得用Long,因为有long参与的运算返回值也是long Map<Long,Integer> map=new HashMap<Long,Integer>(); //获得前缀和数组 for(int i=0;i<N;++i) { arr[i+1]=arr[i]+sc.nextLong(); } long ans=0; //千万不能忘记把这个忘记放入 map.put(0L,1); for(int i=1;i<=N;++i) { ans+=map.getOrDefault(arr[i]%k, 0); map.put(arr[i]%k, map.getOrDefault(arr[i]%k, 0)+1); } System.out.println(ans); } }
放到蓝桥OJ上取跑一跑满分没问题。
✈️5.2子串分值
题目链接：子串分值https://www.lanqiao.cn/problems/499/learning/
题目分析：这道题是可以暴力做的，可以拿到60分。每次计算以S[i]为字符串的头往后遍历计算可以获得的分数。对于S[i,j]的子数组中只出现一次的元素我们可以通过S[i,j-1]去获得，用不着每次都遍历。这里我用一个Set去记录只出现一次的元素，再用一个Set记录重复出现过的元素（感觉可以优化但是没有去优化）
public class 子串分值 { //过了6个得了六十分 public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s=sc.next(); int count=0; int n=s.length(); for(int i=0;i<n;++i){ int ans=1; //放只出现一次的字符 Set<Character> set1=new HashSet<>(); //放多次出现的字符 Set<Character> set2=new HashSet<>(); set1.add(s.charAt(i)); for(int j=i+1;j<n;++j) { char c=s.charAt(j); if(set1.contains(c)) { set1.remove(c); set2.add(c); }else if(!set1.contains(c)&&!set2.contains(c)) { set1.add(c); } //set1的长度即是只出现了一次的元素 ans+=set1.size(); } count+=ans; } System.out.println(count); } }
满分做法：
做到这里，我们可以去分析一下。一个字符什么时候可以贡献分数？
题目要求在一个字符串中，只有只出现一次的元素可以得分。所以说明什么适合它不能得分呢？是不是就是当它和前一个和它相同的字符或者后一个和它相同的字符在一个区间时，它就无法得分。我以abcdaefa为例：中间这个a在不和它前一个a和后一个a在同一个子串中时，它都可以得分。换个说法：这个a只有在bcdaef这个区间内的它才可以得分。画个草图给大家理解下
通过上面的思路我们去算出所有的字符的得分就是我们的答案。以图中j位置的a为例，前一个a的元素为i（没有则记为-1），后一个a的位置为k（没有则记为n）。则j位置的a的得分就是（j-i）(k-j)。所以基于此思路我们需要用一个数组pre记录每个字符前一次出现的位置，next为后一次出现的位置。一个数组where记录每个字符最后一次出现的下标。难点在于三个数组的更新，得到三个数组后答案就很好得到了。
import java.util.Arrays; import java.util.Scanner; public class 子串分值2 { //满分答案 public static void main(String[] args) { Scanner sc=new Scanner(System.in); String s=sc.next(); int n=s.length(); //记录每个字符a在前一次出现的位置，如果没有则为-1 int[] pre=new int[n]; //记录每个字符a在后一次出现的位置，如果没有则为n int[] next=new int[n]; int[] where=new int[26];//统计每个字符最后一次出现的下标 Arrays.fill(where, -1); //这样能得到i处字符前一次出现的位置 for(int i=0;i<n;++i) { pre[i]=where[s.charAt(i)-'a']; where[s.charAt(i)-'a']=i; } Arrays.fill(where, n); for(int i=n-1;i>=0;i--) { next[i]=where[s.charAt(i)-'a']; where[s.charAt(i)-'a']=i; } //统计答案 int ans=0; for(int j=0;j<n;++j) { ans+=(j-pre[j])*(next[j]-j); } System.out.println(ans); } }
拿去跑跑果不其然拿了满分😆
