程序设计实践_201602期末

发表于 | 分类于 ， |
程序设计实践课程，2016年下学期，期末考试题解。
题目 类型 难度
Page 数学 ★
RGB 数学 ★★
Matrix 模拟 ★★★
鞍点 统计，执行 ★★
Craftman 二分 ★★★★
Unique Digit Number 递推，队列 ★★★★★

Page

题意

题目来源于小学3年级奥数题。
一本书从1开始编页码，已知用了n个页码，问书有多少页？

思路

页码位数$i$ 页范围 页码数量$P_i$
1 1~9 $9$
2 1~99 $2\times90+9$
3 1~999 $3\times900+2\times90+9$

所以可以递推出页码位数下最多的页码数量，然后根据$n$的值，找出页码数量比n大的最小页码位数i。
所以结果就是$\underbrace{99\cdots9}_{i-1} + (n - P_{i-1}) / i$

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>

int main(){
	int T,n,a[9]={0},i,k;
	for(i=1,n=1;i<9;i++,n*=10) a[i] = a[i-1] + i*(10*n-n);
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(i=8,k=99999999;i>=0&&a[i]>=n;i--,k/=10);
		printf("%d\n",k+(n-a[i])/(i+1));
	}
	return 0;
}

RGB

题意

红绿蓝三色球排成一行，一次可以任意调换两个球的位置，求把所有球排列成红绿蓝三种单色区间需要交换的最少次数。

思路

与颜色区间不同颜色的球才需要调换。
如果相对颜色区间存在相对颜色的球，那就先对换。
最后剩下的肯定是 红区绿球，绿区蓝球，蓝区红球 或者 红区蓝球，绿区红球，蓝区绿球 这两种。这是一个轮换，两次交换就可以完成。
假设红区绿球，蓝球分别为rg，rb；绿区红球，蓝球分别为gr，gb； 蓝区红球，绿球分别为br,bg;
那么

标程

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 <string.h>
#define ABS(x)   ((x)<0?(-(x)):(x))
#define MIN(a,b) ((a)<(b)?(a):(b))

int main(){
	char s[10011];
	int r,g,rg,rb,gb,gr,br,bg,i,n,ans;
	while(gets(s)){
		r = g = 0;
		n = strlen(s);
		for(i = 0; i < n; i++){
			if(s[i] == 'R') r++;
			else if(s[i] == 'G') g++;
		}
		rg = rb = gr = gb = br = bg = 0;
		for(i = 0; i < r; i++){
			if(s[i] == 'G') rg++;
			else if(s[i] == 'B') rb++;
		} 
		for(; i < r+g; i++){
			 if(s[i] == 'R') gr++;
			 else if(s[i] == 'B') gb++;
		}		
		for(; i < n; i++){
			if(s[i] == 'R') br++;
			else if(s[i] == 'G') bg++;
		}
		ans = MIN(rg,gr) + MIN(rb,br) + MIN(gb,bg);
		ans += 2 * ABS(rg-gr);
		printf("%d\n",ans);
	}

	 return 0;
}

Matrix

题意

一个指令序列，包括矩阵初始化，矩阵交换行、列，矩阵按行、列镜像翻转，矩阵转置和输出矩阵的操作，模拟指令序列。

思路

很直白的模拟题，直接做就可以，代码量稍大。镜像翻转可以用行列交换来实现，矩阵转置注意矩阵的维度也要交换。

指令的前两个字符相加值是唯一的，可以用来作指令字符串的hash，快速判断是哪个指令，不过这个并不影响题目本身

标程

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <stdio.h>
#include <assert.h>
const unsigned int N = 10;

int a[N][N];


void init(int n,int m){
	int i,j;
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
			a[i][j] = i*m+j+1;
}

void swapRow(int m,int x,int y){
	int j,t;
	for(j=0; j<m; j++){
		t = a[x][j];
		a[x][j] = a[y][j];
		a[y][j] = t;
	}
}

void swapCol(int n,int x,int y){
	int i,t;
	for(i=0; i<n; i++){
		t = a[i][x];
		a[i][x] = a[i][y];
		a[i][y] = t;
	}	
}

void flipRow(int n, int m){
	int i,k;
	for(i=0,k=n-1;i<k;i++,k--){
		swapRow(m,i,k);
	}	
}

void flipCol(int n,int m){
	int j,k;
	for(j=0,k=m-1;j<k;j++,k--){
		swapCol(n,j,k);
	}
}

void print(int n,int m){
	int i,j;
	for(i=0;i<n;i++){
		for(j=0;j<m;j++)
			printf("%d%c",a[i][j]," \n"[j==m-1]);
	}
	putchar('\n');
} 

void trans(int *n,int *m){
	int i,j,t,len;
	len = *n>*m?*n:*m;
	for(i=0;i<len;i++){
		for(j=0;j<i;j++){
			t = a[i][j];
			a[i][j] = a[j][i];
			a[j][i] = t;
		}
	}
	t = *n;
	*n = *m;
	*m = t;
}

int main(){
	char buf[111];
	int x,y,n,m;
	while(gets(buf)){
		switch(buf[0]+buf[1]){
		case 151: //IN x y
			sscanf(buf+3,"%d %d",&n,&m);			
			init(n,m);
			break;
		case 165:	// SR x y
			sscanf(buf+3,"%d %d",&x,&y);			
			swapRow(m,x-1,y-1);
			break;
		case 150:	// SC x y
			sscanf(buf+3,"%d %d",&x,&y);			
			swapCol(n,x-1,y-1);
			break;
		case 166:	// TR
			trans(&n,&m);
			break;
		case 152:	// FR
			flipRow(n,m);
			break;
		case 137:	// FC
			flipCol(n,m);
			break;
		case 162:	// PR
			print(n,m);
			break;
		}
	}
}

鞍点

题意

题目来源于矩阵中一个常见的问题（当年还是我读书的时候，数据结构老师问的），不过我把定义稍微改了一点，增加了所在列最大，行最小。

求矩阵中所在行最大，所在列最小或者所在行最小，所在列最大的元素。

思路

明显的统计题，直接遍历矩阵，统计每行每列的最大、最小值。再遍历矩阵，判断元素是否满足条件。

标程

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
#include <stdio.h>
#include <string.h>
#define N 100

int main(){
	int a[N][N],col_max[N],col_min[N],row_max[N],row_min[N],n,m,i,j,T,cnt,ans[N*N][2];
	scanf("%d",&T);
	while(T--){
		scanf("%d %d",&n,&m);
		memset(row_max,0,sizeof(row_max));
		memset(row_min,0x7f,sizeof(row_min));
		memset(col_max,0,sizeof(col_max));
		memset(col_min,0x7f,sizeof(col_min));		

		for(i=0;i<n;i++){
			for(j=0;j<m;j++){
				scanf("%d",&a[i][j]);
				if(a[i][j] > row_max[i]) row_max[i] = a[i][j];
				if(a[i][j] < row_min[i]) row_min[i] = a[i][j];
				if(a[i][j] > col_max[j]) col_max[j] = a[i][j];
				if(a[i][j] < col_min[j]) col_min[j] = a[i][j];
			}
		}
		cnt = 0;
		for(i=0;i<n;i++){
			for(j=0;j<m;j++){
				if(a[i][j] == row_max[i] && a[i][j] == col_min[j]){
					ans[cnt][0] = i;
					ans[cnt][1] = j;
					cnt++;
				} else if(a[i][j] == row_min[i] && a[i][j] == col_max[j]){
					ans[cnt][0] = i;
					ans[cnt][1] = j;
					cnt++;
				}
			}			   	 
		}
		if(cnt==0) puts("None");
		else {
			printf("%d\n",cnt);
			for(i=0; i<cnt; i++){
				printf("%d %d %d\n",ans[i][0],ans[i][1],a[ans[i][0]][ans[i][1]]);
			}
		}
	}

	return 0;
}

Craftman

题意

题目来源CF原题（题号也不记得了），我修改了一下题面描述。
做一件“恶魔手套”需要$n$种原材料，分别需要$a_i,i=1,2,\ldots,n$份,你有$b_i,i=1,2,\ldots,n$份材料。
你还有$k$张材料兑换券，一张券可以兑换任意一份材料，问你最多能做几件“恶魔手套”？

思路

$f(x)$表示制作$x$件恶魔手套需要的兑换券的数量。
问题转换成求满足$f(x) \le k$情况下，最大的$x$。
显然，$f(x)$是单调递增的，所以很容易想到使用二分求上限即可。

标程

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
#include <stdio.h>
#define N 1000

long long a[N],b[N];

int check(int x,int n,int k){
	int i;
	long long s=0;
	for(i=0;i<n&&s<=k;i++){
		if(b[i] < a[i]*x ) s += a[i]*x - b[i];
	}
	return s <= k;
}

int solve(int L,int R,int n,int k){
	int m=0;
	while(L < R){
		m = ((R-L+1)>>1) + L;
		if(check(m,n,k)) L = m;
		else R = m - 1; 
	}	
	return L;
}

int main(){
	int T,n,k,i,L,R,t;
	scanf("%d",&T);
	while(T--){
		scanf("%d %d",&n,&k);
		for(i=0;i<n;i++) scanf("%I64d",a+i);
		L = R = 2000000000;
		for(i=0;i<n;i++){
			scanf("%I64d",b+i);
			t = (b[i]+k) / a[i];
			if( t < R) R = t;
			t = b[i] / a[i];
			if (t < L) L = t; 
		}
		printf("%d\n",solve(L,R,n,k));
	}
	return 0;
}

Unique Digit Number

题意

求第$n$个数码不相同的数。

思路

明显$0-9$是数码不相同的数。如果$p(p>0)$是数码不相同的数，$j$是p没有使用过的数码，那么$10p+j$也是数码不相同的数。
所以我们可以用一个队列来生成和存放所有的不同数码的数，由于生成是有序的，所以队列里也是有序的。
题目有提示，这样的数最多有8877691个。

标程

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
#include <stdio.h>
#include <math.h>

#define N 10000000
long long a[N];
int t[N];
int cnt = 1;

int main(){
	int i,j;
	for(i=1;i<10;i++){
		a[cnt] = i;
		t[cnt] |=  1<<i;
		cnt++;
	} 
	for(i=1;i<cnt;i++){
		for(j=0;j<10;j++){
			if((1<<j) & ~t[i] ){
				a[cnt] = a[i] * 10 + j;
				t[cnt] = t[i] | (1<<j);
				cnt++;
			}
		}
	}
	while(scanf("%d",&i)!=EOF){
		printf("%I64d\n",a[i-1]);
	}
	return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！