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

HDU1005——Number Sequence,HDU1006——Tick and Tick,HDU1007——Quoit Design

目录

HDU1005——Number Sequence

题目描述

超时代码

代码思路

正确代码

代码思路

HDU1006——Tick and Tick

题目描述

运行代码

代码思路

HDU1007——Quoit Design

题目描述

运行代码

代码思路

HDU1005——Number Sequence

题目描述

Problem - 1005

超时代码

#include <iostream>
using namespace std;
int f(int A, int B, int n) {int f1 = 1, f2 = 1, fn;if (n == 1 || n == 2) {return 1;}for (int i = 3; i <= n; i++) {fn = (A * f1 + B * f2) % 7;f2 = f1;f1 = fn;}return fn;
}
int main() {int A, B, n;while (true) {cin >> A >> B >> n;if (A == 0 && B == 0 && n == 0) {break;}cout << f(A, B, n) << endl;}return 0;
}

代码思路

  1. 函数 f:

    • 定义了三个变量 f1f2, 和 fn 分别代表序列中的前两个值和当前计算的值。
    • 如果 n 是1或者2,函数直接返回1,这可以看作是序列的初始条件。
    • 当 n 大于2时,进入一个循环,从3到 n
      • 每次迭代计算 fn 为 A 乘以 f1 加上 B 乘以 f2 的结果,并对7取模。
      • 然后更新 f1 和 f2 的值以便下一次迭代。
    • 循环结束后,返回 fn
  2. 主函数 main:

    • 无限循环读取用户输入的 AB, 和 n 值,直到遇到所有为0的终止条件。
    • 调用 f 函数并打印结果。
    • 当输入 AB, 和 n 全部为0时,循环结束,程序退出。

这个结果最后是超时运算

正确代码

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;
int f[100];
int length, st;  // 循环节长度和循环开始的标记bool finda(int n) {int a = f[n - 1], b = f[n];// 使用更高效的搜索算法,如二分查找int left = 1, right = n - 2;while (left <= right) {int mid = left + (right - left) / 2;if (f[mid] == a && f[mid + 1] == b) {st = mid;length = n - 1 - mid;return true;}else if (f[mid] < a || (f[mid] == a && f[mid + 1] < b)) {left = mid + 1;}else {right = mid - 1;}}return false;
}int main() {int a, b, n;while (true) {cin >> a >> b >> n;if (a == 0)break;f[1] = 1; f[2] = 1;for (int i = 3; i < 100; i++) {// 预先计算乘法结果,避免重复计算int prev1Mult = a * f[i - 1];int prev2Mult = b * f[i - 2];f[i] = (prev1Mult + prev2Mult) % 7;if (finda(i))break;}if (n < st)cout << f[n] << endl;elsecout << f[(n - st) % length + st] << endl;}
}

代码思路

  1. 初始化序列:数组f[]用来存储序列的值。lengthst变量分别用于记录循环节的长度和循环节开始的位置。

  2. 计算序列

    • 使用循环从第三项开始计算序列的值,直到检测到循环节或者达到预设的上限(这里是100项)。
    • 每一项计算使用了预先计算的乘法结果(prev1Multprev2Mult),这有助于减少重复计算,提高效率。
  3. 检测循环节:函数finda()通过二分查找算法检测序列中的循环节。一旦找到重复的模式(即连续两项相同),它会记录循环节的开始位置(st)和长度(length)。

  4. 输出结果

    • 根据用户输入的nn,如果nn小于循环节开始的位置,直接输出f[n]
    • 如果nn大于等于循环节开始的位置,则输出循环节中对应位置的值,即f[(n - st) % length + st]

这种算法特别适用于计算周期性出现的序列,通过检测循环节可以极大地优化计算过程,尤其是在需要频繁查询大索引位置的场景下。

HDU1006——Tick and Tick

题目描述

Problem - 1006

运行代码

#include <iostream>
#include <stdio.h>
#include <algorithm>const double sm = 59.0 / 10, sh = 719.0 / 120, mh = 11.0 / 120;
const double t_sm = 360 * 10.0 / 59, t_sh = 360 * 120.0 / 719, t_mh = 360 * 120.0 / 11;using namespace std;// 定义最大值最小值函数
double Min(double a, double b, double c) {return min(c, min(a, b));
}double Max(double a, double b, double c) {return max(c, max(a, b));
}int main()
{double D;while (cin >> D && D != -1) {double b_sm, b_sh, b_mh, e_sm, e_sh, e_mh, start, finish, sum = 0;if (D == 0) {sum = 100;printf("%.3lf\n", 100.0);continue;}// 第一次满足条件的时间b_sm = D / sm;b_sh = D / sh;b_mh = D / mh;// 第一次不满足条件的时间e_sm = (360 - D) / sm;e_sh = (360 - D) / sh;e_mh = (360 - D) / mh;// 使用简洁的循环条件double b1 = b_sm, e1 = e_sm;while (e1 <= 12 * 60 * 60) {double b2 = b_sh, e2 = e_sh;while (e2 <= 12 * 60 * 60) {if (e2 < b1) {b2 += t_sh;e2 += t_sh;continue;}if (b2 > e1) {break;}double b3 = b_mh, e3 = e_mh;while (e3 <= 12 * 60 * 60) {if (e3 < b2 || e3 < b1) {b3 += t_mh;e3 += t_mh;continue;}if (b3 > e1 || b3 > e2) {break;}start = Max(b1, b2, b3);finish = Min(e1, e2, e3);sum += (finish - start);b3 += t_mh;e3 += t_mh;}b2 += t_sh;e2 += t_sh;}b1 += t_sm;e1 += t_sm;}printf("%.3lf\n", sum / (12 * 60 * 60) * 100);}return 0;
}

代码思路

  1. 常量

    • smshmh分别代表三个假想的“指针”(小指针、特殊指针和中等指针)的速度(每分钟的度数)。
    • t_smt_sht_mh分别表示这些“指针”完成一个完整周期所需的时间(以分钟计)。
  2. 输入处理

    • 程序读取一个值D,这个值代表任意两个“指针”要被认为是“接近”的最大角度距离。
    • 如果D = 0,意味着“指针”必须完全重合,结果总是100%。
    • 如果D = -1,则表示输入结束。
  3. 计算初始边界

    • 对于每个“指针”,它计算第一次它们会处于离起点DD度内的时刻(b_smb_shb_mh)。
    • 同样,它也计算第一次它们不会处于离起点DD度内的时刻(e_sme_she_mh)。
  4. 查找重叠区间

    • 程序使用嵌套循环来遍历所有可能的时刻,这时所有的三个“指针”可以同时处于彼此DD度内。
    • 根据当前迭代,更新边界(b1b2b3)和端点(e1e2e3)。
    • 它使用MinMax函数来找到所有“指针”都接近的区间的开始和结束。
    • 它在sum中累积这些区间的持续时间。
  5. 输出:处理完所有区间后,它计算出12小时总时段内所有“指针”处于DD度内的百分比时间。

高效地找到所有三个进程符合给定条件的重叠区间,即使它们有不同的速度和周期。

HDU1007——Quoit Design

题目描述

Problem - 1007

运行代码

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXX 1 << 30
#define MAXN 100010
using namespace std;
struct Point {double x, y;
};
Point p[MAXN];
int t[MAXN];
bool cmpX(const Point& a, const Point& b) {if (a.x == b.x) return a.y < b.y;return a.x < b.x;
}
bool cmpY(const int& a, const int& b) {return p[a].y < p[b].y;
}
double dist(Point a, Point b) {return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double findClosestPair(int left, int right) {double minDist = MAXX;if (left == right) return minDist;if (left + 1 == right) return dist(p[left], p[right]);int mid = (left + right) / 2;double leftMin = findClosestPair(left, mid);double rightMin = findClosestPair(mid + 1, right);minDist = min(leftMin, rightMin);int cnt = 0;for (int i = left; i <= right; i++) {if (fabs(p[i].x - p[mid].x) < minDist) {t[cnt++] = i;}}sort(t, t + cnt, cmpY);for (int i = 0; i < cnt; i++) {for (int j = i + 1; j < cnt && p[t[j]].y - p[t[i]].y < minDist; j++) {double d = dist(p[t[i]], p[t[j]]);minDist = min(minDist, d);}}return minDist;
}
int main() {int n;while (scanf("%d", &n) && n) {for (int i = 0; i < n; i++) {scanf("%lf%lf", &p[i].x, &p[i].y);}sort(p, p + n, cmpX);double r = findClosestPair(0, n - 1) / 2.0;printf("%.2lf\n", r);}return 0;
}

代码思路

寻找二维平面上的最近点对。其主要思想是使用分治算法(Divide and Conquer)来解决,具体步骤如下:

  1. 定义结构体 Point 存储每个点的坐标。

  2. 比较函数 cmpXcmpY 分别用于按照 x 坐标和 y 坐标排序点。

  3. 距离函数 dist 计算两点之间的欧几里得距离。

  4. 递归函数 findClosestPair 是核心部分,它接收左边界和右边界作为参数,表示要处理的点集范围。

    • 如果范围内只有一个点或没有点,返回一个很大的值 MAXX 表示没有距离可言。
    • 如果范围内正好有两个点,直接计算并返回这两个点的距离。
    • 否则,将点集分为左右两半,递归地在两边找到最小距离。
    • 然后,检查中线两侧的点是否包含更近的点对。为此,收集所有与中线距离小于目前最小距离的点,并按 y 坐标排序。
    • 在这个已排序的子集中,检查每一对相邻点的 y 坐标差小于目前最小距离的点对,计算它们之间的距离,并更新最小距离。
  5. 主函数 main 读取点集数量 n 和每个点的坐标,然后调用 findClosestPair 函数,最后输出最近点对之间距离的一半(题目可能要求输出半径,即最近点对距离的一半),保留两位小数。

这种方法的时间复杂度为 O(n log n),其中 n 是点的数量。这是因为每次递归调用处理一半的点,同时还需要对子集进行排序。空间复杂度为 O(n),因为需要额外的空间存储排序后的点和临时数组。

相关文章:

HDU1005——Number Sequence,HDU1006——Tick and Tick,HDU1007——Quoit Design

目录 HDU1005——Number Sequence 题目描述 超时代码 代码思路 正确代码 代码思路 HDU1006——Tick and Tick 题目描述 运行代码 代码思路 HDU1007——Quoit Design 题目描述 运行代码 代码思路 HDU1005——Number Sequence 题目描述 Problem - 1005 超时代码…...

uniapp form表单校验

公司的一个老项目&#xff0c;又要重新上架&#xff0c;uniapp一套代码&#xff0c;打包生成iOS端发布到App Store&#xff0c;安卓端发布到腾讯应用宝、OPPO、小米、华为、vivo&#xff0c;安卓各大应用市场上架要求不一样&#xff0c;可真麻烦啊 光一个表单校验&#xff0c;…...

构建RSS订阅机器人:观察者模式的实践与创新

在信息爆炸的时代&#xff0c;如何高效地获取和处理信息成为了一个重要的问题。RSS订阅机器人作为一种自动化工具&#xff0c;能够帮助我们从海量信息中筛选出我们感兴趣的内容。 一、RSS 是什么&#xff1f;观察者模式又是什么&#xff1f; RSS订阅机器人是一种能够自动订阅…...

芯片基础 | `wire`类型引发的学习

在Verilog中&#xff0c;wire类型是一种用于连接模块内部或模块之间的信号的数据类型。wire类型用于表示硬件中的物理连线&#xff0c;它可以传输任何类型的值&#xff08;如0、1、高阻态z等&#xff09;&#xff0c;但它在任何给定的时间点上只能有一个确定的值。 wire类型通…...

如何在AWS上构建Apache DolphinScheduler

引言 随着云计算技术的发展&#xff0c;Amazon Web Services (AWS) 作为一个开放的平台&#xff0c;一直在帮助开发者更好的在云上构建和使用开源软件&#xff0c;同时也与开源社区紧密合作&#xff0c;推动开源项目的发展。 本文主要探讨2024年值得关注的一些开源软件及其在…...

Quartus II 13.1添加新的FPGA器件库

最近需要用到Altera的一款MAX II 系列EPM240的FPGA芯片&#xff0c;所以需要给我的Quartus II 13.1添加新的器件库&#xff0c;在此记录一下过程。 1 下载所需的期间库 进入Inter官网&#xff0c;&#xff08;Altera已经被Inter收购&#xff09;https://www.intel.cn/content…...

【html】html的基础知识(面试重点)

一、如何理解HTML语义化 1、思考 A、在没有任何样式的前提下&#xff0c;将代码在浏览器打开&#xff0c;也能够结构清晰的展示出来。标题是标题、段落是段落、列表是列表。 B、便于搜索引擎优化。 2、参考答案 A、让人更容易读懂&#xff08;增加代码可读性&#xff09;。 B、…...

Java 网络编程(TCP编程 和 UDP编程)

1. Java 网络编程&#xff08;TCP编程 和 UDP编程&#xff09; 文章目录 1. Java 网络编程&#xff08;TCP编程 和 UDP编程&#xff09;2. 网络编程的概念3. IP 地址3.1 IP地址相关的&#xff1a;域名与DNS 4. 端口号&#xff08;port&#xff09;5. 通信协议5.1 通信协议相关的…...

STM32 | 看门狗+RTC源码解析

点击上方"蓝字"关注我们 作业 1、使用基本定时7,完成一个定时喂狗的程序 01、上节回顾 STM32 | 独立看门狗+RTC时间(第八天)02、定时器头文件 #ifndef __TIM_H#define __TIM_H​#include "stm32f4xx.h"​void Tim3_Init(void);void Tim7_Init(void);​…...

filebeat,kafka,clickhouse,ClickVisual搭建轻量级日志平台

springboot集成链路追踪 springboot版本 <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.6.3</version><relativePath/> <!-- lookup parent from…...

Django实战项目之进销存数据分析报表——第一天:Anaconda 环境搭建

引言 Anaconda是一个流行的Python和R语言的发行版&#xff0c;它包含了大量预安装的数据科学、机器学习库和科学计算工具。使用Anaconda可以轻松地创建隔离的环境&#xff0c;每个环境都可以有自己的一套库和Python版本&#xff0c;非常适合多项目开发。本文将指导你如何安装A…...

Linux部署Prometheus+Grafana

【Linux】PrometheusGrafana 一、Prometheus&#xff08;普罗米修斯&#xff09;1、Prometheus简述2、Prometheus特点3、Prometheus生态组件4、Prometheus工作原理 二、部署Prometheus1、系统架构2、部署Prometheus3、修改配置文件4、配置系统启动文件 三、部署 Node Exporter …...

【视频讲解】神经网络、Lasso回归、线性回归、随机森林、ARIMA股票价格时间序列预测|附代码数据

全文链接&#xff1a;https://tecdat.cn/?p37019 分析师&#xff1a;Haopeng Li 随着我国股票市场规模的不断扩大、制度的不断完善&#xff0c;它在金融市场中也成为了越来越不可或缺的一部分。 【视频讲解】神经网络、Lasso回归、线性回归、随机森林、ARIMA股票价格时间序列…...

低代码前端框架Amis全面教程

什么是Amis&#xff1f; 1.1 Amis的基本概念 Amis是一个基于JSON配置的前端低代码框架&#xff0c;由百度开源。它允许开发者通过简单的JSON配置文件来生成复杂的后台管理页面&#xff0c;从而大大减少了前端开发的工作量。Amis的核心理念是通过配置而非编码来实现页面的构建…...

Windows 如何安装和卸载 OneDrive?具体方法总结

卸载 OneDrive 有人想问 OneDrive 可以卸载吗&#xff1f;如果你不使用当然可以卸载&#xff0c;下面是安装和卸载 OneDrive 中的卸载应用具体操作步骤&#xff1a; 卸载 OneDrive 我们可以从设置面板中的应用选项进行卸载&#xff0c;打开设置面板之后选择应用&#xff0c;然…...

c# .net core中间件,生命周期

某些模块和处理程序具有存储在 Web.config 中的配置选项。但是在 ASP.NET Core 中&#xff0c;使用新配置模型取代了 Web.config。 HTTP 模块和处理程序如何工作 官网地址&#xff1a; 将 HTTP 处理程序和模块迁移到 ASP.NET Core 中间件 | Microsoft Learn 处理程序是&#xf…...

Spring后端框架复习总结

之前写的博客太杂,最近想把后端框架的知识点再系统的过一遍,主要是Spring Boot和Mybatis相关,带着自己的理解使用简短的话把一些问题总结一下,尤其是开发中和面试中的高频问题,基础知识点可以参考之前写java后端专栏,这篇不再赘述。 目录 Spring什么是AOP?底层原理?事务…...

基于Llama Index构建RAG应用

前言 Hello&#xff0c;大家好&#xff0c;我是GISer Liu&#x1f601;&#xff0c;一名热爱AI技术的GIS开发者&#xff0c;本文参与活动是2024 DataWhale AI夏令营&#xff1b;&#x1f632; 在本文中作者将通过&#xff1a; Gradio、Streamlit和LlamaIndex介绍 LlamaIndex 构…...

SSLRec代码分析

文章目录 encoder-models-general_cfautocf.py data_utilsdata_handler_general_cf.py输入输出说明使用方法 trainertuner.py encoder-models-general_cf autocf.py import torch as t # 导入PyTorch并重命名为t from torch import nn # 从PyTorch导入神经网络模块 import …...

第四节shell条件测试(1)(2)

一,命令执行结果判定 &&在命令执行后如果没有任何报错时会执行符号后面的动作 ||在命令执行后如果命令有报错会执行符号后的动作 示例: vim lee.sh #!/bin/bash ls /mnt/file &> /dev/null &&{echo /mnt/filr is not existecho no }||{echo /mnt/fi…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist

现象&#xff1a; android studio报错&#xff1a; [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决&#xff1a; 不要动CMakeLists.…...

图解JavaScript原型:原型链及其分析 | JavaScript图解

​​ 忽略该图的细节&#xff08;如内存地址值没有用二进制&#xff09; 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么&#xff1a;保存在堆中一块区域&#xff0c;同时在栈中有一块区域保存其在堆中的地址&#xff08;也就是我们通常说的该变量指向谁&…...