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:

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

2. 主函数 main:

   • 无限循环读取用户输入的 A, B, 和 n 值，直到遇到所有为0的终止条件。
   • 调用 f 函数并打印结果。
   • 当输入 A, B, 和 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[]用来存储序列的值。length和st变量分别用于记录循环节的长度和循环节开始的位置。

2. 计算序列：

   • 使用循环从第三项开始计算序列的值，直到检测到循环节或者达到预设的上限（这里是100项）。
   • 每一项计算使用了预先计算的乘法结果（prev1Mult和prev2Mult），这有助于减少重复计算，提高效率。

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. 常量：

   • sm、sh、mh分别代表三个假想的“指针”（小指针、特殊指针和中等指针）的速度（每分钟的度数）。
   • t_sm、t_sh、t_mh分别表示这些“指针”完成一个完整周期所需的时间（以分钟计）。

2. 输入处理：

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

3. 计算初始边界：

   • 对于每个“指针”，它计算第一次它们会处于离起点DD度内的时刻(b_sm、b_sh、b_mh)。
   • 同样，它也计算第一次它们不会处于离起点DD度内的时刻(e_sm、e_sh、e_mh)。

4. 查找重叠区间：

   • 程序使用嵌套循环来遍历所有可能的时刻，这时所有的三个“指针”可以同时处于彼此DD度内。
   • 根据当前迭代，更新边界(b1、b2、b3)和端点(e1、e2、e3)。
   • 它使用Min和Max函数来找到所有“指针”都接近的区间的开始和结束。
   • 它在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. 比较函数 cmpX 和 cmpY 分别用于按照 x 坐标和 y 坐标排序点。

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

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

   • 如果范围内只有一个点或没有点，返回一个很大的值 MAXX 表示没有距离可言。
   • 如果范围内正好有两个点，直接计算并返回这两个点的距离。
   • 否则，将点集分为左右两半，递归地在两边找到最小距离。
   • 然后，检查中线两侧的点是否包含更近的点对。为此，收集所有与中线距离小于目前最小距离的点，并按 y 坐标排序。
   • 在这个已排序的子集中，检查每一对相邻点的 y 坐标差小于目前最小距离的点对，计算它们之间的距离，并更新最小距离。

5. 主函数 main 读取点集数量 n 和每个点的坐标，然后调用 findClosestPair 函数，最后输出最近点对之间距离的一半（题目可能要求输出半径，即最近点对距离的一半），保留两位小数。

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