补♂课第11场解题报告

2017-11-30 07:47:59来源:CSDN作者:w_weilan人点击

分享

Overview

A - 晶晶赴约会

#incldue<stdio.h>int main(){    int n;    scanf("%d",&n);    printf(n==1||n==3||n==5?           "NO":"YES");}

B - 陶陶摘苹果

#include<stdio.h>int main(){    int a[10],h,ans=0;    for(int i=0; i!=10; ++i)        scanf("%d",&a[i]);    scanf("%d",&h);    for(int i=0; i!=10; ++i)        if(a[i]<=30+h)            ++ans;    printf("%d",ans);}

C - 大象喝水

#include<stdio.h>int main(){    int h,r;    scanf("%d%d",&h,&r);    double v=3.14159*r*r*h;    printf("%d",(int)(20000/v)+1);}

D - 忽略大小写比较字符串大小

学习一个gets和puts函数的用法。另外,为了程序高效,尽量减少strlen函数的调用。

#include<stdio.h>#include<string.h>int main(){    char s[2][128];    for(int i=0; i!=2; ++i)    {        gets(s[i]);        for(int j=strlen(s[i])-1; j!=-1; --j)            if('A'<=s[i][j]&&s[i][j]<='Z')                s[i][j]+='a'-'A';        for(int j=strlen(s[i]); j!=128; ++j)            s[i][j]=0;    }    for(int i=0; i!=128; ++i)        if(s[0][i]!=s[1][i])        {            puts(s[0][i]<s[1][i]?"<":">");            return 0;        }    puts("=");}

E - 学分绩点

#include<stdio.h>float scal(int g){    return g>89?4.0:           g>84?3.7:           g>81?3.3:           g>77?3.0:           g>74?2.7:           g>71?2.3:           g>67?2.0:           g>63?1.5:           g>59?1:0;}int main(){    int n,a[2][10];    float sum[2]= {0,0};    scanf("%d",&n);    for(int i=0; i!=2; ++i)        for(int j=0; j!=n; ++j)            scanf("%d",&a[i][j]);    for(int i=0; i!=n; ++i)    {        sum[0]+=a[0][i];        sum[1]+=a[0][i]*scal(a[1][i]);    }    printf("%.2f",sum[1]/sum[0]);}

F - 不吉利日期

#include<stdio.h>int main(){    int w,days[13]= {0,31,28,31,30,31,30,31,31,30,31,30,31};    scanf("%d",&w);    for(int d=1,m=1; m!=13; ++d,w=w%7+1)    {        if(d==13&&w==5)            printf("%d/n",m);        if(d==days[m])        {            ++m;            d=0;        }    }}

G - 生日相同

#include<stdio.h>#include<string.h>char str[13][32][128][16]= {0};int n,m,d,size[13][32]= {0};int main(){    scanf("%d",&n);    for(char name[16]; n--;)    {        scanf("%s%d%d",name,&m,&d);        strcpy(str[m][d][size[m][d]++],name);    }    for(m=1; m!=13; ++m)        for(d=1; d!=32; ++d)            if(size[m][d]>1)            {                printf("%d %d",m,d);                for(int i=0; i!=size[m][d]; ++i)                    printf(" %s",str[m][d][i]);                printf("/n");            }}

H - 跳格问题

#include<stdio.h>int n,a[32]= {0},flag[32]= {1,0};int main(){    scanf("%d",&n);    for(int i=0; i!=n; scanf("%d",&a[++i]));    for(int p=2,cnt=1;;)    {        while(flag[p]&&p<=n)        {            cnt+=2;            ++p;        }        flag[p]=1;        p+=a[p];        ++cnt;        if(p<0)p=0;        if(p>n)        {            printf("%d",cnt);            return 0;        }    }}

I - 采药

可以看到I、J两题不同的只有数据范围。
对于数据范围比较小的I题,可以直接暴力搜索:
将草药从1开始编号,记f[t][m]为时间t内采集前m棵的草药的最优解,那么有f[t][m]=max(f[t][m-1],f[t-cost[m]][m-1]+value[m]);用自然语言表述,就是m号草药要么采,要么不采
然后考虑搜索的边界条件:如果t<0,那么说明时间已经是不够用的,那么要返回一个负无穷来表示这个状态不可以被转移;如果t==0那么显然结果是0;如果m==0,说明所有的草药都已经被考虑过,这时候时间还有多,返回0表示继续采也不会再有收益了。

#include<stdio.h>int cost[128]= {0},value[128]= {0};int max(int a,int b){    return a>b?a:b;}int work(int t,int m){    if(t<0)return -1e9;    if(t==0||m==0)return 0;    return max(work(t,m-1),            work(t-cost[m],m-1)+value[m]);}int main(){    int t,m;    scanf("%d%d",&t,&m);    for(int i=1; i<=m; ++i)        scanf("%d%d",&cost[i],&value[i]);    printf("%d",work(t,m));}

J - 还是采药问题

注意到在第I题的搜索里,搜索的过程有很多重复的浪费;我们可以用数组自己手动推转移关系。

int work(int t,int m){    static int f[1024][128]= {0};    //定义成static可以直接初始化为0    for(int i=1; i<=t; ++i)        for(int j=1;j<=m;++j)        {            f[i][j]=f[i][j-1];            if(i>=cost[j])                f[i][j]=max(f[i][j],                    f[i-cost[j]][j-1]+value[j]);        }    return f[t][m];}

注意到转移方向的特殊性,稍微改一下循环的层级和方向,就可以将原先的数组降至一维,从而大大降低函数的内存开销。

int work(int t,int m){    static int f[1024]= {0};    for(int j=1; j<=m; ++j)        for(int i=t; i>=cost[j]; --i)            f[i]=max(f[i],                f[i-cost[j]]+value[j]);    return f[t];}

当然,也可以在I题中的函数里加上静态(static)记录数组,每次搜索后把结果存起来;在调用函数的时候。这样的技术,我们称之为记忆化搜索。当然,也可以使用全局数组代替,但是全局数组可以被程序的其他部分访问,从而可能使函数的运行不符合我们的预期;使用静态数组,可以使搜索函数变成记录数组唯一合法的访问入口,更加保险。
注意,和很多常见的记忆化搜索不同,这里的0是有可能(其实是一定,例如work(0,0)一定为0)出现在搜索结果中的,因此需要专门使用一个标记数组来记录访问情况,而不能直接判断f[t][m]!=0是否成立否则会TLE。
当然,这样写的好处是逻辑清晰易写,效率也和之前的动态规划是一个级别(每个点至多只计算一次,而且很多无关点不会被访问);缺点是函数调用会有一点微小的开销,造成更大的内存空间浪费,也不像之前的规划那样容易降维优化。

int work(int t,int m){    static int f[1024][128]= {0},                flag[1024][128]= {0};    if(t<0)return -1e9;    if(t==0||m==0)return 0;    if(flag[t][m])return f[t][m];    flag[t][m]=1;    return f[t][m]=max(work(t,m-1),        work(t-cost[m],m-1)+value[m]);}

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台