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

news/2024/2/29 17:38:05/文章来源:https://blog.csdn.net/m0_66102593/article/details/135577857

前言

在这里插入图片描述


整体评价

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.luyixian.cn/news_show_925548.aspx

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

相关文章

order by之后的injection(sqllabs第四十六关)

order by相关注入知识 这一关的sql语句是利用的order by 根据输入的id不同数据排序不一样可以确定就是order by order by后面无法使用ubion注入&#xff08;靠找不到&#xff09; 可以利用后面的参数进行攻击 1&#xff09;数字 没作用考虑布尔类型 rand和select ***都可以 …

neo4j 图数据库 py2neo 操作 示例代码

文章目录 摘要前置NodeMatcher & RelationshipMatcher创建节点查询获取节点节点有则查询&#xff0c;无则创建创建关系查询关系关系有则查询&#xff0c;无则创建 Cypher语句创建节点 摘要 利用py2neo包&#xff0c;实现把excel表里面的数据&#xff0c;插入到neo4j 图数据…

GPT在地学、GIS、气象、农业、生态、环境等领域应用

详情点击链接&#xff1a;GPT在地学、GIS、气象、农业、生态、环境等领域应用 一开启大模型 1 开启大模型 1)大模型的发展历程与最新功能 2)大模型的算法构架与底层逻辑 3)大模型的强大功能与应用场景 4)国内外经典大模型&#xff08;ChatGPT、LLaMA、Gemini、DALLE、Mid…

Excel学习

文章目录 学习链接Excel1. Excel的两种形式2. 常见excel操作工具3.POI1. POI的概述2. POI的应用场景3. 使用1.使用POI创建excel2.创建单元格写入内容3.单元格样式处理4.插入图片5.读取excel并解析图解POI 4. 基于模板输出POI报表5. 自定义POI导出工具类ExcelAttributeExcelExpo…

【Spring Boot】项目端口号冲突解决方法,一步到位

启动项目遇到以下问题&#xff1a; Description: Web server failed to start. Port 8080 was already in use. Action: Identify and stop the process that’s listening on port 8080 or configure this application to listen on another port. Process finished with …

python学习笔记10(选择结构2、循环结构1)

&#xff08;一&#xff09;选择结构2 1、if……else……语句 #&#xff08;1&#xff09;基本格式 numbereval(input("请输入您的6位中奖号码&#xff1a;")) if number123456:print("恭喜您&#xff0c;中奖了") else:print("未中奖")#&…

jupyter notebook 配置conda 虚拟环境python

conda创建python环境 conda create -n openvoice python3.9 激活环境 source activate openvoice 在虚拟环境中安装ipykernel pip install ipykernel 添加虚拟环境进到 jupyter notebook python -m ipykernel install --user --name openvoice --display-name openvoice …

C#,入门教程(15)——类(class)的基础知识

上一篇&#xff1a; C#&#xff0c;入门教程(14)——字符串与其他数据类型的转换https://blog.csdn.net/beijinghorn/article/details/124004562 物以类聚&#xff0c;凡物必类。 类的使用&#xff0c;须遵循几个简单的原则&#xff1a; &#xff08;1&#xff09;能类则类&a…

数字智慧驱动:数据可视化如何助力大企业效率飙升?

在当今信息大爆炸的时代&#xff0c;大型企业面临着前所未有的数据挑战。数据量庞大、多样化的信息汇聚&#xff0c;无疑成为企业高效运营的挑战之一。幸运的是&#xff0c;数据可视化作为一种强大的工具&#xff0c;正成为大型企业提高效率、优化决策的得力助手。 数据可视化首…

IP定位技术在网络安全行业的探索

随着互联网的普及和深入生活&#xff0c;网络安全问题日益受到人们的关注。作为网络安全领域的重要技术&#xff0c;IP定位技术正逐渐成为行业研究的热点。本文将深入探讨IP定位技术在网络安全行业的应用和探索。 一、IP定位技术的概述 IP定位技术是通过IP地址来确定设备地理位…

【Linux】第二十八站:动静态库

文章目录 一、设计静态库1.自己设计一个静态库2.使用一下我们的静态库3.动态链接和静态链接4.得到的一些结论5.可以不用写-I和-L的两种方法 二、设计动态库1.自己设计一个动态库2.使用一下我们的动态库3.得到的结论 三、动态库是怎么被加载的 一、设计静态库 在我们之前提到过…

电脑扩容升级硬盘选1T还是2T

SSD固态有必要升级2TB吗&#xff1f;----------吴中函 某大二学生用的一台笔记本电脑&#xff0c;512GB的硬盘空间已经严重不够用了&#xff0c;想给笔记本扩容升级一下硬盘&#xff1b; 这位学生是学设计专业的、平时也喜欢摄影、电脑里面也装了一些游戏&#xff0c;经常整理、…

C# wpf 实现任意控件(包括窗口)更多调整大小功能

WPF拖动改变大小系列 第一节 Grid内控件拖动调整大小 第二节 Canvas内控件拖动调整大小 第三节 窗口拖动调整大小 第四节 附加属性实现拖动调整大小 第五章 拓展更多调整大小功能&#xff08;本章&#xff09; 文章目录 WPF拖动改变大小系列前言一、添加的功能1、任意控件Drag…

SpringBoot参数校验

介绍 在开发现代应用程序时&#xff0c;数据验证是确保用户输入的正确性和应用程序数据完整性的关键方面。Spring Boot 提供了强大的数据验证机制&#xff0c;使开发者能够轻松地执行验证操作。本文将深入介绍 Spring Boot 中的 Validation&#xff0c;以及如何在应用程序中正…

网络文件共享服务

目录 一、网络文件共享服务原理内容 1.存储类型 2.应用场景 3.总结 二、FTP——文件传输协议 1.工作原理介绍 2.vsftpd软件 2.1使用ftp 2.2延伸——FileZilla 2.3修改默认端口号 2.4主动模式端口 2.5被动模式端口 2.6匿名用户登录 2.7匿名用户上传 2.8匿名用户…

5文件操作

包含头文件<fstream> 操作文件三大类&#xff1a; ofstream : 写文件ifstream &#xff1a;读文件fstream : 读写文件 5.1文本文件 -文件以ascii的形式存储在计算机中 5.1.1写文件 步骤&#xff1a; 包含头文件 #include "fstream"创建流对象 ofs…

Open CASCADE学习|参数化球面的奇异性

参数曲面的奇异性是一个相对复杂的概念&#xff0c;它涉及到参数曲面的几何特性和参数化过程中的一些特殊情况。参数曲面通常用于描述三维空间中的复杂形状&#xff0c;通过参数方程将二维参数域映射到三维空间中。然而&#xff0c;在某些情况下&#xff0c;参数曲面可能会表现…

ssm基于vue的儿童教育网站的设计与实现论文

摘 要 传统信息的管理大部分依赖于管理人员的手工登记与管理&#xff0c;然而&#xff0c;随着近些年信息技术的迅猛发展&#xff0c;让许多比较老套的信息管理模式进行了更新迭代&#xff0c;视频信息因为其管理内容繁杂&#xff0c;管理数量繁多导致手工进行处理不能满足广大…

react 项目结构配置

1 项目整体目录结构的搭建 如下图&#xff1a; 2 重置css样式: normalize.css reset.less ; 第一步 安装 npm i normalize.css 入口文件index.tsx导入&#xff1a;import ‘noremalize.css’ 第二步 创建自己的css样式&#xff1a;在assets文件夹中创建css…

Go 知多少?

作为一名已接触过其他语言的开发&#xff0c;再去学习一门新语言可比之前轻松不少&#xff0c; 语言之间存在很多相似点&#xff0c;但是新语言也有自己的不同点&#xff0c;通常我会先了解它与其他语言常遇到的不同点有哪些&#xff0c; 使自己先能够上手编写基础程序&#…