网站空间的申请,手机网站建设wap,校园网站模板下载,elision豪华级创意企业wordpress今天第二天#xff0c;主要练习二分和枚举。其实我突然发现#xff0c;当做题突然卡主的时候#xff0c;不妨想想今天练习的是什么内容…… 传送门http://acm.hit.edu.cn/hoj/contest/view?id100128 Problem A#xff1a;Crossed Ladders 此题导致本人郁闷一整天。。从哪说…今天第二天主要练习二分和枚举。其实我突然发现当做题突然卡主的时候不妨想想今天练习的是什么内容…… 传送门http://acm.hit.edu.cn/hoj/contest/view?id100128 Problem ACrossed Ladders 此题导致本人郁闷一整天。。从哪说起呢 看到这道题觉得很像初中数学的平面几何抄起家伙开始列方程最初的想法就是把表达式写出来之后程序里几句话搞定。 最后方程是出来了但是在尝试整理成x形式的时候失败了。。就连下午和同学出去蹦跶都还在想这道题……终于在晚饭之后数次尝试无果的情况下放弃解方程感叹数学才70多分的孩子还是换一种方法把。。询问度娘后发现这是一道很经典甚至古老的数学题wikipedia上一句话令在下恍然大明白忘了原句是啥了大意是某方程可以用逼近的方式得出解……然后思路就哗哗的呀想起今天的主题想起初中的时候二分逼近求解的时候我还写过一个用二分法解一元二次方程的经历然后就……无语了。哎此题还是借了度娘一臂之力甚是惭愧…… 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 BPrime Palindromes 这道题是hoj1004我们的高级语言程序设计课当时的lab1或者是lab2……记不清了所以有现成的代码很猥琐地直接贴了上去。。只不过比1004的时间限制更严格好像佳男学长改之后是3s之前是1s。 思路就是生成回文数然后再判断是否是素数判断素数从3开始只判断奇数试到sqrt我是在生成回文数的时候就跳过了偶数。这样基本就完全无压力了0.4s就完全可以给出输入 5 1000000000的输出。这个代码是当时写的其实我都很不好意思拿出来……生成回文数的地方很奇葩很暴力完全可以写出既简洁又高效的代码的……哎望各位看官莫笑。 1 /*This Code is Submitted by acehypocrisy for Problem 4000087 at 2012-01-18 22:26:01*/ 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 n0;15 result[0]5;16 result[1]7;17 result[2]11;18 n3;19 20 for (i11;i19;i12){21 for (i20;i29;i2){22 if (i1%20)23 continue;24 result[n]i1*100i2*10i1;25 n;26 }27 }28 29 for (i11;i19;i12){30 for (i20;i29;i2){31 for (i30;i39;i3){32 if (i1%20)33 continue;34 result[n]i1*10000i2*1000i3*100i2*10i1;35 n;36 }37 }38 }39 40 for (i11;i19;i12){41 for (i20;i29;i2){42 for (i30;i39;i3){43 for (i40;i49;i4){44 if (i1%20)45 continue;46 result[n]i1*1000000i2*100000i3*10000i4*1000i3*100i2*10i1;47 n;48 }49 }50 }51 }52 53 for (i11;i19;i12){54 for (i20;i29;i2){55 for (i30;i39;i3){56 for (i40;i49;i4){57 for (i50;i59;i5){58 result[n]i1*100000000i2*10000000i3*1000000i4*100000i5*10000i4*1000i3*100i2*10i1;59 n;60 }61 }62 }63 }64 }65 66 67 for (i0;in;i){68 if (result[i]a||result[i]b)69 continue;70 int k,jsqrt(result[i]);71 int flag0;72 for (k3;kj;k2){73 if (result[i]%k0){74 flag1;75 break;76 }77 }78 if (flag1)79 continue;80 printf(%d\n,result[i]);81 }82 83 return 0;84 } Problem CFibonacci Extended 高级一点的斐波那契数列在F(n-1)和F(n-2)前面多了系数A和B。而且是给出FnF0来求F1也不太麻烦就是在数据类型上要多做注意。我的两次WA全都献给long long了。 解题思想的关键部分就是用一个数组Fn[41][2]来保存Fn用F1和F0来表示时二者的系数。例如F0 0 * F1 1 * F0所以Fn[0][0] 0, Fn[0][1] 1以此类推Fn[i][0]存放的是F1的系数[1]存放的是F0的系数。题目中给出N40所以要有41个空间。最后就可以算出F1了。 要注意的是long long啊。。一定要注意呀。。。这道题居然猥琐的连系数都要用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 DMinimum Area 和整数点相关的问题最开始暴力枚举奉献了一次TLE然后学乖了用二分法。。。 其实核心问题就是如何寻找最小的C中间统计整数点的时候用了一小点点的“优化”虽然有点可有可无效果一点都不明显……就是当当前统计的那一列的点只有一个的时候他往后的所有列的点就全是1了这个时候加一下就可以break了。。最后微积分学告诉我们答案应该是C * lnC - C 1 ……库函数里的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 } 现在正好是000 恩。。。明天的题据说用java更给力明天的题明天再说吧。。。感谢老妈陪我到凌晨。。。转载于:https://www.cnblogs.com/tuesday/archive/2012/01/20/2327688.html
