【蓝桥真题3】蓝桥改革变难,想进国赛这些能力你可缺一不可(下)

简介: 【蓝桥真题3】蓝桥改革变难,想进国赛这些能力你可缺一不可

🍒5.经典必做大题系列


🚀5.1k倍区间

image.png


题目链接:k倍区间https://www.lanqiao.cn/problems/97/learning/


      之所以会说这道题,是因为这道题在蓝桥杯中的大题中算简单的。力扣甚至有和它一样的原题(而且只是mid的难度)。只不过有一点区别,但是做法几乎是完全一样的。首先和大家讲明一个定理——同余定理


同予定理——想要 b - a为 k 的倍数,只需要确保 b 和 a 模 k 相同即可


image.png


        掌握了这个定理,我们就能去分析题目了。首先要找子数组,肯定要想到利用前缀和数组去查找(没想到的要反省了)。当在前缀和数组中遍历到第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上取跑一跑满分没问题。


image.png


✈️5.2子串分值


image.png


    题目链接:子串分值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这个区间内的它才可以得分。画个草图给大家理解下


image.png


        通过上面的思路我们去算出所有的字符的得分就是我们的答案。以图中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);
  }
}

拿去跑跑果不其然拿了满分😆


image.pngimage.png

image.png

相关文章
|
存储 分布式计算 Java
详细探讨在线上环境中慎用BigDecimal的原因和可能的替代方案
详细探讨在线上环境中慎用BigDecimal的原因和可能的替代方案
428 0
详细探讨在线上环境中慎用BigDecimal的原因和可能的替代方案
electron解决创建新窗口html文件不能引入ipcRenderer通信
electron解决创建新窗口html文件不能引入ipcRenderer通信
|
算法 开发者 索引
二分算法详解
本文介绍了二分查找及其相关问题的解决方法,包括基本的二分查找、查找元素的第一个和最后一个位置、求平方根、搜索插入位置、寻找峰值和旋转数组中的最小值等问题。通过详细分析每种情况下的二分查找策略,如循环条件、区间划分及特殊情况处理,提供了清晰的代码实现。适用于算法初学者和需要巩固二分查找技巧的开发者。
407 18
二分算法详解
|
5月前
|
编解码 安全 BI
二维码技术如何助力医疗行业提质增效?从设备管理到健康宣教到的全场景应用
医疗设备管理、院感防控、资产盘点和健康宣教是医疗机构日常运营中的重要环节,但传统手工方式常导致效率低下、数据不透明等问题。草料二维码提供了一种轻量化解决方案:通过为每台设备、物品或宣传资料绑定专属二维码,实现信息查询、维护记录、消毒登记及患者教育等功能的数字化管理。该方案操作简单、成本低且上手快,适合基层医疗机构使用,有效提升管理效率与服务质量,助力医疗信息化建设。
156 35
二维码技术如何助力医疗行业提质增效?从设备管理到健康宣教到的全场景应用
|
Linux 编译器 开发工具
Android内核的编译过程
Android内核的编译过程
209 0
|
网络协议 算法 安全
【专栏】RIP是一种古老的内部网关协议,使用距离矢量算法,基于跳数更新路由表,最古老的距离矢量协议
【4月更文挑战第28天】RIP是一种古老的内部网关协议,使用距离矢量算法,基于跳数更新路由表。其工作原理包括周期性更新、度量标准、路由表更新和防止计数到无穷问题的技术。RIP简单易用,适合小规模网络,但在大规模网络中效率低且有限制。随着OSPF和EIGRP等协议的发展,RIP在大型网络中的应用减少,但在中小型网络和遗留系统中仍有其地位。RIPv2的改进提高了安全性与灵活性。尽管逐渐被替代,RIP在理解路由协议基本概念和历史中仍具价值。
419 1
|
消息中间件 C# RocketMQ
MQ产品使用合集之设置rocketmq的timerMaxDelaySec时间出现报错如何解决
消息队列(MQ)是一种用于异步通信和解耦的应用程序间消息传递的服务,广泛应用于分布式系统中。针对不同的MQ产品,如阿里云的RocketMQ、RabbitMQ等,它们在实现上述场景时可能会有不同的特性和优势,比如RocketMQ强调高吞吐量、低延迟和高可用性,适合大规模分布式系统;而RabbitMQ则以其灵活的路由规则和丰富的协议支持受到青睐。下面是一些常见的消息队列MQ产品的使用场景合集,这些场景涵盖了多种行业和业务需求。
754 4
|
机器学习/深度学习 运维 监控
信息安全:入侵检测技术原理与应用.(IDS)
信息安全:入侵检测技术原理与应用.(IDS)
726 1
|
数据安全/隐私保护 网络虚拟化 网络协议
2024年广东省网络系统管理样题第1套网络搭建部分
2024年广东省网络系统管理样题第1套网络搭建部分
2024年广东省网络系统管理样题第1套网络搭建部分
|
JSON Cloud Native Java
通过 Higress Wasm 插件 3 倍性能实现 Spring-cloud-gateway 功能
本文将和大家一同回顾 Spring Cloud Gateway 是如何满足 HTTP 请求/响应转换需求场景的,并为大家介绍在这种场景下使用 Higress 云原生网关的解决方案,同时还对比了两者的性能差异。
69366 263