2012 winter training @HIT Day 2 解题报告
今天第二天，主要練習二分和枚舉。其實我突然發(fā)現(xiàn)，當做題突然卡主的時候，不妨想想今天練習的是什么內(nèi)容……
傳送門http://acm.hit.edu.cn/hoj/contest/view?id=100128
?
Problem A：Crossed Ladders
此題導致本人郁悶一整天。。從哪說起呢 看到這道題覺得很像初中數(shù)學的平面幾何，抄起家伙開始列方程，最初的想法就是把表達式寫出來之后程序里幾句話搞定。
最后方程是出來了，但是在嘗試整理成x=？形式的時候失敗了。。就連下午和同學出去蹦跶都還在想這道題……終于在晚飯之后數(shù)次嘗試無果的情況下放棄解方程，感嘆數(shù)學才70多分的孩子還是換一種方法把。。詢問度娘后發(fā)現(xiàn)這是一道很經(jīng)典甚至古老的數(shù)學題，wikipedia上一句話令在下恍然大明白！忘了原句是啥了，大意是：某方程可以用逼近的方式得出解……然后思路就嘩嘩的呀，想起今天的主題，想起初中的時候二分逼近求解的時候我還寫過一個用二分法解一元二次方程的經(jīng)歷，然后就……無語了。哎，此題還是借了度娘一臂之力，甚是慚愧……
1 /*This Code is Submitted by acehypocrisy for Problem 4000086 at 2012-01-19 22:45:39*/2 #include <stdio.h>
3 #include <cmath>
4 #include <stdlib.h>
5
6 int main()
7 {
8 double x, y, c;
9 while (scanf("%lf %lf %lf", &x, &y, &c) == 3){
10 double w, wMax, wMin;
11 wMax = ((x < y) ? x : y);
12 wMin = 0;
13 w = wMax / 2;
14 double A = sqrt(x * x - w * w);
15 double B = sqrt(y * y - w * w);
16 while(fabs(A * B / (A + B) - c) > 0.0001){
17 if (A * B / (A + B) - c < 0){
18 wMax = w;
19 }else{
20 wMin = w;
21 }
22 w = (wMax + wMin) / 2;
23 A = sqrt(x * x - w * w);
24 B = sqrt(y * y - w * w);
25 }
26 printf("%.3f\n", w);
27 }
28 return 0;
29 }
?
Problem B：Prime Palindromes
這道題是hoj1004，我們的高級語言程序設(shè)計課當時的lab1（或者是lab2……記不清了），所以有現(xiàn)成的代碼，很猥瑣地直接貼了上去。。只不過比1004的時間限制更嚴格，好像佳男學長改之后是3s，之前是1s。
思路就是生成回文數(shù)然后再判斷是否是素數(shù)，判斷素數(shù)從3開始只判斷奇數(shù)，試到<=sqrt，我是在生成回文數(shù)的時候就跳過了偶數(shù)。這樣基本就完全無壓力了，0.4s就完全可以給出輸入 5 1000000000的輸出。
這個代碼是當時寫的，其實我都很不好意思拿出來……生成回文數(shù)的地方很奇葩很暴力，完全可以寫出既簡潔又高效的代碼的……哎，望各位看官莫笑。
2 #include <stdio.h>
3 #include <stdlib.h>
4 #include <math.h>
5
6 int main(int argc, char *argv[])
7 {
8 unsigned int a,b,result[100000];
9 scanf("%u %u",&a,&b);
10
11
12 int i,i1,i2,i3,i4,i5;
13
14 int n=0;
15 result[0]=5;
16 result[1]=7;
17 result[2]=11;
18 n=3;
19
20 for (i1=1;i1<=9;i1+=2){
21 for (i2=0;i2<=9;i2++){
22 if (i1%2==0)
23 continue;
24 result[n]=i1*100+i2*10+i1;
25 n++;
26 }
27 }
28
29 for (i1=1;i1<=9;i1+=2){
30 for (i2=0;i2<=9;i2++){
31 for (i3=0;i3<=9;i3++){
32 if (i1%2==0)
33 continue;
34 result[n]=i1*10000+i2*1000+i3*100+i2*10+i1;
35 n++;
36 }
37 }
38 }
39
40 for (i1=1;i1<=9;i1+=2){
41 for (i2=0;i2<=9;i2++){
42 for (i3=0;i3<=9;i3++){
43 for (i4=0;i4<=9;i4++){
44 if (i1%2==0)
45 continue;
46 result[n]=i1*1000000+i2*100000+i3*10000+i4*1000+i3*100+i2*10+i1;
47 n++;
48 }
49 }
50 }
51 }
52
53 for (i1=1;i1<=9;i1+=2){
54 for (i2=0;i2<=9;i2++){
55 for (i3=0;i3<=9;i3++){
56 for (i4=0;i4<=9;i4++){
57 for (i5=0;i5<=9;i5++){
58 result[n]=i1*100000000+i2*10000000+i3*1000000+i4*100000+i5*10000+i4*1000+i3*100+i2*10+i1;
59 n++;
60 }
61 }
62 }
63 }
64 }
65
66
67 for (i=0;i<n;i++){
68 if (result[i]<a||result[i]>b)
69 continue;
70 int k,j=sqrt(result[i]);
71 int flag=0;
72 for (k=3;k<=j;k+=2){
73 if (result[i]%k==0){
74 flag=1;
75 break;
76 }
77 }
78 if (flag==1)
79 continue;
80 printf("%d\n",result[i]);
81 }
82
83 return 0;
84 }
Problem C：Fibonacci Extended
高級一點的斐波那契數(shù)列，在F(n-1)和F(n-2)前面多了系數(shù)A和B。而且是給出Fn，F0來求F1，也不太麻煩，就是在數(shù)據(jù)類型上要多做注意。我的兩次WA全都獻給long long了。
解題思想的關(guān)鍵部分就是用一個數(shù)組Fn[41][2]來保存Fn用F1和F0來表示時二者的系數(shù)。例如，F0 =?0 * F1 + 1 * F0，所以Fn[0][0] = 0, Fn[0][1] = 1，以此類推，Fn[i][0]存放的是F1的系數(shù)，[1]存放的是F0的系數(shù)。題目中給出N<=40，所以要有41個空間。最后就可以算出F1了。
要注意的是long long啊。。一定要注意呀。。。這道題居然猥瑣的連系數(shù)都要用longlong來存，這樣int情何以堪……
1 /*This Code is Submitted by acehypocrisy for Problem 4000088 at 2012-01-19 22:10:56*/2 #include <stdio.h>
3
4 long long Fn[41][2];
5
6 int main()
7 {
8 int A, B, N, F0;
9 long long FN;
10 while (scanf("%d %d %d %d %lld", &A, &B, &N, &F0, &FN) == 5){
11 int i;
12 Fn[0][0] = 0;
13 Fn[0][1] = 1;
14 Fn[1][0] = 1;
15 Fn[1][1] = 0;
16 Fn[2][0] = A;
17 Fn[2][1] = B;
18 for(i = 3; i <= N; i++){
19 Fn[i][0] = A * Fn[i - 1][0] + B * Fn[i - 2][0];
20 Fn[i][1] = A * Fn[i - 1][1] + B * Fn[i - 2][1];
21 }
22 int F1 = (FN - Fn[N][1] * F0) / Fn[N][0];
23 printf("%d\n", F1);
24 }
25 return 0;
26 }
27
?
Problem D：Minimum Area
和整數(shù)點相關(guān)的問題，最開始暴力枚舉奉獻了一次TLE，然后學乖了用二分法。。。
其實核心問題就是如何尋找最小的C，中間統(tǒng)計整數(shù)點的時候用了一小點點的“優(yōu)化”（雖然有點可有可無，效果一點都不明顯……），就是當當前統(tǒng)計的那一列的點只有一個的時候，他往后的所有列的點就全是1了，這個時候加一下就可以break了。。最后微積分學告訴我們，答案應(yīng)該是C * lnC - C + 1 ……庫函數(shù)里的log（）就是以e為底的。
?
1 /*This Code is Submitted by acehypocrisy for Problem 4000089 at 2012-01-19 21:27:36*/2 #include <stdio.h>
3 #include <math.h>
4
5 int main()
6 {
7 int T;
8 scanf("%d", &T);
9 while(T--){
10 int N;
11 scanf("%d", &N);
12 int C, Cmin, Cmax, count;
13 Cmax = N;
14 Cmin = 0;
15 while (Cmax - Cmin > 1){
16 C = (Cmax + Cmin) / 2;
17 count = 0;
18 for (int j = 1; j <= C; j++){
19 count += C / j;
20 if (C / j == 1){
21 count += C - j;
22 break;
23 }
24 }
25 if(count >= N){
26 Cmax = C;
27 }else{
28 Cmin = C;
29 }
30 }
31 C = Cmax;
32 double result = C * log(C) - C + 1;
33 printf("%.4f\n", result);
34 }
35 return 0;
36 }
現(xiàn)在正好是0：00 恩。。。明天的題據(jù)說用java更給力？明天的題明天再說吧。。。感謝老媽陪我到凌晨。。。
轉(zhuǎn)載于:https://www.cnblogs.com/tuesday/archive/2012/01/20/2327688.html
總結(jié)
以上是生活随笔為你收集整理的2012 winter training @HIT Day 2 解题报告的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 闰年的判断方法 和 当目前为止你生存的
- 下一篇： 物理外挂4G秒变5G！华为Mate 50