http://acm.hdu.edu.cn/showproblem.php?pid=1006

?

　　題意不多說，這題是求一個概率。剛開始的時候我并沒有思路，想了頗久，最后還是打算看看題解。網上的題解不好理解，但是當我看到一個找三種針之間速度的差距就可以計算出來，我就突然靈機一動，想到了先計算出兩種針間每秒的變化速度，然后就像小學的追逐問題一樣，計算出時間。一天是24小時，但是我們只需要計算前12個小時就可以了。

　　然后，將計算出的時間儲存起來，變成區間，最后就把問題轉變為區間取交的問題了！

　　運行的時間不會太長，15ms，跟網上某些說跟精度有關的算法不一樣，我的是直接計算，所以精度不會影響結果！

代碼如下（1y）：

View Code 1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cmath> 5 6 // degrees per second 7 const double h_m = (360.0 - 30.0) / 3600; 8 const double h_s = (360.0 * 60 - 30.0) / 3600; 9 const double m_s = (360.0 * 60 - 360.0) / 3600; 10 const double maxt = 43200; 11 const double eps = 1e-6; 12 const int maxn = 800; 13 14 double max2(double a, double b){return a > b ? a : b;} 15 double min2(double a, double b){return a < b ? a : b;} 16 17 struct line{ 18 double s, t; 19 }l1[maxn], l2[maxn], l3[maxn], ll[maxn << 2]; 20 21 bool in[maxn]; 22 23 bool cmp(line a, line b){ 24 if (fabs(a.s - b.s) > eps) return a.s < b.s; 25 return a.t < b.t; 26 } 27 28 bool nocross(line a, line b){ 29 return a.s > b.t || b.s > a.t; 30 } 31 // 區間取交 sections intersection 32 void calm(line a[], int n, line b[], int m, line c[], int &k){ 33 k = 0; 34 if (!n || !m) return; 35 int i = 0, j = 0, w; 36 while (i < n && j < m){ 37 if (a[i].s < b[j].s){ 38 for (w = j; b[w].s < a[i].t && w < m; w++){ 39 c[k].s = b[w].s; 40 c[k].t = min2(a[i].t, b[w].t); 41 k++; 42 } 43 j = w; 44 i++; 45 if (j && (!nocross(a[i], b[j - 1]))) j--; 46 } 47 else { 48 for (w = i; a[w].s < b[j].t && w < n; w++){ 49 c[k].s = a[w].s; 50 c[k].t = min2(a[w].t, b[j].t); 51 k++; 52 } 53 i = w; 54 j++; 55 if (i && (!nocross(a[i - 1], b[j]))) i--; 56 } 57 } 58 } 59 60 // deal with the problem 61 double cal(double k){ 62 int T = 0; 63 bool ref = true; 64 double s, t; 65 int n1, n2, n3, n; 66 67 n1 = n2 = n3 = 0; 68 while (ref){ 69 ref = false; 70 s = 360.0 * T + k; 71 t = 360.0 * (T + 1) - k; 72 73 if (s / h_m < maxt){ 74 l1[n1].s = s / h_m; 75 l1[n1].t = t / h_m; 76 if (t / h_m > maxt) l1[n1].t = maxt; 77 n1++; 78 ref = true; 79 } 80 if (s / h_s < maxt){ 81 l2[n2].s = s / h_s; 82 l2[n2].t = t / h_s; 83 if (t / h_s > maxt) l2[n2].t = maxt; 84 n2++; 85 ref = true; 86 } 87 if (s / m_s < maxt){ 88 l3[n3].s = s / m_s; 89 l3[n3].t = t / m_s; 90 if (t / m_s > maxt) l3[n3].t = maxt; 91 n3++; 92 ref = true; 93 } 94 T++; 95 } 96 calm(l1, n1, l2, n2, ll, n); 97 calm(l3, n3, ll, n, l1, n1); // calculate the intersection of three sections 98 99 double sum = 0; 100 for (int i = 0; i < n1; i++){ 101 sum += l1[i].t - l1[i].s; 102 } 103 // sum up the sections 104 105 return sum * 100 / maxt; 106 } 107 108 109 bool deal(){ 110 double D; 111 112 scanf("%lf", &D); 113 if (D < -0.5) return false; 114 printf("%.3f\n", cal(D)); 115 116 return true; 117 } 118 119 int main(){ 120 #ifndef ONLINE_JUDGE 121 freopen("in", "r", stdin); 122 printf("h_m %f\nh_s %f\nm_s %f\n\n", h_m, h_s, m_s); 123 #endif 124 while (deal()); 125 126 return 0; 127 }

?

?

——written by Lyon

轉載于:https://www.cnblogs.com/LyonLys/archive/2012/08/15/hdu_1006_Lyon.html

總結

以上是生活随笔為你收集整理的hdu 1006 Tick and Tick的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。