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

时间：2024-07-18 13:28:34

目录

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;
        else
            cout << 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)，因为需要额外的空间存储排序后的点和临时数组。

相关文章