没有自己的网站做百度竞价,中国建设企业银行官网站,沈丘做网站去哪里,网站seo内链建设目录
HDU1005——Number Sequence
题目描述
超时代码
代码思路
正确代码
代码思路
HDU1006——Tick and Tick
题目描述
运行代码
代码思路
HDU1007——Quoit Design
题目描述
运行代码
代码思路
HDU1005——Number Sequence
题目描述
Problem - 1005 超时代码…目录
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;
}
代码思路 函数 f: 定义了三个变量 f1, f2, 和 fn 分别代表序列中的前两个值和当前计算的值。如果 n 是1或者2函数直接返回1这可以看作是序列的初始条件。当 n 大于2时进入一个循环从3到 n 每次迭代计算 fn 为 A 乘以 f1 加上 B 乘以 f2 的结果并对7取模。然后更新 f1 和 f2 的值以便下一次迭代。循环结束后返回 fn。 主函数 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;}
}
代码思路 初始化序列数组f[]用来存储序列的值。length和st变量分别用于记录循环节的长度和循环节开始的位置。 计算序列 使用循环从第三项开始计算序列的值直到检测到循环节或者达到预设的上限这里是100项。每一项计算使用了预先计算的乘法结果prev1Mult和prev2Mult这有助于减少重复计算提高效率。 检测循环节函数finda()通过二分查找算法检测序列中的循环节。一旦找到重复的模式即连续两项相同它会记录循环节的开始位置st和长度length。 输出结果 根据用户输入的nn如果nn小于循环节开始的位置直接输出f[n]。如果nn大于等于循环节开始的位置则输出循环节中对应位置的值即f[(n - st) % length st]。
这种算法特别适用于计算周期性出现的序列通过检测循环节可以极大地优化计算过程尤其是在需要频繁查询大索引位置的场景下。
HDU1006——Tick and Tick
题目描述
Problem - 1006 运行代码
#include iostream
#include stdio.h
#include algorithmconst 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;
}
代码思路 常量 sm、sh、mh分别代表三个假想的“指针”小指针、特殊指针和中等指针的速度每分钟的度数。t_sm、t_sh、t_mh分别表示这些“指针”完成一个完整周期所需的时间以分钟计。 输入处理 程序读取一个值D这个值代表任意两个“指针”要被认为是“接近”的最大角度距离。如果D 0意味着“指针”必须完全重合结果总是100%。如果D -1则表示输入结束。 计算初始边界 对于每个“指针”它计算第一次它们会处于离起点DD度内的时刻(b_sm、b_sh、b_mh)。同样它也计算第一次它们不会处于离起点DD度内的时刻(e_sm、e_sh、e_mh)。 查找重叠区间 程序使用嵌套循环来遍历所有可能的时刻这时所有的三个“指针”可以同时处于彼此DD度内。根据当前迭代更新边界(b1、b2、b3)和端点(e1、e2、e3)。它使用Min和Max函数来找到所有“指针”都接近的区间的开始和结束。它在sum中累积这些区间的持续时间。 输出处理完所有区间后它计算出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来解决具体步骤如下 定义结构体 Point 存储每个点的坐标。 比较函数 cmpX 和 cmpY 分别用于按照 x 坐标和 y 坐标排序点。 距离函数 dist 计算两点之间的欧几里得距离。 递归函数 findClosestPair 是核心部分它接收左边界和右边界作为参数表示要处理的点集范围。 如果范围内只有一个点或没有点返回一个很大的值 MAXX 表示没有距离可言。如果范围内正好有两个点直接计算并返回这两个点的距离。否则将点集分为左右两半递归地在两边找到最小距离。然后检查中线两侧的点是否包含更近的点对。为此收集所有与中线距离小于目前最小距离的点并按 y 坐标排序。在这个已排序的子集中检查每一对相邻点的 y 坐标差小于目前最小距离的点对计算它们之间的距离并更新最小距离。 主函数 main 读取点集数量 n 和每个点的坐标然后调用 findClosestPair 函数最后输出最近点对之间距离的一半题目可能要求输出半径即最近点对距离的一半保留两位小数。
这种方法的时间复杂度为 O(n log n)其中 n 是点的数量。这是因为每次递归调用处理一半的点同时还需要对子集进行排序。空间复杂度为 O(n)因为需要额外的空间存储排序后的点和临时数组。
