[算法刷题题解笔记] 洛谷 P1011 [NOIP1998 提高组] 车站 [数学|斐波那契|推导]

简介: [算法刷题题解笔记] 洛谷 P1011 [NOIP1998 提高组] 车站 [数学|斐波那契|推导]

题目链接

题目大意

  • 根据题目给出的每个车站上下车人数的规律,以及测试点输入的数据:始发站上车人数a、车站数n、终点站下车人数m,编写程序,计算出所求的站点编号x火车发车时车上的人数

解题思路

  • 假设第二站上下车人数为x,推导每个车站火车发车时车上人数的公式表达式:
  • 推导出公式为:m = k1a + k2x
  • 其中k1 k2为a和x前的系数,a为始发站上车人数,x为第二站的上下车人数,m为终点站下车人数
  • k1_i = k1_(i-1) + k1_(i-2) - 1 从第四站开始为前两站系数之和 - 1
  • k2_i = k2_(i-1) + k2_(i-2) + 1 从第四站开始为前两站系数之和 + 1
  • 先根据a和x前的系数k1 k2的规律,求出最后一站前一站发车时车上人数表示公式的k1 k2,最后一站下车人数等于前一站上下车后车上人数(最后一站全部下)
  • 在求解最后一站前一站发车时车上人数表示公式的k1 k2的过程中,保存每一站发车时车上人数表示公式的k1 k2
  • 然后根据推导出公式求出未知数x
  • 最后利用推导公式和提前求解保存的每一站发车时车上人数表示公式的k1 k2,求解输出所求站点xi出发时的车上人数

截图代码

// package luogu.orange;
import java.io.*;
/**
 * ClassName: P1011
 * Package: luogu.orange
 * Description:
 *
 * @Author tcw
 * @Create 2023-06-08 23:44
 * @Version 1.0
 */
public class Main {
    // 快读快写
    private static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    private static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static void main(String[] args) {
        // 始发站上车人数
        int a = readInt();
        // 车站数
        int n = readInt();
        // 终点站下车人数
        int m = readInt();
        // 所求站点编号
        int xi = readInt();
        // 根据推导,m = k1a + k2x
        // 其中k1 k2为a和x前的系数,a为始发站上车人数
        // x为第二站的上下车人数,m为终点站下车人数
        // k1_i = k1_(i-1) + k1_(i-2) - 1 从第四站开始为前两站系数之和-1
        // k2_i = k2_(i-1) + k2_(i-2) + 1 从第四站开始为前两站系数之和+1
        // 存储系数
        int[] k1 = new int[n];
        int[] k2 = new int[n];
        // 求解推导出的公式系数,并求解x
        // 由于最后一站下车人数等于前一站上下车后车上人数(最后一站全部下)
        for (int i = 1; i <= n - 1; i++) {
            if (i == 1) {
                k1[i] = 1;
                k2[i] = 0;
            } else if (i == 2) {
                k1[i] = 1;
                k2[i] = 0;
            } else if (i == 3) {
                k1[i] = 2;
                k2[i] = 0;
            } else {
                k1[i] = k1[i - 1] + k1[i - 2] - 1;
                k2[i] = k2[i - 1] + k2[i - 2] + 1;
            }
            // out.println(k1[i] +" " + k2[i]);
        }
        // 根据推导公式 m = k1a + k2x 求解x
        int x = (m - k1[n - 1] * a) / k2[n - 1];
        // 计算输出所求站点xi出发时的车上人数
        out.print(k1[xi] * a + k2[xi] * x);
        out.flush();
    }
    private static int readInt() {
        int in = 0;
        try {
            st.nextToken();
            in = (int) st.nval;
        } catch (IOException e) {
            e.printStackTrace();
        }
        return in;
    }
}


相关文章
|
19天前
|
机器学习/深度学习 算法
扩散模型=进化算法!生物学大佬用数学揭示本质
在机器学习与生物学交叉领域,Tufts和Harvard大学研究人员揭示了扩散模型与进化算法的深刻联系。研究表明,扩散模型本质上是一种进化算法,通过逐步去噪生成数据点,类似于进化中的变异和选择机制。这一发现不仅在理论上具有重要意义,还提出了扩散进化方法,能够高效识别多解、处理高维复杂参数空间,并显著减少计算步骤,为图像生成、视频合成及神经网络优化等应用带来广泛潜力。论文地址:https://arxiv.org/pdf/2410.02543。
38 21
|
2月前
|
机器学习/深度学习 人工智能 算法
Transformer打破三十年数学猜想!Meta研究者用AI给出反例,算法杀手攻克数学难题
《PatternBoost: Constructions in Mathematics with a Little Help from AI》提出了一种结合传统搜索算法和Transformer神经网络的PatternBoost算法,通过局部搜索和全局优化交替进行,成功应用于组合数学问题。该算法在图论中的Ramsey数研究中找到了更小的反例,推翻了一个30年的猜想,展示了AI在数学研究中的巨大潜力,但也面临可解释性和通用性的挑战。论文地址:https://arxiv.org/abs/2411.00566
92 13
|
2月前
|
机器学习/深度学习 算法 PyTorch
深度强化学习中SAC算法:数学原理、网络架构及其PyTorch实现
软演员-评论家算法(Soft Actor-Critic, SAC)是深度强化学习领域的重要进展,基于最大熵框架优化策略,在探索与利用之间实现动态平衡。SAC通过双Q网络设计和自适应温度参数,提升了训练稳定性和样本效率。本文详细解析了SAC的数学原理、网络架构及PyTorch实现,涵盖演员网络的动作采样与对数概率计算、评论家网络的Q值估计及其损失函数,并介绍了完整的SAC智能体实现流程。SAC在连续动作空间中表现出色,具有高样本效率和稳定的训练过程,适合实际应用场景。
298 7
深度强化学习中SAC算法:数学原理、网络架构及其PyTorch实现
|
5月前
|
算法 API 计算机视觉
人脸识别笔记(一):通过yuface调包(参数量54K更快更小更准的算法) 来实现人脸识别
本文介绍了YuNet系列人脸检测算法的优化和使用,包括YuNet-s和YuNet-n,以及通过yuface库和onnx在不同场景下实现人脸检测的方法。
155 1
|
5月前
|
JSON 算法 数据可视化
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
这篇文章是关于如何通过算法接口返回的目标检测结果来计算性能指标的笔记。它涵盖了任务描述、指标分析(包括TP、FP、FN、TN、精准率和召回率),接口处理,数据集处理,以及如何使用实用工具进行文件操作和数据可视化。文章还提供了一些Python代码示例,用于处理图像文件、转换数据格式以及计算目标检测的性能指标。
114 0
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
|
5月前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
45 0
|
7天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于GRU网络的MQAM调制信号检测算法matlab仿真,对比LSTM
本研究基于MATLAB 2022a,使用GRU网络对QAM调制信号进行检测。QAM是一种高效调制技术,广泛应用于现代通信系统。传统方法在复杂环境下性能下降,而GRU通过门控机制有效提取时间序列特征,实现16QAM、32QAM、64QAM、128QAM的准确检测。仿真结果显示,GRU在低SNR下表现优异,且训练速度快,参数少。核心程序包括模型预测、误检率和漏检率计算,并绘制准确率图。
80 65
基于GRU网络的MQAM调制信号检测算法matlab仿真,对比LSTM
|
12天前
|
算法
基于遗传优化算法的风力机位置布局matlab仿真
本项目基于遗传优化算法(GA)进行风力机位置布局的MATLAB仿真,旨在最大化风场发电效率。使用MATLAB2022A版本运行,核心代码通过迭代选择、交叉、变异等操作优化风力机布局。输出包括优化收敛曲线和最佳布局图。遗传算法模拟生物进化机制,通过初始化、选择、交叉、变异和精英保留等步骤,在复杂约束条件下找到最优布局方案,提升风场整体能源产出效率。
|
12天前
|
算法 安全 机器人
基于包围盒的机械臂防碰撞算法matlab仿真
基于包围盒的机械臂防碰撞算法通过构建包围盒来近似表示机械臂及其环境中各实体的空间占用,检测包围盒是否相交以预判并规避潜在碰撞风险。该算法适用于复杂结构对象,通过细分目标对象并逐级检测,确保操作安全。系统采用MATLAB2022a开发,仿真结果显示其有效性。此技术广泛应用于机器人运动规划与控制领域,确保机器人在复杂环境中的安全作业。
|
12天前
|
机器学习/深度学习 数据采集 算法
基于WOA鲸鱼优化的CNN-GRU-SAM网络时间序列回归预测算法matlab仿真
本项目基于MATLAB 2022a实现时间序列预测,采用CNN-GRU-SAM网络结构,结合鲸鱼优化算法(WOA)优化网络参数。核心代码含操作视频,运行效果无水印。算法通过卷积层提取局部特征,GRU层处理长期依赖,自注意力机制捕捉全局特征,全连接层整合输出。数据预处理后,使用WOA迭代优化,最终输出最优预测结果。