2013ACM/ICPC湘潭多省程序设计竞赛暨湘潭市第五届大学生程序设计竞赛

Hurry Up

题目链接：http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1175

解题思路：一道三分搜索的水题，可直接使用模板！

解题代码：

View Code

 1 // File Name: Hurry Up
 2 // Author: sheng
 3 // Created Time: 2013年05月12日 星期日 20时36分10秒
 4 
 5 #include <stdio.h>
 6 #include <string.h>
 7 #include <math.h>
 8 #include <iostream>
 9 using namespace std;
10 const double EPS = 1e-10;
11 
12 int x1, yy1, x2, yy2, vr, vt;     //y1为c++库函数的变量所以用yy1
13 
14 double calc(double x)
15 {
16     return (sqrt( (x1 - x) * (x1 - x) + yy1 * yy1)/ vr + sqrt( (x2 - x) * (x2 - x) + yy2 * yy2)/vt);
17 }
18 
19 double solve ()
20 {
21     double xx1 = (double)x1;
22     double xx2 = (double)x2;
23     if (xx1 > xx2)
24     {
25         double temp = xx1;
26         xx1 = xx2;
27         xx2 = temp;
28     }
29 //    printf ("%lf %lf\n", xx1, xx2);
30     double left = xx1, right = xx2;
31     double mid, midmid;
32     double mid_value, midmid_value;
33     while (left + EPS < right)
34     {
35         mid = (left + right)/2;
36         midmid = (mid + right)/2;
37         mid_value = calc(mid);
38         midmid_value = calc(midmid);
39     //    cout << mid_value <<" " << midmid_value << endl;
40         if (mid_value < midmid_value)
41             right = midmid;
42         else left = mid;
43     }
44     return calc(left);
45 }
46 
47 int main ()
48 {
49     int cas;
50     double ans1, ans2;
51     scanf ("%d", &cas);
52     while (cas--)
53     {
54         scanf ("%d%d%d%d%d%d", &x1, &yy1, &x2, &yy2, &vr, &vt);
55         ans1 = sqrt ( (x1 - x2) * (x1 - x2) + (yy1 - yy2) * (yy1 - yy2))/vr;
56         ans2 = solve();
57 //        printf ("%.2lf %.2lf\n", ans1, ans2);
58         printf ("%.2lf\n", ans1 > ans2 ? ans2 : ans1);
59     }
60     return 0;
61 }

Jack’s sequence

题目链接：http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1177

解题思路：此题我们只需找出我们序列中间最后一个“（”变成“）”之后依旧能与之前匹配的位置然后直接输出就可以了，具体方法看代码吧！

解题代码：

View Code

 1 // File Name:  Jack’s sequence 1177.cpp
 2 // Author: sheng
 3 // Created Time: 2013年05月12日 星期日 21时58分06秒
 4 
 5 #include <stdio.h>
 6 #include <iostream>
 7 #include <string.h>
 8 using namespace std;
 9 
10 const int max_n = 10010;
11 char bg[max_n];
12 int sign[max_n];
13 
14 int main ()
15 {
16     int n, tag;
17     int cnt;
18     int cun;
19     scanf ("%d", &n);
20     getchar();
21     while (n--)
22     {
23         cnt = cun = 0;
24         scanf ("%s", bg);
25         memset (sign, 0, sizeof (sign));
26         int len = strlen (bg);
27         for (int i = 0; i < len; i ++)
28         {
29             if (bg[i] == '(')
30             {
31                 cnt ++;
32                 tag = 0;
33             }
34             else
35             {
36                 cnt --;
37                 if (cnt > 0 && !tag)
38                     sign[cun++] = tag = i - 1;
39             }
40         }
41         tag = 0;
42         cnt = 0;
43         for (int i = cun - 1; i >= 0; i --)
44         {
45             if ( sign[i])
46             {
47                 tag = sign[i];
48                 break;
49             }
50         }
51         if (!tag)
52         {
53             cout << "No solution\n";
54             continue;
55         }
56         for (int i = 0; i < tag; i ++)
57         {
58             cout << bg[i];
59             if (bg[i] == '(')
60                 cnt ++;
61             else cnt --;
62         }
63         cnt --;
64         cout << ")";
65         for (int i = 0; i < (len - cnt - tag)/2; i ++)
66             cout << "(";
67         for (int i = 0; i < (len - tag + cnt)/2; i ++)
68             cout << ")";
69         cout << endl;
70     }
71     return 0;
72 }