当前位置: 首页 > news >正文

第十三届蓝桥杯真题:x进制减法,数组切分,gcd,青蛙过河

目录

x进制减法

数组切分

gcd

青蛙过河


        

        

x进制减法

其实就是一道观察规律的题。你发现如果a这个位置上的数x,b这个位置上的数是y,那么此位置至少是max(x,y)+1进制。一定要把位置找对啊 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10,mod=1000000007;
int len1,len2;
ll tmp,ans,a[N],b[N],c[N],n;
int main(){cin>>n;cin>>len1;for(int i=len1;i>=1;i--)cin>>a[i];cin>>len2;for(int i=len2;i>=1;i--)cin>>b[i];for(int i=len1;i>=1;i--){c[i]=max(max(a[i]+1,b[i]+1),2*1ll);a[i]=a[i]-b[i];}tmp=1;for(int i=1;i<=len1;i++){ans=(tmp*a[i]+ans)%mod;tmp=(tmp*c[i])%mod;}cout<<ans;return 0;
}
/*错解
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10,mod=1000000007;
int len1,len2;
ll tmp,ans,a[N],b[N],c[N],n;
int main(){cin>>n;cin>>len1;for(int i=1;i<=len1;i++)cin>>a[i];cin>>len2;for(int i=1;i<=len2;i++)cin>>b[i];for(int i=1;i<=len1;i++){c[i]=max(max(a[i]+1,b[i]+1),2*1ll);a[i]=a[i]-b[i];//这个bug我找了两个小时,不能从高位开始减,}tmp=1;for(int i=len1;i>=1;i--){ans=(tmp*a[i]+ans)%mod;tmp=(tmp*c[i])%mod;}
cout<<ans;return 0;
}*/

        

        

数组切分

一道动态规划题,

我们设置f[i]表示从1到i区间的切法。那么可以从任意区间[j,i]转移,只要这个区间[j,i]也是满足题意的就行。那么如果判断[j,i]是否满足题意呢?

首先要注意到题上给出的是连续的的1~n的某个排列,然后我们只需要判断区间的极值和区间长度是否一样就行,如果相等,就说明此区间一定是连续的自然数。 

#include <bits/stdc++.h>
using namespace std;
long long f[10010],mod =1000000007;
int a[10010],n;
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];f[0]=1;for(int i=1;i<=n;i++){int ma=a[i],mi=a[i];for(int j=i;j>=1;j--){ma=max(ma,a[j]);mi=min(mi,a[j]);if(i-j==ma-mi){f[i]=(f[i]+f[j-1])%mod;}}}cout<<f[n];return 0;
}

        

        

gcd

这道题本以为很麻烦,但是做着做着就发现了个不可思议的规律。

观察5和7,它们的最大gcd一定是2,为什么呢?因为你5+k和7+k始终保持差2,所以它们不可能有比2更大的gcd(因为它们两个一定是不等的)

对于一组a和b(假设b大于a),不妨另c=b-a。最终的a+k和b+k一定是差c,而且c必是它们的公因数。所以如果b+k是m*c的话,那么此时a+k必然也是c的倍数(因为它们两个差c啊),所以只需要枚举到b的下一个c的倍数即可,也就是(b/c+1)*c 

验证5和9,它们差值为4,我们枚举到8和12时候发现gcd已经是4了,那么k就确定了

验证2和9,它们差值为7,我们一直枚举到7和14时发现gcd为7,那么此时k也确定了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,s,c;
int main(){cin>>a>>b;c=abs(a-b);if(a>b)swap(a,b);s=b/c;cout<<(s+1)*c-b;return 0;
}

        

        

青蛙过河

二分做法:

我们对跳跃距离二分,然后去判断这个距离能不能跑2x次即可,既然我们都已经确定了区间长度了。

那么不妨我们把这整个长度分成等长的mid区间,只需要保证所有的mid长度区间和都是大于2x的就行。

证明:(我只会反证法)

假设存在一组mid长度的区间和小于2x,那么经过x次来回,必然要经过此区间2x次,所以不成立。故原假设成立。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int s[N];
ll n,x;
bool check(int m){for(int i=1;i+m<=n;i++){if(s[i+m-1]-s[i-1]<2*x) return false;}return true;
}
int main(){cin>>n>>x;int a;for(int i=1;i<n;i++)cin>>a,s[i]=s[i-1]+a;int l=1,r=n;while(l<=r){int mid=(l+r)>>1;if(check(mid)) r=mid-1;else l=mid+1;}cout<<l;return 0;
}

相关文章:

第十三届蓝桥杯真题:x进制减法,数组切分,gcd,青蛙过河

目录 x进制减法 数组切分 gcd 青蛙过河 x进制减法 其实就是一道观察规律的题。你发现如果a这个位置上的数x&#xff0c;b这个位置上的数是y&#xff0c;那么此位置至少是max(x,y)1进制。一定要把位置找对啊 #include <bits/stdc.h> using namespace std; typedef l…...

JavaEE初阶Day 6:多线程(4)

目录 Day 6&#xff1a;多线程&#xff08;4&#xff09;1. 线程不安全的原因2. 锁3. synchronized Day 6&#xff1a;多线程&#xff08;4&#xff09; 前序&#xff1a;针对Day 5结尾的count 多线程的执行&#xff0c;是随机调度抢占式的执行模式&#xff0c;某个线程执行指…...

微信小程序 django+nodejs电影院票务售票选座系统324kd

小程序Android端运行软件 微信开发者工具/hbuiderx uni-app框架&#xff1a;使用Vue.js开发跨平台应用的前端框架&#xff0c;编写一套代码&#xff0c;可编译到Android、小程序等平台。 前端&#xff1a;HTML5,CSS3 VUE 后端&#xff1a;java(springbootssm)/python(flaskdja…...

基于springboot实现桂林旅游景点导游平台管理系统【项目源码+论文说明】计算机毕业设计

基于springboot实现桂林旅游景点导游平台管理系统演示 摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了桂林旅游景点导游平台的开发全过程。通过分析桂林旅游景点导游平台管理的不足&#xff0c;创建了一个计算…...

idea 开发serlvet汽车租赁管理系统idea开发sqlserver数据库web结构计算机java编程layUI框架开发

一、源码特点 idea开发 java servlet 汽车租赁管理系统是一套完善的web设计系统sqlserver数据库 系统采用serlvetdaobean mvc 模式开发&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。 java se…...

Unity之PUN实现多人联机射击游戏的优化(Section 3)

目录 &#x1f4a3;一、准备工作 &#x1f4a3;二、生成弹头脚本的编写 &#x1f4a3;三、实现发射和伤害同步 手雷都加了在给狗剩加个火箭筒不过分吧。效果看GIF动图&#xff0c;分别是单机和联机的效果。 添加火箭筒依旧是在原有的基础上更改&#xff0c;我查看火箭筒模型…...

PDF锐化

PDF Shaper Ultimate(pdf转图片) 编辑->添加文件->选中一个要处理的pdf 操作->转换->PDF转为图片 ComicEnhancerPro设置(把图片锐化) PDF Shaper Ultimate(图片转pdf) 编辑-添加图片->选中所有锐化处理后的图片 转换->图片转为pdf&#xff08;会把所有图…...

【python和java】

如何理解java和python的不同&#xff0c;在java中&#xff0c;先有类&#xff0c;类生出对象&#xff0c;对象承载数据。而python是直接数据&#xff0c;没有类的概念 理解 Java 和 Python 在面向对象编程&#xff08;OOP&#xff09;方面的不同&#xff0c;关键在于理解它们各…...

C盘满了怎么办,清理工具TreeSize

TreeSize是一款强大的磁盘空间分析工具&#xff0c;它可以帮助用户轻松地找出电脑中占用空间最多的文件和程序&#xff0c;从而让用户进行针对性地删除或卸载。 占用空间很小 下载链接&#xff1a;https://pan.quark.cn/s/bea23ed6b1d3...

【vue】watch 侦听器

watch&#xff1a;可监听值的变化&#xff0c;旧值和新值 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><titl…...

校招生如何准备软件测试、测试开发岗位的面试?

校招生如何准备软件测试、测试开发岗位的面试&#xff1f; 求职建议 大家都很困惑如何学习测试&#xff1f;如何准备测试方面的面试&#xff1f; 我有朋友是做研发的&#xff0c;他认为测试不用准备&#xff0c;直接用开发的简历就行。也有人认为要学习一些测试理论&#xf…...

蓝桥杯抱佛脚篇~

文章目录 基础语法输入输出集合(set&#xff09;排序 基础语法 输入输出 # 输入一个数 nint(input())# 输入两、三个数&#xff0c;例如&#xff1a;1 2 或者 1 2 3 x,y map(int,input().split())# 输入数组 # ——— 1 —— nums[int(i) for i in input().split()] print(n…...

基于springboot的大学城水电管理系统源码数据库

基于springboot的大学城水电管理系统源码数据库 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了大学城水电管理系统的开发全过程。通过分析大学城水电管理系统管理的不足&#xff0c;创建了一个计算机管理大学城水…...

AI大模型探索之路-应用篇2:Langchain框架ModelIO模块—数据交互的秘密武器

目录 前言 一、概述 二、Model 三、Prompt 五、Output Parsers 总结 前言 随着人工智能技术的不断进步&#xff0c;大模型的应用场景越来越广泛。LangChain框架作为一个创新的解决方案&#xff0c;专为处理大型语言模型的输入输出而设计。其中&#xff0c;Model IO&#…...

【SSH】群晖开启ssh访问

群晖开启ssh访问 假设 你需要设置群晖 账号 test-user 开启ssh访问 设置 你的 test-user 为管理员权限 否则你无法通过cmd 面板 连接访问 群晖你需要哪个账号 就使用哪个账号终端 cmd连接 否则需要考虑后续创建 rsa 公密钥文件的 所属权 问题账号密码连接登录终端 ssh -p 端…...

Vue 移动端(H5)项目怎么实现页面缓存(即列表页面进入详情返回后列表页面缓存且还原页面滚动条位置)keep-alive缓存及清除keep-alive缓存

一、需求 产品要求&#xff1a;Vue移动端项目进入列表页&#xff0c;列表页需要刷新&#xff0c;而从详情页返回列表页&#xff0c;列表页则需要缓存并且还原页面滚动条位置 二、实现思路 1、使用Vue中的keep-alive组件&#xff0c;keep-alive提供了路由缓存功能 2、因为我项…...

【MVCC】深入浅出彻底理解MVCC

MVCC概述 MVCC&#xff08;Multi-Version Concurrency Control&#xff09;即多版本并发控制。主要是为了提高数据库的并发性能而提供的&#xff0c;采用了不加锁的方式处理读-写并发冲突&#xff0c;确保了任何时刻的读操作都是非阻塞的。只需要很小的开销&#xff0c;就可以…...

【问题解决】ubuntu安装新版vscode报code-insiders相关错误

问题 目前 vscode官网 最新的包为 insiders_1.89.0-1712297812_amd64.deb &#xff0c;双击或者使用sudo dpkg -i code-insiders_1.89.0-1712297812_amd64.deb安装后报错&#xff0c;执行其他命令也报错。 安装环境&#xff1a;ubuntu18.04 dpkg: 处理软件包 code-insiders (…...

【Python】面向对象(专版提升2)

面向对象 1. 概述1.1面向过程1.2 面向对象 2. 类和对象2.1 语法2.1.1 定义类2.1.2 实例化对象 2.2 实例成员2.2.1 实例变量2.2.2 实例方法2.2.3 跨类调用 3. 三大特征3.1 封装3.1.1 数据角度3.1.2 行为角度3.1.3 案例:信息管理系统3.1.3.1 需求3.1.3.2 分析3.1.3.3 设计 3.2 继…...

Vscode设置滚轮进行字体大小的调节

Vscode设置滚轮进行字体大小的调节 正常的话按 ctrl 或者 ctrl - 进行字体的大小调节 1.打开Vscode&#xff0c;找打设置的图标&#xff0c;在点击设置&#xff0c;或者直接使用快捷键&#xff0c;【ctrl ,】 2. 在搜索框搜索Font Ligatures 3.双击进入settings.json ,找到如…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...