文章

05年浙大复试机试题解

05年浙大复试机试题解

以下是05年浙大研究生复试机试题解,感觉题目与ACM题相比,难度还相差很远, 基本上直接贴上代码了(后续年度的题解同上), 而且将整年的5道题的代码在一篇文章中贴出来。

A题:A+B (hdoj1228)( 九度1010)

水题,不解释,直接上代码:

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
#include <stdio.h> 
#include <string.h> 
char map[][8] = {"zero","one","two","three","four","five","six","seven","eight","nine"};
int cmp( char s[] ) 
{
	for( int i = 0 ; i <= 9 ; i++ )
		if( strcmp( s , map[i] ) == 0 )
			return i;
}
int main() 
{
	char s[8];
	int a,b;
	while(1) 
	{
		a = 0;
		while(scanf("%s",s)&&strcmp(s,"+")!=0)
			a = 10*a + cmp(s);
		b = 0;
		while(scanf("%s",s)&&strcmp(s,"=")!=0)
			b = 10*b + cmp(s);
		if( a == 0 && b == 0 ) break;
		printf( "%d\n" , a+b );
	}
	return 1;
}

B题:最大连续子序列 (hdoj1231)( 九度 1011 )

这道题做过很多遍了,但用过的最好的方法还是用二重循环,在OJ上难免TLE了。 Google了下才知道,可以用DP在O(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
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<stdio.h> 
int main() 
{
	int k,d[10000];
	int i,j,sum,max,st,end,cnt;
	while(1)
	{
		scanf("%d",&k);
		if(k==0)break;
		for(i=0;i<k;i++,getchar())
			scanf("%d",d+i);
		cnt=0;
		for(i=0;i<k;i++)
			if(d[i]<0) cnt++;
			else break;
		if(cnt==k)
		{
			printf("%d %d %d\n",0,d[0],d[k-1]);
			continue;
		}
		st=end=j=sum=0;
		max=d[0];
		for(i=0;i<k;i++)
		{
			j=sum>0 ? j:i;
			sum = sum>0 ? sum : 0;
			sum+=d[i];
			if(sum>max)
			{
				max=sum;
				st=j;
				end=i;
			}
		}
		printf("%d %d %d\n",max,d[st],d[end]);
	}
	return 0;
}

C题:畅通工程 (hdoj1232)( 九度 1012)

以前很少做图论的题,看到这题时,首先想到的就是用BFS,计算遍历完所有点所需要BFS的次数, 该次数减一即为所求,但提交后发现TLE了。查了下资料才知道,要使用并查集,以前没用过, 总以为这是STL中的东西,而STL也没学过,不会,于是乎继续想办法改进基于BFS的算法, 悲剧的是一直TLE,最后还是看了下并查集的知识,才发现用C数组很容易就可以实现。 使用了并查集后,果断AC了,呵呵。代码如下:

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
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h> 
#include <memory.h> 
int m,n,min,set[1002];
int Find(int x)
{
	while(x!=set[x])
		x=set[x];
	return x;
}
void Union(int a,int b)
{
	int t1,t2;
	t1=Find(a);
	t2=Find(b);
	if(t1!=t2)
	{
		set[t2]=t1;
		min--;
	}
}
int main() 
{
	int i,a,b;
	while(1)
	{
		scanf("%d",&n);
		if(n==0) break;
		for(i=0;i<=n;i++) set[i]=i;
		min=n-1;
		scanf("%d",&m);
		for(i=0;i<m;i++)
		{
			scanf("%d %d",&a,&b);
			Union(a,b);
		}
		if(min>0)printf("%d\n",min);
		else printf("0\n");
	}
	return 0;
}

D题:开门人和关门人(hdoj1234)( 九度 1013)

水题,直接上代码:

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
29
30
31
32
33
34
35
#include <stdio.h> 
#include <memory.h> 
int m,n; char temp[16],first[16],last[16];
int time[3],min,max;
int main() 
{
	int i,j;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&m);
		min=86400;
		max=-1;
		for(j=0;j<m;j++)
		{
			scanf("%s",temp);
			scanf("%d:%d:%d",time,time+1,time+2);
			time[0]=time[0]*3600+time[1]*60+time[2];
			if(time[0]<min)
			{
				min=time[0];
				memcpy(first,temp,sizeof(temp));
			}
			scanf("%d:%d:%d",time,time+1,time+2);
			time[0]=time[0]*3600+time[1]*60+time[2];
			if(time[0]>max)
			{
				max=time[0];
				memcpy(last,temp,sizeof(temp));
			}
		}
		printf("%s %s\n",first,last);
	}
	return 0;
}

E题:排名(hdoj1236)( 九度 1014)

简单题,直接调用系统的快排函数,代码如下:

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
typedef struct student {
	char name[21];
	int score;
}stu;
int m,n,g,fz[10];
stu st[1000];
int cmp(const void * a,const void * b)
{
	int t=(*(stu*)b).score-(*(stu*)a).score;
	if(t!=0)return t;
	else return strcmp((*(stu*)a).name,(*(stu*)b).name);
}
int main() 
{
	int i,j,t,ts,ss;
	while(1)
	{
		scanf("%d",&n);
		if(0==n)break;
		scanf("%d %d",&m,&g);
		for(i=0;i<m;i++)
			scanf("%d",&fz[i]);
		for(i=0;i<n;i++)
		{
			scanf("%s",&(st[i].name));
			scanf("%d",&t);
			ss=0;
			for(j=0;j<t;j++)
			{
				scanf("%d",&ts);
				ss+=fz[ts-1];
			}
			if(ss<g)
			{
				n--;
				i--;
			}
			else
				st[i].score=ss;
		}
		qsort(st,n,sizeof(stu),cmp);
		printf("%d\n",n);
		for(i=0;i<n;i++)
		printf("%s %d\n",st[i].name,st[i].score);
	}
	return 0;
}

小结:总的来说,05年的题不是太难,但由于很久没写代码,所以做的不是很顺。

本文由作者按照 CC BY 4.0 进行授权