程序设计实践-201501期末

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