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

【2024.9.28练习】青蛙的约会

题目描述


题目分析

        由于两只青蛙都在跳跃导致变量多,不妨采用物理题中的相对运动思想,设青蛙A不动,青蛙B每次跳n-m米,两只青蛙的距离为x-y米。正常来说,只要模拟青蛙B与青蛙A的相对运动过程,最终当青蛙B与青蛙A距离为0时即可求得总跳跃次数。但是难点在于数据量大,按部就班的模拟将会超时。

        由于这是一道有关整数和环的数学题,考虑使用扩展欧几里得算法求解。现直接假设一只青蛙静止,另一只青蛙每次位移为a=n-m,总跳跃次数为X,一圈长度为b=L,跳跃的圈数为Y,青蛙间的距离为c=x-y。则题目满足方程:aX+bY=c。显然要使方程有整数解,必须满足的条件是:c必须是 a 和 b 的最大公约数的倍数,即ax\equiv c(mod\ b)。这可以通过贝祖定理证明。

        接下来的难点是求出最小跳跃次数。根据拓展欧几里得算法已经得到了方程的一组特解,但这不一定是最优解,根据线性同余方程的通解公式:

x=x_0+k\frac{b}{d}\mid k\in \mathbb{Z},d=gcd(a,b)

只需让该特解模除\frac{b}{d}即可求出跳跃次数在(0,\frac{b}{d}]间的最小正整数解。

        提交后有一处测试点有误,经检查,原来在exgcd算法中,如果两个参数存在负数,输出的最大公因数gcd(a,b)也可能是负数。这并不影响所得特解的正确性,但在求最小正解的时候,需要采取措施让取模后的结果转变为正数。


我的代码

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;// 扩展欧几里得算法
ll extgcd(ll a, ll b, ll& x, ll& y) {if (b == 0) {x = 1;y = 0;return a;}ll d = extgcd(b, a % b, y, x);y -= (a / b) * x;return d;
}int main() {ll x, y, m, n, L;cin >> x >> y >> m >> n >> L;ll a = n - m;  // 移项后得到 a = n - mll b = x - y;  // 常数项 b = x - yll l = L;      // 模数为 Lll x0, y0;ll d = extgcd(a, l, x0, y0);  // 使用扩展欧几里得求解if (b % d != 0) {cout << "Impossible" << endl;}else {// 存在解的情况,求最小非负整数解ll k = (x0 * (b / d)) % (l / d); //其中x0*(b/d)为一个方程的特解if (k < 0) {if (l / d > 0) {k += l / d;  // 保证 k 为非负}else {k -= l / d;  // 保证 k 为非负}}cout << k << endl;}return 0;
}

由于扩展欧几里得算法参数使用了引用,导致逻辑相对更难理解,我利用原本欧几里得算法的数学递推逻辑修改为一下函数,程序可以成功运行:

ll x_0;
ll y_0;
ll x_1;
ll y_1;
ll extgcd(ll a, ll b) {ll d = a;if (b != 0) {d = extgcd(b, a % b);x_0 = y_1;y_0 = x_1 - a / b * y_1;y_1 = y_0;x_1 = x_0;}else {x_1 = 1;y_1 = 0;}return d;
}

相关文章:

【2024.9.28练习】青蛙的约会

题目描述 题目分析 由于两只青蛙都在跳跃导致变量多&#xff0c;不妨采用物理题中的相对运动思想&#xff0c;设青蛙A不动&#xff0c;青蛙B每次跳米&#xff0c;两只青蛙的距离为米。正常来说&#xff0c;只要模拟青蛙B与青蛙A的相对运动过程&#xff0c;最终当青蛙B与青蛙A距…...

Python入门:类的异步资源管理与回收( __del__ 方法中如何调用异步函数)

文章目录 📖 介绍 📖🏡 演示环境 🏡📒 文章内容 📒📝 使用上下文管理器📝 使用 `__del__` 方法📝 结合使用上下文管理器与 `__del__`📝 资源回收的重要性⚓️ 相关链接 ⚓️📖 介绍 📖 在编程中,资源的管理和回收至关重要,尤其是在处理网络请求时。频…...

Android开发中的ViewModel

在Android应用开发中&#xff0c;ViewModel作为架构组件之一&#xff0c;扮演着管理UI数据和生命周期的关键角色。本文将深入探讨ViewModel如何感知View的生命周期&#xff0c;并分析其内核原理&#xff0c;帮助开发者更好地利用ViewModel优化应用架构。 一、ViewModel简介 在…...

Vue 3 文件编译流程详解与 Babel 的使用

文章目录 一、背景二、结论三、vitejs/plugin-vue 插件调试前物料准备vuePlugin 入口buildStart 方法transform 方法 四、vue/compiler-sfc 核心包parse 方法compileScript、rewriteDefault 方法compileTemplate 方法 五、整体架构六、总结参考资料 一、背景 最近正在研究 rea…...

Android常用C++特性之std::chrono

声明&#xff1a;本文内容生成自ChatGPT&#xff0c;目的是为方便大家了解学习作为引用到作者的其他文章中。 std::chrono 是 C11 引入的标准库中的时间处理工具&#xff0c;提供了以多种精度进行时间测量、处理和操作的功能。它允许开发者处理时间点&#xff08;time_point&am…...

[Oracle] ORA-04036: 实例使用的 PGA 内存超出 PGA_AGGREGATE_LIMIT

有说该问题是因为触发了Oracle的BUG导致&#xff0c;最直接的解决方法就是重启数据库实例&#xff1b; Linux下数据库实例重启...

一次 Spring 扫描 @Component 注解修饰的类坑

问题现象 之前遇到过一个问题&#xff0c;在一个微服务的目录下有相同功能 jar 包的两个不同的版本&#xff0c;其中一个版本里面的类有 Component 注解&#xff0c;另外一个版本的类里面没有 Component 注解&#xff0c;且按照加载的顺序&#xff0c;没有 Component 注解的 j…...

深度学习:调整学习率

目录 前言 一、什么是调整学习率&#xff1f; 二、调整学习率的作用 三、怎么调整学习率 1.有序调整 2.自适应调整 3.自定义调整 4.调整示例 前言 在深度学习中&#xff0c;调整学习率是非常重要的&#xff0c;它对模型的训练效果和收敛速度有显著影响。 一、什么是调整…...

Java项目实战II基于Java+Spring Boot+MySQL的厨艺交流平台设计与实现(源码+数据库+文档)

目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发&#xff0c;CSDN平台Java领域新星创作者&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。获取源码联系方式请查看文末 一、前言 在美食文化…...

第二十节:学习Redis缓存数据库实现增删改查(自学Spring boot 3.x的第五天)

这节记录下如何使用redis缓存数据库。 第一步&#xff1a; 先在服务器端安装redis&#xff0c; 下载地址&#xff1a;Releases tporadowski/redis GitHub。 第二步&#xff1a; 安装redis客户端可视化管理软件redisDesktopmanager Redis Desktop Manager - Download 第…...

Android SQLite的基本使用、生成Excel文件保存到本地

1. Android SQLite的基本使用 1.1. SQLiteOpenHelper Android 底层已经通过一个SQLiteOpenHelper的抽象类将数据库的创建&#xff0c;以及修改&#xff0c;更新等都放在了里面。 要使用它必须实现它的OnCreate(SQLiteDatabase db)&#xff0c;onUpgrade(SQLiteDatabase db, int…...

记一次因视频编码无法在浏览器播放、编码视频报错问题

起因 ... f cv2.VideoWriter_fourcc(*h264) ...我这边使用h264编码会提示 OpenCV: FFMPEG: tag 0x34363268/h264 is not supported with codec id 27 and format mp4 / MP4 (MPEG-4 Part 14) OpenCV: FFMPEG: fallback to use tag 0x31637661/avc1 [ERROR:02.711] global /i…...

【深度学习】深度卷积神经网络(AlexNet)

在 LeNet 提出后&#xff0c;卷积神经网络在计算机视觉和机器学习领域中很有名气&#xff0c;但并未起到主导作用。 这是因为 LeNet 在更大、更真实的数据集上训练的性能和可行性还有待研究。 事实上&#xff0c;在 20 世纪 90 年代到 2012 年之间的大部分时间里&#xff0c;…...

C语言扫盲

文章目录 C版本C语言特征GCCprintf数据类型函数指针内存管理void指针 Struct结构和Union结构typedef预处理器make工具cmake工具Projectintegral of sinc functionemulator embedded systeman event schedule 补充在线Linux终端安装Linux参考 建议还是国外教材学习…人家的PPT比…...

视频融合共享平台LntonAIServer视频智能分析抖动检测算法和过亮过暗检测算法

LntonAIServer作为一款智能视频监控平台&#xff0c;集成了多种先进的视频质量诊断功能&#xff0c;其中包括抖动检测和过暗检测算法。这些算法对于提升视频监控系统的稳定性和图像质量具有重要意义。 以下是对抖动检测算法和过暗检测算法的应用场景及优势的详细介绍。 一、L…...

【笔记篇】Davinci Configurator OS模块(上)

目录 1 简介1.1 架构概览2 功能描述2.1 特性2.2 规范偏离2.2.1 API 函数的泛型偏离2.2.2 可信函数 API 偏离2.2.3 服务保护偏离2.2.4 代码保护2.2.5 SyncScheduleTable API 偏差2.2.6 CheckTask/ISRMemoryAccess API 偏差2.2.7 中断 API 偏差2.2.8 Cross Core Getter API2.2.9 …...

19.3 打镜像部署到k8s中,prometheus配置采集并在grafana看图

本节重点介绍 : 打镜像&#xff0c;导出镜像&#xff0c;传输到各个节点并导入运行该项目配置prometheus和grafana 打镜像 本地build docker build -t ink8s-pod-metrics:v1 .build过程 导出镜像 docker save ink8s-pod-metrics > ink8s-pod-metrics.tar 传输到各个node…...

如何让系统u盘重新可用

目录 引言开始操作遇到的错误 引言 我们将 u 盘制作为系统 U 盘后&#xff0c;U 盘就没法在电脑中正常识别出了。当装完系统&#xff0c;不再需要 u 盘充当系统 U 盘想要正常使用该 U 盘&#xff0c;这时候就需要有些操作&#xff0c;让这个 U 盘正常化。 上图就是充当系统盘的…...

14.安卓逆向-frida基础-编写hook脚本2

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 内容参考于&#xff1a;图灵Python学院 本人写的内容纯属胡编乱造&#xff0c;全都是合成造假&#xff0c;仅仅只是为了娱乐&#xff0c;请不要盲目相信。 工…...

车辆零部件检测和分割数据集-车体数据集-yolo格式-yolov5-yolov10可用

这些标签是用于实例分割任务中的类别&#xff0c;通常在汽车图像识别或自动驾驶技术中使用。以下是这些类别&#xff1a; back_bumper - 后保险杠back_glass - 后挡风玻璃back_left_door - 后左车门back_left_light - 后左灯back_right_door - 后右车门back_right_light - 后右…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器

拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件&#xff1a; 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...

Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解

文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一&#xff1a;HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二&#xff1a;Floyd 快慢指针法&#xff08;…...