2018.02.05(算法综合测验)

2018.02.05

算法综合测验

今天我们进行了一次包括动态规划在内的综合考试。分数190=40+100+40+10。下面对此次考试进行总结。

1.奔跑的玉兔

嫦娥和猪八戒是一对恋人，但由于触犯天条，不得见面。终于在一次蟠桃宴会上，玉帝大发慈悲，允许他们见一次面。他们万分激动，各自听到消息后，猪八戒从立即高老庄出发，嫦娥立即从广寒宫出发，准备前往对方的住所。嫦娥出发时还放出了玉兔，玉兔由于踏着风火轮的原因，比二位仙人跑得更快，在他们之间来回跑啊跑，中途遇到猪八戒或者嫦娥就掉头，跑了好几趟，后来他们终于相遇了，玉兔因为锻炼瘦了几斤。求玉兔共跑了多长距离。

　　输入格式：

共一行，有四个正整数，依次是L、v1、v2、v3（范围均在1~100000），分别表示猪八戒和嫦娥住所的距离，嫦娥的速度，猪八戒的速度，玉兔的速度。输入保证玉兔的速度不会比嫦娥和猪八戒的慢。

　　输出格式：

　　一个正整数，即玉兔总共跑过的距离，需要舍去小数位，保留整数部分

解析：一道水题，明显的小学奥数，套公式：$S玉兔=L/(v1+v2)*v3$即可。可惜因为没有注意精度的问题，只有40分。下次要注意，%.0lf会四舍五入。

代码：

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 int main(){
 5     freopen("rabbit.in","r",stdin);
 6     freopen("rabbit.out","w",stdout);
 7     double s,s2;
 8     double v1,v2,v3; 
 9     scanf("%lf",&s);
10     scanf("%lf%lf%lf",&v1,&v2,&v3);
11     s2=(s/(v1+v2))*v3;
12     
13     printf("%d",(int)s2);
14     return 0;
15 }

View Code

　　2030年长沙市一中将举办IOI，需要购置大量的设备。现在联系了N个出售设备的经销商，第i个经销商保有的设备库存为si，报出每台设备的价格为pi元。如果长沙市一中有预算M元，最多可以买多少台设备？由于学校拨款预算方案还没有下来，采购组只能估计多个预算费用M，并提前计算采购力。

　　第一行：一个正整数N(N<10000)。第二行到第N+1行：第i+1行包含两个正整数：si pi （均不超过1000）。第N+2行：一个正整数T（T<100000），表示有多少个M。第N+3行到第N+T+2：每行一个正整数M

　　共T行：每行一个整数，按照输入的M的顺序，输出M元预算能买到最多设备的数量C。

解析：本题100完美AC，和金银岛类似，只要先排序，再按照单价最小的购买即可。优化：买机器时，可以一批一批的买，不用一台一台买。

1 #include <cstdio> 2 #include <cmath> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 struct data {int shu,jia;}mach[10001]; 8 bool cmp(data a,data b){return a.jia < b.jia;} 9 int main(){ 10 freopen("ioi.in","r",stdin); 11 freopen("ioi.out","w",stdout); 12 int N,T,m; 13 int i,j; 14 scanf("%d",&N); 15 for(i=1;i<=N;i++) 16 scanf("%d%d",&mach[i].shu,&mach[i].jia); 17 sort(mach+1,mach+1+N,cmp); 18 scanf("%d",&T); 19 for(i=1;i<=T;i++){ 20 scanf("%d",&m); 21 int sum; 22 sum=0; 23 for(j=1;j<=N;j++){ 24 if(m>=mach[j].jia*mach[j].shu){ 25 m-=mach[j].jia*mach[j].shu; 26 sum+=mach[j].shu; 27 } 28 else if(m<mach[j].jia*mach[j].shu){ 29 sum+=(m/mach[j].jia); 30 break; 31 } 32 } 33 printf("%d ",sum); 34 } 35 return 0; 36 }

1 #include <stdio.h> 2 #include <math.h> 3 #include <string.h> 4 int main(){ 5 freopen("hnfms.in","r",stdin); 6 freopen("hnfms.out","w",stdout); 7 long long H,N,F,M,S; 8 char ch; 9 int n; 10 scanf("%d",&n); 11 getchar(); 12 while(n--){ 13 H=0;N=0;F=0;M=0;S=0; 14 while((ch=getchar())!=' '&&ch!=EOF){ 15 if(ch=='H')H++; 16 if(ch=='N')N+=H; 17 if(ch=='F')F+=N; 18 if(ch=='M')M+=F; 19 if(ch=='S')S+=M; 20 } 21 printf("%lld ",S); 22 } 23 return 0; 24 }

1 #include <stdio.h> 2 #include <math.h> 3 #include <string.h> 4 int w[101],c[101]; 5 int f[101][1001]; 6 int _Max(int x,int y){return x>y?x:y;} 7 int main(){ 8 int n,m; 9 int i,j,v; 10 scanf("%d%d",&m,&n); 11 for(i=1;i<=n;i++) 12 scanf("%d%d",&w[i],&c[i]); 13 for(i=1;i<=n;i++) 14 for(v=m;v>0;v--) 15 if(w[i]<=v) f[i][v]=_Max(f[i-1][v],f[i-1][v-w[i]]+c[i]); 16 else f[i][v]=f[i-1][v]; 17 printf("%d ",f[n][m]); 18 return 0; 19 }

2018.02.05(算法综合测验)

相关推荐