第十三届蓝桥杯真题: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,b这个位置上的数是y,那么此位置至少是max(x,y)1进制。一定要把位置找对啊 #include <bits/stdc.h> using namespace std; typedef l…...
JavaEE初阶Day 6:多线程(4)
目录 Day 6:多线程(4)1. 线程不安全的原因2. 锁3. synchronized Day 6:多线程(4) 前序:针对Day 5结尾的count 多线程的执行,是随机调度抢占式的执行模式,某个线程执行指…...

微信小程序 django+nodejs电影院票务售票选座系统324kd
小程序Android端运行软件 微信开发者工具/hbuiderx uni-app框架:使用Vue.js开发跨平台应用的前端框架,编写一套代码,可编译到Android、小程序等平台。 前端:HTML5,CSS3 VUE 后端:java(springbootssm)/python(flaskdja…...

基于springboot实现桂林旅游景点导游平台管理系统【项目源码+论文说明】计算机毕业设计
基于springboot实现桂林旅游景点导游平台管理系统演示 摘要 随着信息技术在管理上越来越深入而广泛的应用,管理信息系统的实施在技术上已逐步成熟。本文介绍了桂林旅游景点导游平台的开发全过程。通过分析桂林旅游景点导游平台管理的不足,创建了一个计算…...

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

Unity之PUN实现多人联机射击游戏的优化(Section 3)
目录 💣一、准备工作 💣二、生成弹头脚本的编写 💣三、实现发射和伤害同步 手雷都加了在给狗剩加个火箭筒不过分吧。效果看GIF动图,分别是单机和联机的效果。 添加火箭筒依旧是在原有的基础上更改,我查看火箭筒模型…...

PDF锐化
PDF Shaper Ultimate(pdf转图片) 编辑->添加文件->选中一个要处理的pdf 操作->转换->PDF转为图片 ComicEnhancerPro设置(把图片锐化) PDF Shaper Ultimate(图片转pdf) 编辑-添加图片->选中所有锐化处理后的图片 转换->图片转为pdf(会把所有图…...
【python和java】
如何理解java和python的不同,在java中,先有类,类生出对象,对象承载数据。而python是直接数据,没有类的概念 理解 Java 和 Python 在面向对象编程(OOP)方面的不同,关键在于理解它们各…...

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

【vue】watch 侦听器
watch:可监听值的变化,旧值和新值 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><titl…...

校招生如何准备软件测试、测试开发岗位的面试?
校招生如何准备软件测试、测试开发岗位的面试? 求职建议 大家都很困惑如何学习测试?如何准备测试方面的面试? 我有朋友是做研发的,他认为测试不用准备,直接用开发的简历就行。也有人认为要学习一些测试理论…...
蓝桥杯抱佛脚篇~
文章目录 基础语法输入输出集合(set)排序 基础语法 输入输出 # 输入一个数 nint(input())# 输入两、三个数,例如:1 2 或者 1 2 3 x,y map(int,input().split())# 输入数组 # ——— 1 —— nums[int(i) for i in input().split()] print(n…...
基于springboot的大学城水电管理系统源码数据库
基于springboot的大学城水电管理系统源码数据库 随着信息技术在管理上越来越深入而广泛的应用,管理信息系统的实施在技术上已逐步成熟。本文介绍了大学城水电管理系统的开发全过程。通过分析大学城水电管理系统管理的不足,创建了一个计算机管理大学城水…...

AI大模型探索之路-应用篇2:Langchain框架ModelIO模块—数据交互的秘密武器
目录 前言 一、概述 二、Model 三、Prompt 五、Output Parsers 总结 前言 随着人工智能技术的不断进步,大模型的应用场景越来越广泛。LangChain框架作为一个创新的解决方案,专为处理大型语言模型的输入输出而设计。其中,Model IO&#…...
【SSH】群晖开启ssh访问
群晖开启ssh访问 假设 你需要设置群晖 账号 test-user 开启ssh访问 设置 你的 test-user 为管理员权限 否则你无法通过cmd 面板 连接访问 群晖你需要哪个账号 就使用哪个账号终端 cmd连接 否则需要考虑后续创建 rsa 公密钥文件的 所属权 问题账号密码连接登录终端 ssh -p 端…...

Vue 移动端(H5)项目怎么实现页面缓存(即列表页面进入详情返回后列表页面缓存且还原页面滚动条位置)keep-alive缓存及清除keep-alive缓存
一、需求 产品要求:Vue移动端项目进入列表页,列表页需要刷新,而从详情页返回列表页,列表页则需要缓存并且还原页面滚动条位置 二、实现思路 1、使用Vue中的keep-alive组件,keep-alive提供了路由缓存功能 2、因为我项…...

【MVCC】深入浅出彻底理解MVCC
MVCC概述 MVCC(Multi-Version Concurrency Control)即多版本并发控制。主要是为了提高数据库的并发性能而提供的,采用了不加锁的方式处理读-写并发冲突,确保了任何时刻的读操作都是非阻塞的。只需要很小的开销,就可以…...

【问题解决】ubuntu安装新版vscode报code-insiders相关错误
问题 目前 vscode官网 最新的包为 insiders_1.89.0-1712297812_amd64.deb ,双击或者使用sudo dpkg -i code-insiders_1.89.0-1712297812_amd64.deb安装后报错,执行其他命令也报错。 安装环境: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,找打设置的图标,在点击设置,或者直接使用快捷键,【ctrl ,】 2. 在搜索框搜索Font Ligatures 3.双击进入settings.json ,找到如…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...

MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

什么是Ansible Jinja2
理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具,可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板,允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板,并通…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

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