【蓝桥真题7】贴吧车队作弊?应对线上考和双填趋势,我们该如何备考?(上)

简介: 【蓝桥真题7】贴吧车队作弊?应对线上考和双填趋势,我们该如何备考?

🎃 1.打包(二分答案)


Lazy有N个礼物需要打成M个包裹,邮寄给M个人,这些礼物虽然很便宜,但是很重。Lazy希望每个人得到的礼物的编号都是连续的。为了避免支付高昂的超重费,他还希望让包裹的最大重量最小。


题目链接:打包 http://lx.lanqiao.cn/problem.page?gpid=T2978


       题目的意思有一点容易理解错(蓝桥题目特色,生怕你读懂哈哈哈),刚开始我还以为选一个长度为M的子数组保证和最小。但其实它的意思是将N个礼物分成若M个包裹,每个包裹可以有若干个礼物,然后让我们求这些包裹中最大重量最小的值。


      像这种求某某某最大的最小值,或者最小的最大值大家一定要想到二分。很多人肯定心想,切二分嘛,套个模板不就好啦。确实是套个模板不就好了,但是对于二分的题目是分为两种,一种是求值二分,而另外一种就是二分答案。直接对答案去进行二分查找,所以这题我们直接对包括的最大重量的最小值这个属性进行二分,所以问题来了,如何确定边界和check函数逻辑?


      对于左边界left,它肯定是我们所有礼物中最重礼物的重量,因为礼物必须全部打包,最重的包裹在最轻的情况下就是只单独选最重的礼物

      对于右边界right,我们直接考虑极限情况,全部礼物的重量的总值就好,既然是二分,只有答案能在区间里,那就肯定能找到答案

      至于最核心的check函数,无非则是判断选择当前重量,能否分成至多M个包裹,每次选择连续且重量之和不超过mid的的礼物打包为一个包裹,最后的包裹数量小于等于M说明符合,我们让r=mid,否则l=mid+1.


      代码转换:

import java.util.Scanner;
public class Main {
  static int N=100010;
  static int[] arr=new int[N];
  static int n,m;
  public static void main(String[] args) {
  Scanner sc=new Scanner(System.in);
  n=sc.nextInt();
  m=sc.nextInt();
  int max=0;
  int sum=0;
  for(int i=1;i<=n;++i) {
    arr[i]=sc.nextInt();
    sum+=arr[i];
    max=Math.max(max, arr[i]);
  }
  int l=max;
  int r=sum;
  while(l<r) {
    int mid=(l+r)>>1;
    if(check(mid)) r=mid;
    else l=mid+1;
  }
  System.out.println(l);
  }
  static boolean check(int target) {
  int count=0;
  int tmp=0;
  for(int i=1;i<=n;++i) {
    count+=arr[i];
    if(count>target){
    count=0;
    tmp++;
    i--;
    }else if(i==n){
    tmp++;
    }
  }
  return tmp<=m;
  }
}


👻2. 跳跃的小明(动态规划)


 有一条长为n的走廊,小明站在走廊的一端,每次可以跳过不超过p格,每格都有一个权值wi。

 小明要从一端跳到另一端,不能回跳,正好跳t次,请问他跳过的方格的权值和最大是多少?


题目链接:跳跃的小明http://lx.lanqiao.cn/problem.page?gpid=T770


      比较明显的DP问题:


  1.  状态表示:F[i][j]:通过j步走到第i格的最大权值


  1.  转移方程分析:分析最后一步是通过走了跳了第几格到达第i格。如果最后一步是通过跳跃1格到达第i格,那么转移方程应该是,w[i]是第i格的权值。如果最后一步是通过跳跃2格,则转移方程是:。最多是通过跳跃p格到达第i格,我们只需要在这么多方案中取一个最大值即可。


  1.  初始化:由于权值是带有负数的,所以我们首先需要将所有方案初始化成负无穷,然后初始化第一步走一格一直到第一步走p格的情况。最后答案是f[n+1][t],因为对于给定的数组其实左右两头有两个权值为0的位置,那才是我们的起点和终点。


       代码转换:

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    static int N=1010;
    static int n,p,t;
    //通过j步走到第i个格子的最大权值
    static int[][] f=new int[N][N];
    static int[] arr=new int[N];
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        p=sc.nextInt();
        t=sc.nextInt();
        for(int i=1;i<=n;++i) arr[i]=sc.nextInt();
        for(int[] a:f) {
            Arrays.fill(a,-0x3f3f3f);
        }
        //初始化:通过第一步能走到的位置
        for(int i=1;i<=p&&i<=n+1;++i) f[i][1]=arr[i];
        //走到第i格
        for(int i=1;i<=n+1;++i){
            //通过j步
            for(int j=2;j<=t;++j){
                //上一次走了k步到达第i格
                for(int k=1;k<=p&&k<=i;++k) {
                    f[i][j]=Math.max(f[i-k][j-1]+arr[i],f[i][j]);
                }
            }
        }
        System.out.println(f[n+1][t]);
    }
}


🎆3.大胖子走迷宫(BFS)


image.png

image.png


题目链接:大胖子走迷宫 http://lx.lanqiao.cn/problem.page?gpid=T2739#submitpanel


       比较经典的BFS问题,稍微属于一点变种的BFS,首先大家要认真理解题目的意思,摒弃掉我们平常做BFS问题的思维,首先思考以下几个问题:


      1.每次行动的决策,是否只能是上下左右移动?


      2.对于能否移动的判断,我们应该如何判定?


      疑问解答:


       1.由于在某些地点,可能因为小明太胖而走不过去,而这条路径却是唯一的路径,所以小明得在原地等待变小后再通过,或者其实小明走其他路还不如在原地变小再过去,所以在上下左右移动的决策中,还应该加上原地等待


       2.由于小明太胖,所以他占用的区域可能是5X5或者3X3,所以我们在移动到(x,y)坐标时,不仅需要判断x,y和合法坐标,还得判断以x,y为中心周围的3x3或者5x5都得是合法的。这样我们可以用一个变量count记录成小明的膨胀因子,每次判断是否合法时,都需要在原坐标上加上或者减去膨胀因子,最开始是5x5,所以膨胀因子为2,当变成3x3时,膨胀因子为1,最后变回原形以后膨胀因子则变为0。

相关文章
|
9月前
|
人工智能 文字识别 自然语言处理
多模态数据信息提取解决方案测评报告
《多模态数据信息提取解决方案测评报告》概述了该方案在部署、操作界面、文档、函数模板及官方示例等方面的表现。其功能强大,涵盖OCR、NLP、物体检测等五大核心能力,适用于多种应用场景。系统运行稳定,尤其在图像识别方面表现出色,但在处理长篇文档和低质量音视频时有改进空间。尽管存在一些小问题,如配置复杂性和依赖库兼容性,整体用户体验良好,推荐给企业和开发者使用。
142 9
节流
【10月更文挑战第17天】
对excel读写的三个模块,xlsxwriter最牛,xlwt , xlrd,openpyxl
对excel读写的三个模块,xlsxwriter最牛,xlwt , xlrd,openpyxl
|
机器学习/深度学习 前端开发 算法
利用机器学习优化Web前端性能的探索与实践
本文将介绍如何利用机器学习技术来优化Web前端性能,探讨机器学习在前端开发中的应用,以及通过实际案例展示机器学习算法对前端性能优化的效果。通过结合前端技术和机器学习,提升Web应用的用户体验和性能表现。
|
移动开发 小程序 API
微信小程序的一些开发限制
微信小程序的一些开发限制
495 1
|
运维 Kubernetes 负载均衡
Docker不香吗?为什么还要用k8s
Docker不香吗?为什么还要用k8s
Docker不香吗?为什么还要用k8s
|
Cloud Native 容灾 安全
Nacos 开源、自研、商业化三位一体战略解读
Nacos作为整个阿里云原生三位战略中的核心组成部分,我们在2018年以Configserver/VIPServer/Diamond为基础通过Nacos开源输出阿里十年沉淀的注册中心和配置中心能力,并且快速成为国内首选。并且通过云产品MSE以BaaS模式输出解决方案能力。
1291 87
|
移动开发 前端开发 PHP
分享105个PHP源码,总有一款适合您
分享105个PHP源码,总有一款适合您
391 0
|
编译器 C++
VS2022查看类内存布局
先右键点击属性, 选择左侧的C/C++==>命令行,然后在其他选项这里写上/d1 reportAllClassLayout,它可以看到所有相关类的内存布局。切切注意, Layout跟指定的结构/类名CTest之间没有空格, 有空格就不对了. 这会只输出指定的结构的内存布局.这个开关输出所有类, 主要是一大堆编译器内部的结构的内存布局, 其实还有一个开关是。
344 0
|
机器学习/深度学习 自然语言处理 vr&ar
除了Transformer,还有哪些基于自注意力机制的模型?
除了Transformer,还有哪些基于自注意力机制的模型?
317 0