Menu

补♂课第11场

发表于 29 Nov 2017 总计 4841字 阅读时间 17分
CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~

Overview

晶晶赴约会

1
2
3
4
5
6
7
8

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

陶陶摘苹果

1
2
3
4
5
6
7
8
9
10
11
12

#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);
}

大象喝水

1
2
3
4
5
6
7
8

#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 函数的调用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#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 函数结果……本题变得毫无诚意。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#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?"<":"=");
}

学分绩点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#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]);
}

不吉利日期

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#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 号往上加，利用同余系的性质很漂亮的做掉这一题。

1
2
3
4
5
6
7
8
9
10
11
12

#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);
	}
}

生日相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#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");
			}
}

跳格问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#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 表示继续采也不会再有收益了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#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 题的搜索里，搜索的过程有很多重复的浪费；我们可以用数组手动推转移关系。

1
2
3
4
5
6
7
8
9
10
11
12
13

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];
}

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

1
2
3
4
5
6
7
8
9

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。 当然，这样写的好处是逻辑清晰易写，效率也和之前的动态规划是一个级别（每个点至多只计算一次，而且很多无关点不会被访问）；缺点是函数调用会有一点微小的开销，造成更大的内存空间浪费，也不像之前的规划那样容易降维优化。

1
2
3
4
5
6
7
8
9
10
11

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]);
}