第 3 场 蓝桥杯小白入门赛 解题报告 | 珂学家 | 单调队列优化的DP + 三指针滑窗

前言

在这里插入图片描述

整体评价

T5, T6有点意思，这场小白入门场，好像没真正意义上的签到，整体感觉是这样。

A. 召唤神坤

思路: 前后缀拆解

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
  // 请在此输入您的代码
  int n;
  cin >> n;
  vector<int> arr(n);
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  vector<int> pre(n);
  vector<int> suf(n);

  pre[0] = -1;
  for (int i = 1; i < n; i++) {
    pre[i] = max(arr[i - 1], pre[i - 1]);
  }
  suf[n - 1] = -1;
  for (int i = n - 2; i >= 0; i--) {
    suf[i] = max(arr[i + 1], suf[i + 1]);
  }

  int res = 0;
  for (int i = 1; i < n - 1; i++) {
    res = max(res, (pre[i] + suf[i]) / arr[i]);
  }
  cout << res << endl;

  return 0;
}

B. 聪明的交换策略

思路: 模拟+枚举

#include <bits/stdc++.h>
using namespace std;

int main()
{
  // 请在此输入您的代码
  int n;
  cin >> n;
  string s;
  cin >> s;

  // long long res = 1LL << 60;

  long long acc1 = 0, acc2 = 0;
  int t0 = 0, t1 = 0;
  for (int i = 0; i < n;i++) {
    char c = s[i];
    if (c == '0') {
      acc1 += (i - t0);
      t0++;
    } else {
      acc2 += (i - t1);
      t1++;
    }
  }
  cout << min(acc1, acc2) << endl;

  return 0;
}

C. 怪兽突击

思路: 枚举

#include <bits/stdc++.h>
using namespace std;
int main()
{
  // 请在此输入您的代码

  int n, k;
  cin >> n >> k;
  vector<int> arr(n), brr(n);
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> brr[i];
  }

  long long res = 1LL << 60;

  long long pre = 0;
  long long mv = arr[0] + brr[0];
  for (int i = 0; i < n; i++) {
    if (i + 1 > k) break;
    pre += arr[i];
    mv = min(mv, (long long)arr[i] + brr[i]);
    res = min(res, pre + (k - i - 1) * mv);
  }
  cout << res << endl;

  return 0;
}

D. 蓝桥快打

思路: 二分

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

int main()
{

  // 请在此输入您的代码
  int t;
  cin >> t;
  while (t-- > 0) {
    int a, b, c;
    cin >> a >> b >> c;

    // 可以二分的
    int l = 1, r = b;
    while (l <= r) {
      int m = l + (r - l) / 2;

      // *) 
      int times = (b + m - 1) / m;
      if ((int64)(times - 1) * c < a) {
        r = m - 1;
      } else {
        l = m + 1;
      }   

    }

    cout << l << endl;

  }

  return 0;

}

E. 奇怪的段

思路: 单调队列优化的DP

这题只需要维护最大值就行，不需要维护单调队列

其核心是如下的公式

d p [ i ] [ j ] = max ⁡ t = 0 t = j − 1 d p [ i − 1 ] [ t ] + ( p r e [ j + 1 ] − p r e [ t ] ) ∗ w [ i ] dp[i][j] = \max_{t=0}^{t=j-1} dp[i - 1][t] + (pre[j + 1] - pre[t]) * w[i] dp[i][j]=t=0maxt=j−1​dp[i−1][t]+(pre[j+1]−pre[t])∗w[i]

公式拆解后

d p [ i ] [ j ] = max ⁡ t = 0 t = j − 1 ( d p [ i − 1 ] [ t ] − p r e [ t ] ) ∗ w [ i ] ) + p r e [ j ] ∗ w [ i ] dp[i][j] = \max_{t=0}^{t=j-1}(dp[i - 1][t] - pre[t]) * w[i]) + pre[j] * w[i] dp[i][j]=t=0maxt=j−1​(dp[i−1][t]−pre[t])∗w[i])+pre[j]∗w[i]

这样这个递推的时间代价为 O ( 1 ) O(1) O(1)，而不是 O ( n ) O(n) O(n)

这样总的时间复杂度为 O ( n ∗ k ) O(n * k) O(n∗k)


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) {
        AReader sc = new AReader();

        int n = sc.nextInt(), p = sc.nextInt();
        int[] arr = new int[n];
        long[] pre = new long[n + 1];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            pre[i + 1] = pre[i] + arr[i];
        }
        int[] ws = new int[p];
        for (int i = 0; i < p; i++) {
            ws[i] = sc.nextInt();
        }

        // *)
        long inf = Long.MIN_VALUE / 10;
        long[][] dp = new long[p + 1][n];
        for (int i = 0; i <= p; i++) {
            Arrays.fill(dp[i], inf);
        }

        for (int i = 0; i < n; i++) {
            dp[1][i] = pre[i + 1] * ws[0];
        }

        // O(n)
        // dp[i - 1][j] - p * pre[j + 1] + p * pre[j]
        for (int i = 2; i <= p; i++) {
            long tmp = dp[i - 1][0] - ws[i - 1] * pre[1];
            for (int j = 1; j < n; j++) {
                dp[i][j] = tmp + ws[i - 1] * pre[j + 1];
                tmp = Math.max(tmp, dp[i - 1][j] - ws[i - 1] * pre[j + 1]);
            }
        }

        System.out.println(dp[p][n - 1]);

    }

    static
    class AReader {
        private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        private StringTokenizer tokenizer = new StringTokenizer("");
        private String innerNextLine() {
            try {
                return reader.readLine();
            } catch (IOException ex) {
                return null;
            }
        }
        public boolean hasNext() {
            while (!tokenizer.hasMoreTokens()) {
                String nextLine = innerNextLine();
                if (nextLine == null) {
                    return false;
                }
                tokenizer = new StringTokenizer(nextLine);
            }
            return true;
        }
        public String nextLine() {
            tokenizer = new StringTokenizer("");
            return innerNextLine();
        }
        public String next() {
            hasNext();
            return tokenizer.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

//        public BigInteger nextBigInt() {
//            return new BigInteger(next());
//        }
        // 若需要nextDouble等方法，请自行调用Double.parseDouble包装
    }

}

F. 小蓝的反击

思路: 滑窗 + 三指针

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static List<int[]> split(int v) {
        List<int[]> res = new ArrayList<>();
        for (int i = 2; i <= v / i; i++) {
            if (v % i == 0) {
                int cnt = 0;
                while (v % i == 0) {
                    v /= i;
                    cnt++;
                }
                res.add(new int[] {i, cnt});
            }
        }
        if (v > 1) {
            res.add(new int[] {v, 1});
        }
        return res;
    }

    // *)
    static boolean check(int[][] pre, int s, int e, List<int[]> xx) {
        for (int i = 0; i < xx.size(); i++) {
            int tn = xx.get(i)[1];
            if (pre[i][e + 1] - pre[i][s] < tn) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        AReader sc = new AReader();

        int n = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        if (b == 1) {
            System.out.println(0);
            return;
        }

        List<int[]> facs1 = split(a);
        int m1 = facs1.size();
        List<int[]> facs2 = split(b);
        int m2 = facs2.size();

        // 三指针做法
//        int[][] brr1 = new int[m1][n];
        int[][] pre1 = new int[m1][n + 1];

//        int[][] brr2 = new int[m2][n];
        int[][] pre2 = new int[m2][n + 1];

        for (int i = 0; i < n; i++) {
            int v = arr[i];
            for (int j = 0; j < m2; j++) {
                int p = facs2.get(j)[0];
                int tmp = 0;
                while (v % p == 0) {
                    v /= p;
                    tmp++;
                }
//                brr2[j][i] = tmp;
                pre2[j][i + 1] = pre2[j][i] + tmp;
            }

            v = arr[i];
            for (int j = 0; j < m1; j++) {
                int p = facs1.get(j)[0];
                int tmp = 0;
                while (v % p == 0) {
                    v /= p;
                    tmp++;
                }
//                brr1[j][i] = tmp;
                pre1[j][i + 1] = pre1[j][i] + tmp;
            }
        }

        long res = 0;
        int k1 = 0, k2 = 0;
        for (int k3 = 0; k3 < n; k3++) {

            // 找到不满足的点为止
            while (k1 <= k3 && check(pre1, k1, k3, facs1)) {
                k1++;
            }

            //
            while (k2 <= k3 && check(pre2, k2, k3, facs2)) {
                k2++;
            }

//            res += Math.min(k1, k2);
            // 0 - k1 - 1
            // k2 -> n

            res += (k2 <= k1 - 1) ? (k1 - k2): 0;
        }

        System.out.println(res);
    }

    static
    class AReader {
        private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        private StringTokenizer tokenizer = new StringTokenizer("");
        private String innerNextLine() {
            try {
                return reader.readLine();
            } catch (IOException ex) {
                return null;
            }
        }
        public boolean hasNext() {
            while (!tokenizer.hasMoreTokens()) {
                String nextLine = innerNextLine();
                if (nextLine == null) {
                    return false;
                }
                tokenizer = new StringTokenizer(nextLine);
            }
            return true;
        }
        public String nextLine() {
            tokenizer = new StringTokenizer("");
            return innerNextLine();
        }
        public String next() {
            hasNext();
            return tokenizer.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

//        public BigInteger nextBigInt() {
//            return new BigInteger(next());
//        }
        // 若需要nextDouble等方法，请自行调用Double.parseDouble包装
    }

}

写在最后

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/319167.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

二分图最大匹配——匈牙利算法详解

二分图最大匹配——匈牙利算法详解

文章目录 零、前言一、红娘牵线二、二分图最大匹配2.1概念2.2交替路2.3增广路2.4匈牙利算法2.4.1算法原理2.4.2算法示例2.4.3代码实现 3.OJ练习3.1模板3.2棋盘覆盖3.3車的放置 零、前言 关于二分图的基本知识见&#xff1a;二分图及染色法判定 一、红娘牵线 一位红娘近日遇到一…
阅读更多...
Word插件-大珩助手-手写电子签名

Word插件-大珩助手-手写电子签名

手写签名 支持鼠标写&#xff0c;支持触摸屏写&#xff0c;点击画笔按钮切换橡皮擦&#xff0c;支持清空画板重写&#xff0c;点击在word中插入签名&#xff0c;可插入背景透明的签字图 素材库-保存签名 将写好的签字图复制粘贴到素材库中&#xff0c;以便永久使用&#xff…
阅读更多...
详解Java之Spring框架中事务管理的艺术

详解Java之Spring框架中事务管理的艺术

第1章&#xff1a;引言 大家好&#xff0c;我是小黑&#xff0c;咱们今天聊聊Spring框架中的事务管理。不管是开发小型应用还是大型企业级应用&#xff0c;事务管理都是个不可避免的话题。那么&#xff0c;为什么事务管理这么重要呢&#xff1f;假设在银行系统中转账时&#x…
阅读更多...
OpenCV——多分辨率LBP的计算方法

OpenCV——多分辨率LBP的计算方法

目录 一、算法原理1、原理概述2、参考文献 二、代码实现三、结果展示 OpenCV——多分辨率LBP的计算方法由CSDN点云侠原创&#xff0c;爬虫自重。如果你不是在点云侠的博客中看到该文章&#xff0c;那么此处便是不要脸的爬虫。 一、算法原理 1、原理概述 基本LBP算子虽然在早期…
阅读更多...
Qt/QML编程学习之心得：使用camera摄像头（35）

Qt/QML编程学习之心得：使用camera摄像头（35）

汽车应用中，camera起到了越来越多的作用，数字化的作用，这点无可争议，而作为GUI设计工具，如何让Camera类的应用能更好的发挥作用呢？ You can use Camera to capture images and movies from a camera, and manipulate the capture and processing settings that get appl…
阅读更多...
关于 setData 同步异步的问题

关于 setData 同步异步的问题

小程序官方文档中的回答解释: 所以大概意思就是: 1.setData在逻辑层的操作是同步&#xff0c;因此this.data中的相关数据会立即更新,比如下面的例子: const a 1 this.setData({b: a ? a : , }) console.log(that.data.b) // 1 2. setData在视图层的操作是异步&#xff0c;…
阅读更多...
Linux Ubuntu搭建我的世界Minecraft服务器实现好友远程联机MC游戏

Linux Ubuntu搭建我的世界Minecraft服务器实现好友远程联机MC游戏

文章目录 前言1. 安装JAVA2. MCSManager安装3.局域网访问MCSM4.创建我的世界服务器5.局域网联机测试6.安装cpolar内网穿透7. 配置公网访问地址8.远程联机测试9. 配置固定远程联机端口地址9.1 保留一个固定tcp地址9.2 配置固定公网TCP地址9.3 使用固定公网地址远程联机 前言 Li…
阅读更多...
C语言之从浅入深一步一步全方位理解指针【附笔试题】

C语言之从浅入深一步一步全方位理解指针【附笔试题】

文章目录 前言从浅入深理解指针《第一阶段》一、内存和地址1.1 内存1.2 究竟该如何理解编址 二、指针变量和地址2.1 取地址操作符&#xff08;&&#xff09; 三、指针变量和解引用操作符&#xff08;*&#xff09;3.1 指针变量3.2 如何拆解指针类型3.3 解引用操作符 四、指…
阅读更多...
web网页设计学习记录（五）

web网页设计学习记录（五）

1.如何设置背景色呢&#xff1f; 格式为&#xff1a; <body bgcolor"色彩值"> “色彩值”可以为色彩的英文名或相应十六进制值。 2.如何将图片作为背景呢&#xff1f; 格式为&#xff1a;<body background"图片文件名"> 使用<body&g…
阅读更多...
具于xilinx FPGA的可动态配置DDS频率控制字的DDS IP核使用例程详解

具于xilinx FPGA的可动态配置DDS频率控制字的DDS IP核使用例程详解

目录 1 概述2 IP examples功能3 IP 使用例程4注意事项5 DDS IP Examples下载位置 1 概述 本文用于讲解xilinx IP 的dds ip examples&#xff08;动态配置频率&#xff09;的功能说明&#xff0c;方便使用者快速上手。 2 IP examples功能 本examples 是月隐编写的针对DDS的使…
阅读更多...
一分钟找到所有的中文核心期刊

一分钟找到所有的中文核心期刊

1.进入中国知网找到出版物检索 2.在出版来源导航这里选择期刊导航 3.右边拉到底选择核心期刊导航 4.选择自己专业的期刊即可
阅读更多...
软件设计不是CRUD（10）：低耦合模块设计理论——业务抽象：从需求中提取业务维度

软件设计不是CRUD（10）：低耦合模块设计理论——业务抽象：从需求中提取业务维度

接上文《软件设计不是CRUD（9）：低耦合模块设计理论——设计落地所面临的挑战》 2、什么是业务抽象 业务抽象是一种将需求落地成模块功能的设计思想，是对业务需求和技术设计进行转换、隔离的一种分析方法。经过业务抽象后的业务模块一般具有较高的业务屈服度，能更大程度满…
阅读更多...
Hex Editor的使用教程（VS Code）

Hex Editor的使用教程（VS Code）

Hex Editor&#xff08;十六进制编辑器&#xff09;是一种用于查看和编辑计算机文件的低级别编辑工具。与常规文本编辑器不同&#xff0c;它允许用户直接查看和修改文件的二进制数据。在 Hex Editor 中&#xff0c;数据通常以十六进制&#xff08;hex&#xff09;格式显示&…
阅读更多...
Arduino| IDE下载、安装和设置以及开发板的连接

Arduino| IDE下载、安装和设置以及开发板的连接

IDE下载、安装和设置以及开发板的连接 IDE下载IDE安装IDE设置首选项——设置语言、字体、主题、地址等等开发板管理器——添加开发板 开发板的连接 IDE下载 第一步&#xff1a;进入Arduino官网https://www.arduino.cc。 第二步&#xff1a;选择导航栏的Software&#xff0c;然…
阅读更多...
【论文阅读笔记】Prompt Tuning for Parameter-efficient Medical Image Segmentation

【论文阅读笔记】Prompt Tuning for Parameter-efficient Medical Image Segmentation

Fischer M, Bartler A, Yang B. Prompt tuning for parameter-efficient medical image segmentation[J]. Medical Image Analysis, 2024, 91: 103024. 【开源】 【核心思想】 本文的核心思想是提出了一种用于医学图像分割的参数高效的提示调整&#xff08;Prompt Tuning&…
阅读更多...
Flutter开发进阶之动画

Flutter开发进阶之动画

Flutter开发进阶之动画 在Flutter中&#xff0c;动画是至关重要的一个部分&#xff0c;它能够为应用程序提供更加丰富和生动的用户体验&#xff0c;Flutter中的动画系统是UI框架的核心功能之一&#xff0c;也是开发者学习Flutter框架的重要部分&#xff0c;由于动画原理在所有…
阅读更多...
实时时钟芯片DS1302单片机C语言驱动程序

实时时钟芯片DS1302单片机C语言驱动程序

实时时钟RTC相关索引 1.单片机RTC及时钟芯片的时间到底从哪一年起始&#xff1f; 2.STM32F103单片机内部RTC实时时钟驱动程序 3.实时时钟芯片DS1302单片机C语言驱动程序 一、DS1302简介 DS1302 是 DALLAS&#xff08;达拉斯&#xff09;公司推出的一款涓流充电时钟芯片。 主…
阅读更多...
Aigtek超声功率放大器的选型技巧及参数指标有哪些

Aigtek超声功率放大器的选型技巧及参数指标有哪些

超声功率放大器是一种广泛应用于声学测量、医疗成像、声纳等领域的装置&#xff0c;其作用是将输入信号的功率放大到需要的水平。在选型超声功率放大器时&#xff0c;需要考虑一些关键的技巧和参数指标&#xff0c;以确保选择合适的设备来满足特定的需求。 首先&#xff0c;需要…
阅读更多...
【java八股文】之Spring系列篇

【java八股文】之Spring系列篇

1、你怎么理解Spring&#xff1f; Spring是个轻量级的框架&#xff0c;简化了应用的开发程序&#xff0c;提高开发人员的系统维护性&#xff0c;不过配置消息比较繁琐&#xff0c;所以后面才出选了SpringBoot的框架。 Spring的核心组件 &#xff1a; Spring Core 、 Spring Con…
阅读更多...
【Python数据可视化】matplotlib之设置子图：绘制子图、子图共享x轴坐标

【Python数据可视化】matplotlib之设置子图：绘制子图、子图共享x轴坐标

文章传送门 Python 数据可视化matplotlib之绘制常用图形&#xff1a;折线图、柱状图&#xff08;条形图&#xff09;、饼图和直方图matplotlib之设置坐标&#xff1a;添加坐标轴名字、设置坐标范围、设置主次刻度、坐标轴文字旋转并标出坐标值matplotlib之增加图形内容&#x…
阅读更多...
最新文章

Copyright @ 2022~2023