第 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=j1dp[i1][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=j1(dp[i1][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(nk)


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]);}staticclass 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 -> nres += (k2 <= k1 - 1) ? (k1 - k2): 0;}System.out.println(res);}staticclass 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包装}}

写在最后

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

爬虫案例—抓取豆瓣电影的电影名称、评分、简介、评价人数

爬虫案例—抓取豆瓣电影的电影名称、评分、简介、评价人数 豆瓣电影网址&#xff1a;https://movie.douban.com/top250 主页截图和要抓取的内容如下图&#xff1a; 分析&#xff1a; 第一页的网址&#xff1a;https://movie.douban.com/top250?start0&filter 第二页的…

时间差异导致数据缺失,如何调整Grafana时间与Prometheus保持同步?

Grafana时间如何调快或调慢&#xff1f; 在k8s环境中&#xff0c;常使用prometheusgrafana做监控组件&#xff0c;prometheus负责采集、存储数据&#xff0c;grafana负责监控数据的可视化。 在实际的使用中&#xff0c;有时会遇到这样的问题&#xff0c;k8s集群中的时间比真实…

unity C#中使用ref、out区别和使用案例

文章目录 ref 关键字out 关键字 在Unity&#xff08;以及C#编程语言中&#xff09;&#xff0c; ref 和 out 都是用来传递参数的引用&#xff0c;这意味着它们允许函数修改实参变量&#xff0c;并且这些修改会反映到调用函数的地方。但它们之间确实存在一些关键区别和使用场景…

【数据结构 | 直接选择排序】

直接选择排序 基本思路直接插入排序SelectSort 基本思路 直接插入排序&#xff08;StraightInsertionSort&#xff09;的基本操作是将一个记录插入到已经排好序的有序表中&#xff0c;从而得到一个新的、记录数增1的有序表。 我们可以同时从数组的头部和尾部同时进行排序工作…

Jenkins集成Sonar Qube

下载插件 重启Jenkins 容器 sonarqube 使用令牌 Jenkins 配置 重新构建

智能合约笔记

前言&#xff1a; 首先了解下为什么会出现智能合约&#xff0c;打个比方现在有两个人A和B打赌明天会不会下雨&#xff0c;每个人赌注100元&#xff0c;如果第二天下雨则A拿走200元&#xff0c;否则B拿走200元&#xff0c;这样就有一个问题&#xff0c;赌注要到第二天才能见效&…

每日一题——LeetCode1189.气球的最大数量

方法一 个人方法&#xff1a; 统计text字符串中b、a、l、o、n 这几个字符出现的次数 l和n需要两个才能拼成一个balloon&#xff0c;所以碰到l和o加1&#xff0c;其他字符加2 最后求出出现次数最少的那个字符再除以2就是能拼凑成的单词数量&#xff0c;避免出现小数要使用向下…

MySQL 从零开始:04 增删改查

文章目录 1、准备工作2、insert 增加数据2.1 添加所有列的数据2.2 添加部分列2.3 一次插入多条数据 3、delete 删除记录4、update 更新记录5、select 查询记录5.1 查询所有行所有列5.2 查询指定行的所有列5.3 查询所有行的指定列5.4 查询指定行的指定列 在上一小节中介绍了 MyS…

leetcode第365题:水壶问题

有两个水壶&#xff0c;容量分别为 jug1Capacity 和 jug2Capacity 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 targetCapacity 升。 如果可以得到 targetCapacity 升水&#xff0c;最后请用以上水壶中的一或两个来盛放取得的 targetCapacity 升水。 你可以&a…

C练习——杨辉三角

题目&#xff1a; 打印近似杨辉三角&#xff0c;行数n自选 百度找的杨辉三角&#xff0c;参考一下&#xff1a; 解析&#xff1a; 把它的全部元素左对齐&#xff0c;就可以看成近似杨辉三角的样子 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 …… 每个数等于它上方两数…

第一个 OpenGL 程序:旋转的立方体(VS2022 / MFC)

文章目录 OpenGL API开发环境在 MFC 中使用 OpenGL初始化 OpenGL绘制图形重置视口大小 创建 MFC 对话框项目添加 OpenGL 头文件和库文件初始化 OpenGL画一个正方形OpenGL 坐标系改变默认颜色 重置视口大小绘制立方体使用箭头按键旋转立方体深度测试添加纹理应用纹理换一个纹理 …

随笔03 笔记整理

图源&#xff1a;文心一言 关于我的考研与信息安全类博文整理~&#x1f95d;&#x1f95d; 第1版&#xff1a;整理考研类博文~&#x1f9e9;&#x1f9e9; 第2版&#xff1a;提前列出博文链接&#xff0c;以便小伙伴查阅~&#x1f9e9;&#x1f9e9; 第3版&#xff1a;整理We…

SLF4J Spring Boot日志框架

JAVA日志框架 JAVA有好多优秀的日志框架&#xff0c;比如log4j、log4j2、logback、JUL&#xff08;java.util.logging&#xff09;、JCL&#xff08;JAVA Common Logging&#xff09;等等&#xff0c;logback是后起之秀&#xff0c;是Spring Boot默认日志框架。 今天文章的目…

快速了解——逻辑回归及模型评估方法

一、逻辑回归 应用场景&#xff1a;解决二分类问题 1、sigmoid函数 1. 公式&#xff1a; 2. 作用&#xff1a;把 (-∞&#xff0c;∞) 映射到 (0&#xff0c; 1) 3. 数学性质&#xff1a;单调递增函数&#xff0c;拐点在x0&#xff0c;y0.5的位置 4. 导函数公式&#xff1a;f…

【镜像制作】OS云主机镜像的制作——以H3C为例

一、云主机镜像简介 1&#xff0e;云主机镜像 云主机镜像不同于容器镜像&#xff0c;是一个含有引导分区、操作系统以及必要应用的单一文件&#xff0c;可以理解成是对整个系统安装光盘所有数据的克隆文件。云用户在创建和申请云主机时可通过选择不同的镜像来快速获取相应操作…

一文读懂「Prompt Engineering」提示词工程

在了解提示过程之前&#xff0c;先了解一下什么是提示prompt&#xff0c;见最后附录部分 一、什么是Prompt Engingering&#xff1f; 提示工程&#xff08;Prompt Engingering&#xff09;&#xff0c;也被称为上下文提示&#xff08;In-Context Prompting&#xff09;&#x…

Android的setContentView流程

一.Activity里面的mWindow是啥 在ActivityThread的performLaunchActivity方法里面&#xff1a; private Activity performLaunchActivity(ActivityClientRecord r, Intent customIntent) {ActivityInfo aInfo r.activityInfo;if (r.packageInfo null) {r.packageInfo getP…

常见面试题之CSS

CSS3的新特性 新增选择器&#xff1a;:nth-child()、:first-of-type、:last-of-type等 弹性盒子&#xff1a;display: flex 媒体查询&#xff1a;media根据设备的特性和屏幕大小应用不同的样式规则 多列布局&#xff1a;column-count和column-with等属性可以实现将内容分为多…

SpringBoot读取配置文件中的内容

文章目录 1. 读取配置文件application.yml中内容的方法1.1 Environment1.2 Value注解1.3 ConfigurationProperties 注解1.4 PropertySources 注解&#xff0c;获取自定义配置文件中的内容&#xff0c;yml文件需要自行实现适配器1.5 YamlPropertiesFactoryBean 加载 YAML 文件1.…

缓存和数据库一致性

前言&#xff1a; 项目的难点是如何保证缓存和数据库的一致性。无论我们是先更新数据库&#xff0c;后更新缓存还是先更新数据库&#xff0c;然后删除缓存&#xff0c;在并发场景之下&#xff0c;仍然会存在数据不一致的情况&#xff08;也存在删除失败的情况&#xff0c;删除…