程序设计实践_201602期末

题目 类型 难度
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;
}
坚持原创技术分享,您的支持将鼓励我继续创作!