C/C++蓝桥杯算法真题打卡(Day4)
一、P11041 [蓝桥杯 2024 省 Java B] 报数游戏 - 洛谷
算法代码:
#include<bits/stdc++.h>
using namespace std;// 计算第 n 个满足条件的数
long long findNthNumber(long long n) {long long low = 1, high = 1e18; // 二分查找范围while (low < high) {long long mid = (low + high) / 2;// 计算 mid 以内 20 或 24 的倍数的个数long long count = mid / 20 + mid / 24 - mid / 120;if (count < n) {low = mid + 1;} else {high = mid;}}return low;
}int main() {long long n = 202420242024;long long result = findNthNumber(n);cout << result << endl;return 0;
}
代码说明
-
二分查找:
-
通过二分查找确定第 n 个满足条件的数。
-
查找范围从 1 到 1e18(足够大的数)。
-
-
容斥原理:
-
mid / 20
:计算 mid 以内 20 的倍数的个数。 -
mid / 24
:计算 mid 以内 24 的倍数的个数。 -
mid / 120
:减去 20 和 24 的最小公倍数的个数(避免重复计算)。
-
-
时间复杂度:
-
二分查找的时间复杂度为 O(log N),效率非常高。
-
二、P8792 [蓝桥杯 2022 国 A] 最大公约数 - 洛谷
算法代码:
#include<bits/stdc++.h>
#define int long long
#define lc 2*k
#define rc 2*k+1
using namespace std;
int n,a[1234567],cnt;
struct nord{int l,r,mx;
}t[1234567];
void build(int k,int l,int r){//建树t[k].l=l,t[k].r=r;if (l==r){t[k].mx=a[l];return ;}int mid=(l+r)/2;build(lc,l,mid);build(rc,mid+1,r);t[k].mx=__gcd(t[lc].mx,t[rc].mx);
}
int ask(int k,int l,int r){//求区间gcdif (l<=t[k].l&&r>=t[k].r) return t[k].mx;int ans=0;int mid=(t[k].l+t[k].r)/2;if (l<=mid) ans=__gcd(ans,ask(lc,l,r));if (r>mid) ans=__gcd(ans,ask(rc,l,r));return ans;
}
main(){cin>>n;for (int i=1;i<=n;i++) cin>>a[i],cnt+=(a[i]==1?1:0);build(1,1,n);if (cnt){//特殊情况cout <<n-cnt;return 0;}int ans=1e9;int i=1;for (int j=1;j<=n;j++){//枚举while (i<j&&ask(1,i+1,j)==1) i++;//一直往前走if (ask(1,i,j)==1) ans=min(ans,j-i);//成功了}if (ans==1e9) cout <<-1;//不合法else cout <<n+ans-1;return 0;
}
这段代码的主要功能是解决一个与区间 GCD(最大公约数)相关的问题。以下是代码的思路和逻辑分析:
代码思路
1. 问题描述
-
给定一个长度为
n
的数组a
。 -
目标是找到一个最短的区间
[i, j]
,使得该区间内所有元素的 GCD 为 1。 -
如果存在这样的区间,输出将整个数组变为全 1 的最小操作次数;否则输出 -1。
2. 核心逻辑
-
特殊情况处理:
-
如果数组中已经有
cnt
个 1,则直接输出n - cnt
,因为只需要将其他元素变为 1 即可。
-
-
区间 GCD 计算:
-
使用线段树维护区间 GCD,支持快速查询任意区间的 GCD。
-
-
滑动窗口枚举:
-
使用双指针
i
和j
枚举区间[i, j]
。 -
如果区间
[i, j]
的 GCD 为 1,则尝试缩小窗口(移动i
)以找到更短的区间。 -
记录满足条件的最短区间长度。
-
-
结果计算:
-
如果找到满足条件的区间,输出
n + ans - 1
(将整个数组变为全 1 的最小操作次数)。 -
否则输出 -1。
-
代码逻辑分析
1. 线段树构建
-
build
函数用于构建线段树,每个节点存储区间的左右边界和区间 GCD。 -
递归地将数组划分为左右子区间,直到区间长度为 1。
-
区间 GCD 通过
__gcd
函数计算。
2. 区间 GCD 查询
-
ask
函数用于查询区间[l, r]
的 GCD。 -
如果当前节点区间完全包含在查询区间内,则直接返回节点值。
-
否则递归查询左右子区间,并计算 GCD。
3. 滑动窗口枚举
-
使用双指针
i
和j
枚举区间。 -
如果区间
[i, j]
的 GCD 为 1,则尝试缩小窗口(移动i
)。 -
记录满足条件的最短区间长度
ans
。
4. 结果计算
-
如果找到满足条件的区间,输出
n + ans - 1
。 -
否则输出 -1。
代码优化建议
-
变量命名:
-
变量名如
lc
、rc
、nord
等不够直观,建议改为更具描述性的名称,如left_child
、right_child
、Node
等。
-
-
代码可读性:
-
添加注释,解释关键逻辑和变量的含义。
-
使用空格和换行符提高代码的可读性。
-
-
边界条件处理:
-
确保数组下标从 1 开始,避免越界问题。
-
在滑动窗口枚举时,注意
i
和j
的移动条件。
-
-
时间复杂度:
-
线段树构建的时间复杂度为 O(n)。
-
区间查询的时间复杂度为 O(log n)。
-
滑动窗口枚举的时间复杂度为 O(n log n)。
-
总体时间复杂度为 O(n log n),效率较高。
-
修正后的代码
#include<bits/stdc++.h>
#define int long long
using namespace std;const int MAXN = 1234567;
int n, a[MAXN], cnt;struct Node {int l, r, mx;
} t[MAXN * 4];// 构建线段树
void build(int k, int l, int r) {t[k].l = l, t[k].r = r;if (l == r) {t[k].mx = a[l];return;}int mid = (l + r) / 2;build(2 * k, l, mid);build(2 * k + 1, mid + 1, r);t[k].mx = __gcd(t[2 * k].mx, t[2 * k + 1].mx);
}// 查询区间 GCD
int ask(int k, int l, int r) {if (l <= t[k].l && r >= t[k].r) return t[k].mx;int ans = 0;int mid = (t[k].l + t[k].r) / 2;if (l <= mid) ans = __gcd(ans, ask(2 * k, l, r));if (r > mid) ans = __gcd(ans, ask(2 * k + 1, l, r));return ans;
}signed main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];cnt += (a[i] == 1 ? 1 : 0);}build(1, 1, n);// 特殊情况:数组中已经有 1if (cnt) {cout << n - cnt << endl;return 0;}int ans = 1e9;int i = 1;// 滑动窗口枚举for (int j = 1; j <= n; j++) {while (i < j && ask(1, i + 1, j) == 1) i++;if (ask(1, i, j) == 1) ans = min(ans, j - i + 1);}// 输出结果if (ans == 1e9) cout << -1 << endl;else cout << n + ans - 1 << endl;return 0;
}
总结
这段代码通过线段树和滑动窗口的结合,高效地解决了区间 GCD 问题。修正后的代码提高了可读性和健壮性,同时保留了原有的高效逻辑。
相关文章:
C/C++蓝桥杯算法真题打卡(Day4)
一、P11041 [蓝桥杯 2024 省 Java B] 报数游戏 - 洛谷 算法代码: #include<bits/stdc.h> using namespace std;// 计算第 n 个满足条件的数 long long findNthNumber(long long n) {long long low 1, high 1e18; // 二分查找范围while (low < high) {lo…...
TinyWebServer项目笔记——01 线程同步机制封装类
目录 1.基础知识 (1)RALL (2)信号量 (3)互斥量 (4)条件变量 2.功能 1.基础知识 (1)RALL RALL全称“Resource Acquisition is Initialization”…...
如何在Ubuntu上直接编译Apache Doris
以下是在 Ubuntu 22.04 上直接编译 Apache Doris 的完整流程,综合多个版本和环境的最佳实践: 注意:Ubuntu的数据盘VMware默认是20G,编译不够用,给到50G以上吧 一、环境准备 1. 安装系统依赖 # 基础构建工具链 apt i…...
算法006——和为S 的两个数
力扣——查找总价格为目标值的两个商品点击跳转 注意题目中的关键信息升序 我们利用双指针,不管 target 是多少,让一个指针指向最小值,让一个指针指向最大 那么,共有三种情况 我们首先遇到的是第二种情况 sum < target left …...
物联网设备接入系统后如何查看硬件实时数据?
要在软件中实时查看硬件设备的信息,通常需要结合前后端技术来实现。以下是设计思路和实现步骤: 1. 系统架构设计 实时查看硬件设备信息的系统通常采用以下架构: 数据采集层: 硬件设备通过传感器采集数据,发送到InfluxDB。数据存…...
CSS—属性继承与预处理器:2分钟掌握预处理器
个人博客:haichenyi.com。感谢关注 1. 目录 1–目录2–属性继承3–预处理器 2. 属性继承 像Android里面继承extends,类继承,子类可以使用父类的public和protected的属性和方法。子类可以直接用。 在CSS里面也是类似的。CSS里面是布局里面…...
前端知识点---http.createHttp()的理解(arkts)
通俗易懂的例子:点外卖 🍔🥤 想象一下,你在家里点外卖,HTTP 请求就像是你和餐厅之间的沟通方式。 1️⃣ 没有 http.createHttp():每次点餐都重新拨电话 📞 如果你每次点餐都重新拨打餐厅的电话…...
信息安全访问控制、抗攻击技术、安全体系和评估(高软42)
系列文章目录 信息安全访问控制、抗攻击技术、安全体系和评估 文章目录 系列文章目录前言一、信息安全技术1.访问控制2.抗攻击技术 二、欺骗技术1.ARP欺骗2.DNS欺骗3.IP欺骗 三、抗攻击技术1.端口扫描2.强化TCP/IP堆栈 四、保证体系和评估1.保证体系2.安全风险管理 五、真题在…...
【深度学习】宠物品种分类Pet Breeds Classifier
文章目录 宠物品种数据集制作宠物品种标签图像预处理Presizing 损失函数loss观察模型的性能提升模型的性能learning rate finder使用CLR算法训练选择学习率的策略重新训练 迁移学习微调fine_tunefit_one_cycle有判别力的学习率 选择epoch的数量更深的网络架构 宠物品种数据集 …...
PyQt组件间的通信方式
PyQt组件间的通信方式 PyQt组件间的通信方式 1. 组件介绍 1.1 组件的定义1.2 组件的分类 2. 组件的通信方式 2.1 信号与槽(Signal & Slot) 1. 组件介绍 在 Qt 框架中,组件(Component)是构建图形用户界面&am…...
基于编译器特性浅析C++程序性能优化
最近在恶补计算机基础知识,学到CSAPP第五章的内容,在这里总结并且展开一下C程序性能优化相关的内容。 衡量程序性能的方式 一般而言,程序的性能可以用CPE(Cycles Per Element)来衡量,其指的是处理每个元素…...
在 Docker 中搭建GBase 8s主备集群环境
本文介绍了如何在同一台机器上使用 Docker 容器搭建GBase 8s主备集群环境。 拉取镜像 拉取GBase 8s的最新镜像 docker pull liaosnet/gbase8s或者docker pull liaosnet/gbase8s:v8.8_3513x25_csdk_x64注:在tag为v8.8_3513x25_csdk_x64及之后的版本中,…...
hadoop集群环境配置
目录 VMware虚拟机安装 Xshell安装 网络问题 centos7下载 ---------参考以下视频步骤进行生态搭建---------- 搭建好hadoop01 克隆出hadoop02、hadoop03 启动三台虚拟机 打开终端 输入 记录下各个ip 打开Xshell,新建会话 修改主机名 配置静态IP 主机名称…...
Hive-优化(参数优化篇)
map 数和reduce数 控制hive任务中的map数 合适的map数,会让资源分配的更平均,让我们的代码运行更快,通常情况下,作业会通过input的目录产生一个或者多个map任务。我们可以通过调整参数来控制运行过程中的map数。 Hive Map的数量…...
深度学习|MAE技术全景图:自监督学习的“掩码魔法“如何重塑AI基础
一、引言:深度学习的困境与自监督的曙光 深度学习(Deep Learning)无疑是当今人工智能领域基础中的基础。从图像识别到自然语言处理(NLP),它在无数任务中展现了卓越性能。例如,在安防监控中&…...
学习threejs,使用LineBasicMaterial基础线材质
👨⚕️ 主页: gis分享者 👨⚕️ 感谢各位大佬 点赞👍 收藏⭐ 留言📝 加关注✅! 👨⚕️ 收录于专栏:threejs gis工程师 文章目录 一、🍀前言1.1 ☘️THREE.LineBasicMaterial1.…...
第本章:go 切片
注意: 切片必须要初始化 才能使用 ,切片是引用类型 a :[]int{} // 这上叫始化 此时并没有申请内存 // 如果要追加值的话: append ints : append(a, 1, 2, 3)a : make([]int,5) // 声明切片类型var a []string //声明一…...
dify + ollama + deepseek-r1+ stable-diffusion 构建绘画智能体
故事背景 stable-diffusion 集成进 dify 后,我们搭建一个小智能体,验证下文生图功能 业务流程 #mermaid-svg-6nSwwp69eMizP6bt {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-6nSwwp69eMiz…...
Java基础面试题全集
1. Java语言基础 1.1 Java是什么? • Java是一种广泛使用的编程语言,最初由Sun Microsystems(现为Oracle公司的一部分)于1995年发布。它是一种面向对象的、基于类的、通用型的编程语言,旨在让应用程序“编写一次&…...
基于multisim的自动干手器设计与仿真
1 设计的任务与要求 设计一个输出 5V 的直流稳压电源。用开关的闭合模拟手挡住光线的功能。用灯的亮灭模拟烘干吹风功能。 2 方案论证与选择 2.1 自动干手器的系统方案 本设计由5V直流电源、红外发射电路、红外接收电路、灯模拟电路构成。 1. 5V直流电源系统 这一部分是整…...
three.js 在 webGL 添加纹理
在我们生成了3D设计之后,我们可以添加纹理使其更加吸引人。在 webGL 和 p5.js中,可以使用 gl.texImage2D() 和 texture() API来为形状应用纹理。 使用 webGL 在 webGL 中,gl.texImage2D() 函数用于从图像文件生成2D纹理。该函数接受许多参…...
Docker 部署 MongoDB 并持久化数据
Docker 部署 MongoDB 并持久化数据 在现代开发中,MongoDB 作为 NoSQL 数据库广泛应用,而 Docker 则提供了高效的容器化方案。本教程将介绍如何使用 Docker 快速部署 MongoDB,并实现数据持久化,确保数据不会因容器重启或删除而丢失…...
SpringBoot优雅关机,监听关机事件,docker配置
Spring Boot 提供了多种方法来实现优雅停机(Graceful Shutdown),这意味着在关闭应用程序之前,它会等待当前正在处理的请求完成,并且不再接受新的请求。 一、优雅停机的基本概念 优雅停机的主要步骤如下: …...
网络基础(一)【网络发展/认识协议/网络 VS 系统/以太网通信原理/重谈协议/网络中的地址管理】
网络基础(一) 1. 网络的发展2. 认识协议3. 网络 VS 系统4. 以太网通信原理5. 重谈协议6. 网络中的地址管理 1. 网络的发展 最开始时,计算机之间相互独立。 但是为了协作完成一些任务,就产生了计算机之间相互通讯的需求,…...
PostgreSQL、SQL Server和MySQL数据库性能调优与故障排除技术
通过结合具体技术特性与工具链的深度使用,可系统化提升数据库性能和稳定性。建议根据实际负载特征制定监控-分析-优化的闭环管理流程。 数据库技术: PostgreSQL 13:逻辑复制、分区表、并行查询、监控工具(如pg_stat_statements、…...
本地YARN集群部署
请先完成HDFS的前置部署,部署方式可查看:本地部署HDFS集群https://blog.csdn.net/m0_73641796/article/details/145998092?spm1001.2014.3001.5502 部署说明 组件配置文件启动进程备注Hadoop HDFS需修改 需启动: NameNode作为主节点 DataNode作为从节点 Secondary…...
Redis数据结构——list
目录 列表命令 lpush lrange lpushx rpush rpushx lpop rpop lindex linsert llen lrem ltrim lset blpop / brpop 命令总结 编码方式 list相当于数组或者顺序表,但并不是简单的数组,更接近于C中的"双端队列"(deque)。 最左侧的下标…...
World of Warcraft [CLASSIC] BigFoot BiaoGe
World of Warcraft [CLASSIC] BigFoot BiaoGe 金团表格插件 设置60秒拍卖装备时间 ALT 鼠标左键,点击装备,弹出对话框,填写 1)拍卖时间默认60秒,起拍价, 2)点击【开始拍卖】 团队所有安装了…...
CentOS Docker 安装指南
CentOS Docker 安装指南 引言 Docker 是一个开源的应用容器引擎,它允许开发者打包他们的应用以及应用的依赖包到一个可移植的容器中,然后发布到任何流行的 Linux 机器上,也可以实现虚拟化。Docker 容器是完全使用沙箱机制,相互之…...
PHP:phpstudy无法启动MySQL服务问题解决
文章目录 一、问题说明二、解决问题 一、问题说明 我的Windows10系统,之前安装过MySQL5.7的版本。 然后,用phpstudy安装MySQL8,并启动MySQL8。 发生无法启动的情况。 二、解决问题 1、删除本地MySQL7的服务 net stop MySQL //这里的服务名…...
【电控笔记z29】扰动估测器DOB估测惯量J-摩擦系数B
基本原理 扰动估测器的核心思想是通过向电机系统施加特定的扰动信号,观察系统响应的变化,然后利用系统的动态模型和控制理论来估计未知参数,如惯量和摩擦系数 。一般基于电机的运动方程建立数学模型,结合观测到的电机实际运行数据…...
STM32-I2C通信外设
目录 一:I2C外设简介 二:I2C外设数据收发 三:I2C的复用端口 四:主机发送和接收 五:硬件I2C读写MPU6050 相关函数: 1.I2C_ GenerateSTART 2.I2C_ GenerateSTOP 3.I2C_ AcknowledgeConfig 4.I2C…...
计算机二级MS之PPT
声明:跟着大猫和小黑学习随便记下一些笔记供大家参考,二级考试之前将持续更新,希望大家二级都能轻轻松松过啦,过了二级的大神也可以在评论区留言给点建议,感谢大家!! 文章目录 考题难点1cm25px…...
Spring Boot 3 整合 MinIO 实现分布式文件存储
引言 文件存储已成为一个做任何应用都不可回避的需求。传统的单机文件存储方案在面对大规模数据和高并发访问时往往力不从心,而分布式文件存储系统则提供了更好的解决方案。本篇文章我将基于Spring Boot 3 为大家讲解如何基于MinIO来实现分布式文件存储。 分布式存…...
C++ Primer 交换操作
欢迎阅读我的 【CPrimer】专栏 专栏简介:本专栏主要面向C初学者,解释C的一些基本概念和基础语言特性,涉及C标准库的用法,面向对象特性,泛型特性高级用法。通过使用标准库中定义的抽象设施,使你更加适应高级…...
分布式中间件:Redis介绍
目录 Redis 概述 Redis 的特点 高性能 丰富的数据结构 持久化 分布式特性 简单易用 Redis 的数据结构 字符串(String) 哈希(Hash) 列表(List) 集合(Set) 有序集合&…...
软件测试的基础入门(二)
文章目录 一、软件(开发)的生命周期什么是生命周期软件(开发)的生命周期需求分析计划设计编码测试运行维护 二、常见的开发模型瀑布模型流程优点缺点适应的场景 螺旋模型流程优点缺点适应的场景 增量模型和迭代模型流程适应的场景…...
学之思社区版考试系统docker-compose部署
参考 开源项目-Docker部署学之思管理系统 安装docker sudo yum remove docker docker-client docker-client-latest docker-common docker-latest docker-latest-logrotate docker-logrotate docker-engine mv /etc/yum.repos.d/CentOS-Base.repo /etc/yum.repos.d/CentOS-Bas…...
深度优先搜索(DFS)和广度优先搜索(BFS)——c#实现
一、深度优先搜索(DFS) 原理: 沿着分支尽可能深入,直到到达叶子节点,然后回溯探索其他分支 类似走迷宫时优先选择一条路走到黑,碰壁再回退 数据结构:栈(Stack)或递归实…...
什么是hive
Apache Hive 是一个基于 Hadoop 生态系统构建的数据仓库工具,主要用于处理和分析大规模的结构化数据。它允许用户通过类似 SQL 的查询语言(HiveQL)进行数据操作,而无需直接编写复杂的 MapReduce 程序。以下是 Hive 的核心特点和应…...
JVM详解
目录 一.JVM的概念 1. 什么是JVM? 2.JVM用来干什么? 二JVM运行流程 JVM执⾏流程 2.1类加载机制 2.2类加载机制带来了哪些好处? 2.3类加载的过程是什么? 2.3.1加载 2.3.2验证 2.3.3准备阶段 2.3.4解析阶段 符号引⽤ 直接引⽤ 2.3.5初始化阶段 2.4类加载器 什么…...
PCA(主成分分析)核心原理
一、PCA(主成分分析)核心原理 即主成分分析技术,又称主分量分析技术,旨在利用降维的思想,把多指标转化为少数几个综合指标。在统计学中,主成分分析PCA是一种简化数据集的技术。它是一个线性变换。这个变换…...
DeepSeek私有化部署6:openEuler 24.03-LTS-SP1安装Open WebUI
Open WebUI是一个 Open WebUI 是一个可扩展的、功能丰富、用户友好的自托管 AI 平台,专为完全离线运行而设计。 它支持多种 LLM 运行环境,包括 Ollama 和 OpenAI 兼容的 API,并内置了用于 RAG 的推理引擎,是一个强大的 AI 部署解决…...
【一文学会 HTML5】
目录 HTML概述基本概念HTML 发展历程HTML 基本结构 网页基本标签标题标签(<h1> - <h6>)段落标签(<p>)换行标签(<br>)水平线标签(<hr>)注释࿰…...
前端题目类型
HTMLCSS常见面试题 HTML标签有哪些行内元素 img、picture、span、input、textarea、select、label 说说你对元素语义化的理解 元素语义化就是用正确的元素做正确的事情。虽然理论上所有html元素都可通过css样式实现相同效果,但这样会使事情复杂化,所以需…...
nodejs学习——nodejs和npm安装与系统环境变量配置及国内加速
nodejs和npm安装与系统环境变量配置及国内加速 下载node-v22.14.0-x64.msi 建议修改为非C盘文件夹 其它步骤,下一步,下一步,完成。 打开CMD窗口查看安装详情 $ node -v v22.14.0 $ npm -v 10.9.2$ npm config list创建node_global和node_c…...
[视频编码]rkmpp 实现硬件编码
mpi_enc_test的命令参数描述说明 命令参数的描述说明如下: 命令参数 描述说明 -i 输入的图像文件。 -o 输出的码流文件。 -w 图像宽度,单位为像素。 -h 图像高度,单位为像素。 -hstride 垂直方向相邻两行之间的距离,单…...
Vue3实战学习(Vue3的基础语法学习与使用(超详细))(3)
目录 (1)Vue3工程环境准备、项目基础脚手架搭建详细教程。(博客链接) (2)Vue3的基础语法学习与使用。 (1)"{{}}"绑定数据。 <1>ref()函数定义变量——绑定数据。 <2>reactive({...})…...
基于multisim的花样彩灯循环控制电路设计与仿真
1 课程设计的任务与要求 (一)、设计内容: 设计一个8路移存型彩灯控制器,基本要求: 1. 8路彩灯能演示至少三种花型(花型自拟); 2. 彩灯用发光二极管LED模拟; 3. 选做…...
EasyRTC嵌入式视频通话SDK的跨平台适配,构建web浏览器、Linux、ARM、安卓等终端的低延迟音视频通信
1、技术背景 WebRTC是一项开源项目,旨在通过简单的API为浏览器和移动应用程序提供实时通信(RTC)功能。它允许在无需安装插件或软件的情况下,实现点对点的音频、视频和数据传输。 WebRTC由三个核心组件构成: GetUserM…...