CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
晶晶赴约会
#incldue<stdio.h>
int main()
{
int n;
scanf("%d",&n);
printf(n==1||n==3||n==5?
"NO":"YES");
}
陶陶摘苹果
#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);
}
大象喝水
#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);
}
忽略大小写比较字符串大小
学习一个 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("=");
}
已经强调本题禁用 strcmp 函数结果……本题变得毫无诚意。
#include<stdio.h>
#include<string.h>
#include<ctype.h>
int main()
{
char cmp,s[2][128];
for(int i=0; i!=2; ++i)
{
gets(s[i]);
for(int j=strlen(s[i])-1; j!=-1; --j)
s[i][j]=tolower(s[i][j]);
}
cmp=strcmp(s[0],s[1]);
puts(cmp>0?">":
cmp<0?"<":"=");
}
学分绩点
#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]);
}
不吉利日期
#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;
}
}
}
优解：直接从 1 月 13 号往上加，利用同余系的性质很漂亮的做掉这一题。
#include<stdio.h>
int main()
{
int w,days[13]= {0,12,31,28,31,30,31,30,31,31,30,31,30};
scanf("%d",&w);
for(int m=1; m<=12; ++m)
{
w=(w+days[m])%7+1;
if(w==5)
printf("%d\n",m);
}
}
生日相同
#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");
}
}
跳格问题
#include<stdio.h>
int n,ans=0,a[32]= {1,0};
int main()
{
scanf("%d",&n);
for(int i=1; i<=n; ++i)
scanf("%d",&a[i]);
for(int pos=0,pre=0; pos<=n;)
{
if(a[pre=pos])
{
pos+=a[pos];
if(pos<0)
pos=0;
a[pre]=0;
++ans;
}
else
{
++pos;
ans+=2;
}
}
printf("%d",ans);
}
采药
可以看到 I、J 两题不同的只有数据范围。
对于数据范围比较小的 I 题，可以直接暴力搜索：将草药从 1 开始编号，记 f[t][m] 为时间 t 内采集前 m 棵的草药的最优解，那么有 f[t][m]=max(f[t-cost[m]][m-1]+value[m],f[t][m-1]) ；用自然语言表述，就是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));
}
还是采药问题
注意到在第 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]);
}