目錄

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. 函數(shù) f:

   • 定義了三個變量?f1,?f2, 和?fn?分別代表序列中的前兩個值和當前計算的值。
   • 如果?n?是1或者2，函數(shù)直接返回1，這可以看作是序列的初始條件。
   • 當?n?大于2時，進入一個循環(huán)，從3到?n：
     • 每次迭代計算?fn?為?A?乘以?f1?加上?B?乘以?f2?的結(jié)果，并對7取模。
     • 然后更新?f1?和?f2?的值以便下一次迭代。
   • 循環(huán)結(jié)束后，返回?fn。

2. 主函數(shù) main:

   • 無限循環(huán)讀取用戶輸入的?A,?B, 和?n?值，直到遇到所有為0的終止條件。
   • 調(diào)用?f?函數(shù)并打印結(jié)果。
   • 當輸入?A,?B, 和?n?全部為0時，循環(huán)結(jié)束，程序退出。

這個結(jié)果最后是超時運算

正確代碼

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;
int f[100];
int length, st;  // 循環(huán)節(jié)長度和循環(huán)開始的標記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++) {// 預(yù)先計算乘法結(jié)果，避免重復(fù)計算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. 初始化序列：數(shù)組f[]用來存儲序列的值。length和st變量分別用于記錄循環(huán)節(jié)的長度和循環(huán)節(jié)開始的位置。

2. 計算序列：

   • 使用循環(huán)從第三項開始計算序列的值，直到檢測到循環(huán)節(jié)或者達到預(yù)設(shè)的上限（這里是100項）。
   • 每一項計算使用了預(yù)先計算的乘法結(jié)果（prev1Mult和prev2Mult），這有助于減少重復(fù)計算，提高效率。

3. 檢測循環(huán)節(jié)：函數(shù)finda()通過二分查找算法檢測序列中的循環(huán)節(jié)。一旦找到重復(fù)的模式（即連續(xù)兩項相同），它會記錄循環(huán)節(jié)的開始位置（st）和長度（length）。

4. 輸出結(jié)果：

   • 根據(jù)用戶輸入的nn，如果nn小于循環(huán)節(jié)開始的位置，直接輸出f[n]。
   • 如果nn大于等于循環(huán)節(jié)開始的位置，則輸出循環(huán)節(jié)中對應(yīng)位置的值，即f[(n - st) % length + st]。

這種算法特別適用于計算周期性出現(xiàn)的序列，通過檢測循環(huán)節(jié)可以極大地優(yōu)化計算過程，尤其是在需要頻繁查詢大索引位置的場景下。

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;// 定義最大值最小值函數(shù)
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;// 使用簡潔的循環(huán)條件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分別代表三個假想的“指針”（小指針、特殊指針和中等指針）的速度（每分鐘的度數(shù)）。
   • t_sm、t_sh、t_mh分別表示這些“指針”完成一個完整周期所需的時間（以分鐘計）。

2. 輸入處理：

   • 程序讀取一個值D，這個值代表任意兩個“指針”要被認為是“接近”的最大角度距離。
   • 如果D = 0，意味著“指針”必須完全重合，結(jié)果總是100%。
   • 如果D = -1，則表示輸入結(jié)束。

3. 計算初始邊界：

   • 對于每個“指針”，它計算第一次它們會處于離起點DD度內(nèi)的時刻(b_sm、b_sh、b_mh)。
   • 同樣，它也計算第一次它們不會處于離起點DD度內(nèi)的時刻(e_sm、e_sh、e_mh)。

4. 查找重疊區(qū)間：

   • 程序使用嵌套循環(huán)來遍歷所有可能的時刻，這時所有的三個“指針”可以同時處于彼此DD度內(nèi)。
   • 根據(jù)當前迭代，更新邊界(b1、b2、b3)和端點(e1、e2、e3)。
   • 它使用Min和Max函數(shù)來找到所有“指針”都接近的區(qū)間的開始和結(jié)束。
   • 它在sum中累積這些區(qū)間的持續(xù)時間。

5. 輸出：處理完所有區(qū)間后，它計算出12小時總時段內(nèi)所有“指針”處于DD度內(nèi)的百分比時間。

高效地找到所有三個進程符合給定條件的重疊區(qū)間，即使它們有不同的速度和周期。

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. 定義結(jié)構(gòu)體 Point 存儲每個點的坐標。

2. 比較函數(shù) cmpX 和 cmpY 分別用于按照 x 坐標和 y 坐標排序點。

3. 距離函數(shù) dist 計算兩點之間的歐幾里得距離。

4. 遞歸函數(shù) findClosestPair 是核心部分，它接收左邊界和右邊界作為參數(shù)，表示要處理的點集范圍。

   • 如果范圍內(nèi)只有一個點或沒有點，返回一個很大的值?MAXX?表示沒有距離可言。
   • 如果范圍內(nèi)正好有兩個點，直接計算并返回這兩個點的距離。
   • 否則，將點集分為左右兩半，遞歸地在兩邊找到最小距離。
   • 然后，檢查中線兩側(cè)的點是否包含更近的點對。為此，收集所有與中線距離小于目前最小距離的點，并按 y 坐標排序。
   • 在這個已排序的子集中，檢查每一對相鄰點的 y 坐標差小于目前最小距離的點對，計算它們之間的距離，并更新最小距離。

5. 主函數(shù) main 讀取點集數(shù)量 n 和每個點的坐標，然后調(diào)用 findClosestPair 函數(shù)，最后輸出最近點對之間距離的一半（題目可能要求輸出半徑，即最近點對距離的一半），保留兩位小數(shù)。

這種方法的時間復(fù)雜度為 O(n log n)，其中 n 是點的數(shù)量。這是因為每次遞歸調(diào)用處理一半的點，同時還需要對子集進行排序。空間復(fù)雜度為 O(n)，因為需要額外的空間存儲排序后的點和臨時數(shù)組。