《2012ahut acmicpc选拔赛题目讲评》由会员分享，可在线阅读，更多相关《2012ahut acmicpc选拔赛题目讲评（25页珍藏版）》请在金锄头文库上搜索。
1、 2012-12-13一、等比数列之和 (简单题) Description 问题描述已知等比数列第1,2项，求其前n项之和Input Format 输入格式输入数据有多组，每组占一行，由3个实数组成，分别表示a1,a2,nOutput Format 输出格式对于每组输入数据，输出一行Hint 注释所有数据均为整形基本思路一：定义一个sum表示和，利用循环依次求出前n项，累加放入sum中C语言实现 ：#include int main() int sum=0,i,ai,a1,a2,n,q;while (scanf(“%d%d%d“,sum=a1;ai=a1;if (n=1) printf(“%d
2、n“,a1);elsefor (i=2;i #include int main() int a1,a2,n;int q,s,a,i;while(scanf(“%d %d %d“,if(q=1) s=n*a1;else s=a1*(1-(int)pow(q,n)/(1-q);printf(“%dn“,s); return 0; C语言实现 ：两种不同思路给我们的启示：第一种方法简单易实现，算出每一项的值再累加，最后得 到总和结果，就算你没学过等比数列求和公式都能写出这 个思路。该方法使用了一个循环，所以时间复杂度为 O(n)。第二种方法使用了数学公式，使得运算过程大大简化，不 需要使用循环，直接
3、一个表达式就能得到正确结果，时间 复杂度为O(1)，显然，运用公式对算法做出了很大的改进 ，这也告诉了我们：必须要学好数学！因为有很多这样的 情况公式不是我们学过的，而是需要我们自己来推导的！ 你如果没法推出使问题算法简单化的公式，可能你写出的 程序就要比别人多花很多时间才能得到答案或因为太占用 时间而根本得不到答案。Description 问题描述蜗牛在井底，井深n厘米；蜗牛每分钟上爬u厘米，接下来一分 钟下掉d厘米。重复这一过程直到爬出井。求爬出井需多长时间。 Input Format 输入格式下面存在多组测试数据。每一行包括3个正数分别代表n,u和d。 你可以认为dx，我们认为这最后一段
4、仍然是 花了一分钟。蜗牛肯定会爬出井，也就是ud。所有数据均为整数！二、顽强的蜗牛 (简单题)最易理解的思路：用代码模拟整个蜗牛爬行的过程#include int main() int s,d,u,n,t;while (scanf(“%d%d%d“,t=0; /s代表蜗牛已爬行的距离 t表示已用的时间while (s #include int main() double x1,y1,x2,y2,x3,y3;double d1,d2,d3;double min;while(scanf(“%lf%lf%lf%lf%lf%lf“,d2=sqrt(x2*x2+y2*y2);d3=sqrt(x3*x3+
5、y3*y3); if(d1d3)min=d3;printf(“%.2fn“,min); return 0; C语言实现代码：四、WarCraft (难题)Description 问题描述N元钱，购买150,200,350元三件商品，最少能剩余多少钱Input Format 输入格式第一行整数T(1 int main() int t,n,m,k;scanf(“%d“,while(t-)scanf(“%d“,if (n=50) k=k-50; 只要别把m给弄成负数了而且省的钱数大于50，就用一个150的换一个200的保证多利用50块钱。printf(“%dn“,k);return 0; 五、Loo
6、k Easy (中等题)Description 问题描述 F0=4,F1=7,F2=9,Fn=Fn-1+Fn-2+Fn-3(nint main() int f1005,i,n;f0=4;f1=2;f2=4;for (i=3;iint main() int t,n,m,i;scanf (“%d“,while (t-)scanf (“%d%d“,if (n%(m+1)printf(“firstn“);elseprintf(“secondn“);return 0; C语言实现代码：Description 问题描述 有一电梯共M层，刚开始时你在第一级，若每次只能上一层或 三层，要上第M层，共有多少种方法？ Input Format 输入格式 第一行整数N，表示测试样例的个数，然后是N行数据，每行 包含一个整数M（1int main() long f45,i,n;f1=1;f2=1;f3=1;f4=2;for (i=4;i=40;i+)fi=fi-1+fi-3;scanf(“%d“,while (i-)scanf(“%d“,printf (“%dn“,fn);return 0; C语言实现代码：
