程序设计实践-201501期末

发表于 | 分类于 ， |
程序设计实践课程，2015年上学期，期末考试题解。
题目 类型 难度
Alice and Bob 模拟 ★★★
Alice’s Prime 枚举,队列 ★★
Bonus 拓扑排序 ★★★★★
Colombian_Number 枚举 ★★
Matrix Word 统计 ★
Robot 模拟 ★

Alice and Bob

题意

掷骰子游戏，有豹子，对子，点子三类，比谁大？

思路

为了方便比较，可以直接把三种骰子的情况映射到一个整数，用这个整数作为优先级，然后使用这个整数进行比较。
骰子的优先级依次为$1,6,5,4,3,2$，我们用$g(x) = 7 - x \mod 6$，映射优先级依次为$0,1,2,3,4,5$。
这样，我们使用下面的函数映射三颗骰子的优先级（\left 不被mathjax 支持？mathjax官方文档里有，我怎么搞也搞不出来，不知道为何）

标程

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
#include <bits/stdc++.h>
using namespace std;

int get(int *a)
{
	if(a[0]==a[1]){
		if(a[1]==a[2]) return 100+(7 - a[0]) % 6;
		else return 200+((7 - a[0]) % 6) * 10 + (7 - a[2]) % 6;
	} else {
		if(a[0] == a[2]) return 200+((7 - a[0]) % 6)*10 + (7 - a[1]) % 6;
		else {
			if(a[1] == a[2]) return 200+((7 - a[1]) % 6)*10 + (7 - a[0]) % 6;
			else return 300+18-(a[0]+a[1]+a[2]);
		}
	}
}

int main()
{	
	int ca,a[3],b[3],ap,bp;
	
	scanf("%d",&ca);
	while(ca--){
		scanf("%d %d %d",a,a+1,a+2);
		scanf("%d %d %d",b,b+1,b+2);
		ap = get(a);
		bp = get(b);
		if(ap < bp) puts("Alice");
		else if (ap > bp) puts("Bob");
		else puts("Draw");
	}
	return 0;
}

Alice’s Prime

题意

判断一个整数是否满足依次删去最后一位得到的数都是素数。

思路

$1$位的素数只有$2,3,5,7$,所以最高位只能是这4个数。
$2$位及以上的素数只能是奇数，而且不能是$5$，所以末尾只能加$1,3,7,9$。
所以如果$p$是满足条件，那么就判断${10p+1,10p+3,10p+7, 10p+9}$是否为是素数。
用一个队列来存储和生成所有满足条件的数即可（题目已经给了提示，这样的数不超过83个）。

标程

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

int isPrime(int x)
{
    int i,k;
    if(x<2) return 0;
    if(x==2) return 1;
    if(~x&1) return 0;
    k = sqrt(x);
    for(i=3;i<=k&&x%i;i+=2);
    return i>k;
}

int main()
{
    int a[100] = {2,3,5,7},b[4]={1,3,7,9},i,j,cnt=4,t;
    for(i=0;i<cnt;i++){
        printf("%d %d\n",i+1,a[i]);
        for(j=0;j<4;j++){
            t = a[i]*10+b[j];
            if(isPrime(t)) a[cnt++] = t;
        }
    }
    for(j=0;j<cnt;j++)
        printf("%d %d\n",j+1,a[j]);
    return 0;
}

Bonus

题意

题目来源于 HDOJ 2647 Award，稍微有修改。

有一个员工表现的对比情况，表现最差的员工拿888奖金，每高一级多加1000，求最少需要给多少奖金？
但是对比情况可能会有矛盾的情况，这种情况下，每个人都发888。

思路

拓扑排序的裸题。
根据员工表现情况对比构图，从表现好的员工节点连一条有向边只想表现差的员工（反向构图也可以，后面反过来算即可）。
然后拓扑排序，如果存在环，那么就是存在矛盾，否则计算出所有节点的层次 $level_i \mid i = 1,2,\ldots,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
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
#include <bits/stdc++.h>
using namespace std;

#define FU(i,n) for(int i=0;i<(n);i++)

const int N = 10000;
const int M = 50000;

int visit[N];
int bonus[N];
int edge[M][2];
int node[N];
int cnt;

void addEdge(int a,int b){
	edge[cnt][1] = node[a];
	edge[cnt][0] = b;
	node[a] = cnt++;
}

void init(int n){
	int len = sizeof(int) * n;
	memset(node,-1,len);
	memset(visit,0,len);
	memset(bonus,0,len);
	cnt = 0;
}

void graph(int n,int m){
	init(n);
	FU(i,m){
		int a,b;
		scanf("%d %d",&a,&b);
		addEdge(a-1,b-1);
	}
}

int dfs(int u){
	int v,t;
	visit[u] = -1;
	for(t=node[u];t!=-1;t=edge[t][1]){
		v = edge[t][0];
		if(visit[v] == -1) return -1;
		if(visit[v] == 0) bonus[v] = dfs(v);
		if(bonus[u] < bonus[v]+1) bonus[u] = bonus[v]+1;
	}
	visit[u] = 1;
	return bonus[u];
}

int topoSort(int n,int m){
	int u,t;
	for(u=0;u<n;u++) if(!visit[u]){
		t = dfs(u);
		if(t==-1) return 0;
	}
	return 1;
}

int main()
{
	int n,m,ca,ans;
	scanf("%d",&ca);
	while(ca--){
		scanf("%d %d",&n,&m);
		graph(n,m);

		if(topoSort(n,m)){
            ans = 0;
			FU(i,n) ans += (bonus[i] = bonus[i]*1000+888);
			printf("%d\n",ans);
			FU(i,n-1) printf("%d ",bonus[i]);
			printf("%d\n",bonus[n-1]);
		} else {
			printf("%d\n",888*n);
			FU(i,n-1) printf("888 ");
			printf("888\n");
		}
	}
	return 0;
}

Colombian_Number

题意

题目来源于 OEIS A003052。
判断一个正整数$n$,是否满足不存在整数$k$,使得$n$等于$k$加上$k$的数码累加和。

思路

显然，我们可以枚举$n-1,n-2,\ldots,1$看是否存在这样的$k$。但是，$n=10^9$，这么做的效率太低了。
我可以观察一下，枚举到什么时候就可以停止，不需要一直枚举到$1$。

所以，只要枚举很少的量就可以了，从而能在时限内完成枚举。

标程

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

int digitSum(int n)
{
    int s=0;
    while(n){
        s += n % 10;
        n /= 10;
    }
    return s;
}

int main()
{    
    int ca,n,i,k;
    scanf("%d",&ca);
    while(ca--){
        scanf("%d",&n);
        k = ceil(log10(n+1));
        k = n - 9*k;
        if(k<(n>>1)) k = n>>1;
        for (i=n-1;i>=k;i--){
            if(i+digitSum(i)==n) break;
        }
        if(i<k) puts("Yes");
        else puts("No");
    }

    return 0;
}

Matrix Word

题意

题目是CF原题，题号不记得了:p。
一个字符矩阵去掉行列不唯一的字符得到字符的序列。

思路

统计行、列出现字符的次数，最后按行列顺序输出行列都唯一的字符即可。

标程

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 <bits/stdc++.h>
using namespace std;

#define FU(i,n) for(int i=0;i<(n);i++)

int main()
{
	char str[111][111];
	int n,m;
	int col[100][26],row[100][26];
	
	while(scanf("%d %d ",&n,&m)!=EOF){
		FU(i,n) scanf("%s",str[i]);
		memset(col,0,sizeof(col));
		memset(row,0,sizeof(row));
		FU(i,n) FU(j,m){
			col[i][str[i][j]-'a']++;
			row[j][str[i][j]-'a']++;
		}
		FU(i,n) FU(j,m){
			if(col[i][str[i][j]-'a']==1 && row[j][str[i][j]-'a']==1) putchar(str[i][j]);
		}
		putchar('\n');
	}
	return 0;
}

Robot

题意

题目是原题，CF 583B Robot’s Task。
一个机器人在坐标轴来回走，任务排一行，完成某个任务之前必须满足$a_i$个任务，问机器人最少需要转几次身。

思路

简单模拟即可。

标程

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 <bits/stdc++.h>
using namespace std;

#define FU(i,n) for(int i=0;i<(n);i++)
#define FD(i,n) for(int i=(n)-1;i>=0;i--)

const int INF = 0x3f3f3f3f;

int main()
{	
	int n,a[1000],c,t;
	while(~scanf("%d",&n)){
		FU(i,n) scanf("%d",a+i);
		c = -1;
		t = 0;
		while(t<n){
			c++;
			FU(i,n) if(a[i]<=t) a[i]=INF,t++;
			if(t==n) break;
			c++;
			FD(i,n) if(a[i]<=t) a[i]=INF,t++;
		}
		printf("%d\n",c);
	}
	return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！