5.15练习赛部分题题解

A.公交车站

原题

问题描述

上海是个交通繁忙的大都市,有时候没有地图的话很容易迷路。XX想乘公交车去一个地方,但是他拿到的交通图却不完整。

他拿到的交通图是一个由0和1组成的$N*N$的矩阵,$N$为公交车站的数量,第$i$行第$j$列的数表示是否有车从第$i$个车站到第$j$个车站(1为有,0为无)。但是,事实上,如果第$i$个车站能到第$k$个车站,第$k$个车站能到第$j$个车站,那第$i$个车站也能到第$j$个车站(即若$m[i][k]=1且m[k][j]=1则m[i][j]=1$),而交通图上的矩阵把很多此类情况漏掉了。

现在请你帮助XX把他手中的交通图补全,使之成为一个有传递性的矩阵。

输入

输入数据第一行为整数$T$,表示有$T$组测试数据,每组测试数据第一行为一个整数$N$ $(1 ≤ N ≤ 20)$,表示有$N$个公交车站,接下来$N$行为一个$N*N$的矩阵,表示题述的车站间的到达情况。

输出

对每组测试数据,先输出“Case #:”(#为序号,从1起),换行。然后输出补全后的矩阵。

输入样例

1
2
3
4
5
6
7
8
9
10
2
3
101
010
011
4
1100
0100
0011
1001

输出样例

1
2
3
4
5
6
7
8
9
Case 1:
111
010
011
Case 2:
1100
0100
1111
1101

思路

  • $O(n^3)$直接做?

代码

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

int main()
{
int t;
int kase = 0;
cin >> t;
while (t--)
{
char a[20][20];
bool m[20][20];
int n;
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
cin >> a[i][j];
m[i][j] = a[i][j] - '0';
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
if (m[i][k] && m[k][j])
m[i][j] = 1;
cout << "Case " << ++kase << ":" << endl;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cout << m[i][j];
cout << endl;
}
}
return 0;
}

C.取弹珠游戏

原题

叉叉和刀刀在玩取弹珠的游戏,游戏的规则是这样的:地上有n粒弹珠,双方依次从中取弹珠,每次至多取剩余弹珠数量的一半,至少取一粒弹珠,当一方无法再取弹珠时,该方输(也就是地上只剩一粒弹珠时,无法再取,因为1大于1的一半)。
现在叉叉先取弹珠,已知弹珠的数量,那么叉叉是否有必胜的策略呢?请你编程帮他解决这个问题。

输入

输入数据第一行为整数$T$ $(2 ≤ T ≤ 10)$,表示有T组测试数据,接下来$T$行每行为一个整数$n$$(1 ≤ n ≤ 1,000,000,000)$,表示弹珠的数量。

输出

对每组测试数据,输出一行’YES’或者’NO’,分别表示叉叉有必胜的策略和没有必胜的策略。见样例。

输入样例

1
2
3
4
5
4
2
3
6
7

输出样例

1
2
3
4
YES
NO
YES
NO

思路

  • 简单的博弈题。找规律可以发现,弹珠数量为$2^n-1$时取弹珠的人必败。判断一个数是不是2的幂可以使用位运算。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
if (n & (n + 1))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}

E.统计问题

原题

问题描述

XX最近在学习数据结构,遇到了一个统计问题,瞬间就2了,不知道你能不能帮助他。
已知有N个盒子$(1,2,3,4……N)$,现在通过命令$P(a,b)$表示在$[a,b]$的每个盒子中各放一个小球,通过命令$Q(a)$表示查询第$a$个盒子中有多少个小球。

输入

输入文件第一行为整数$T$,表示有$T$组测试数据。
每组测试数据第一行为2个整数,$N$,$M$,$(1<=N<=100000,0<=M<=2000)$
接下来M行,每行为下面两种形式其中之一,
P a b $(1<=a<=b<=N)$
Q a $(1<=a<=N)$

输出

对输入中的每组测试数据的Q a ,一行输出第$a$个盒子中有多少个球。

输入样例

1
2
3
4
5
6
7
8
9
10
11
12
13
2
5 4
Q 2
P 1 4
P 4 5
Q 4
10 6
P 1 10
P 2 5
Q 1
P 3 6
Q 4
Q 10

输出样例

1
2
3
4
5
0
2
1
3
1

思路

  • 区间更新,单点查询的树状数组(BIT)模版题.
  • 据说测试数据比较水,直接做也能过。

代码

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

const int maxn = 100000 + 5;
int C[maxn];
int n;
int lowbit(int x)
{
return (-x) & x;
}
void update(int x, int y)
{
for (int i = x; i > 0; i -= lowbit(i))
C[i] += y;
}
int query(int x)
{
int s = 0;
for (int i = x; i <= n; i += lowbit(i))
s += C[i];
return s;
}

int main()
{
int t;
cin >> t;
while (t--)
{
memset(C, 0, sizeof(C));
int m;
cin >> n >> m;
while (m--)
{
char cmd;
cin >> cmd;
if (cmd == 'P')
{
int a, b;
cin >> a >> b;
update(b, 1);
update(a - 1, -1);
}
else
{
int a;
cin >> a;
cout << query(a) << endl;
}
}
}
return 0;
}

F.谁拿了最多奖学金

原题

问题描述

某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种,获取的条件各自不同:

  1. 院士奖学金,每人8000元,期末平均成绩高于80分(>80),并且在本学期内发表1篇或1篇以上论文的学生均可获得;
  2. 五四奖学金,每人4000元,期末平均成绩高于85分(>85),并且班级评议成绩高于80分(>80)的学生均可获得;
  3. 成绩优秀奖,每人2000元,期末平均成绩高于90分(>90)的学生均可获得;
  4. 西部奖学金,每人1000元,期末平均成绩高于85分(>85)的西部省份学生均可获得;
  5. 班级贡献奖,每人850元,班级评议成绩高于80分(>80)的学生干部均可获得;

只要符合条件就可以得奖,每项奖学金的获奖人数没有限制,每名学生也可以同时获得多项奖学金。例如姚林的期末平均成绩是87分,班级评议成绩82分,同时他还是一位学生干部,那么他可以同时获得五四奖学金和班级贡献奖,奖金总数是4850元。

现在给出若干学生的相关数据,请计算哪些同学获得的奖金总数最高(假设总有同学能满足获得奖学金的条件)。

输入

输入有多组测试数据。每组的第一行是一个整数$N$ $(1<=N<=100)$,表示学生的总数。接下来的N行每行是一位学生的数据,从左向右依次是姓名,期末平均成绩,班级评议成绩,是否是学生干部,是否是西部省份学生,以及发表的论文数。姓名是由大小写英文字母组成的长度不超过20的字符串(不含空格);期末平均成绩和班级评议成绩都是0到100之间的整数(包括0和100);是否是学生干部和是否是西部省份学生分别用一个字符表示,Y表示是,N表示不是;发表的论文数是0到10的整数(包括0和10)。每两个相邻数据项之间用一个空格分隔。

输出

对每组输入数据,输出三行,第一行是获得最多奖金的学生的姓名,第二行是这名学生获得的奖金总数。如果有两位或两位以上的学生获得的奖金最多,输出他们之中在输入文件中出现最早的学生的姓名。第三行是这N个学生获得的奖学金的总数。

输入样例

1
2
3
4
5
4
YaoLin 87 82 Y N 0
ChenRuiyi 88 78 N Y 1
LiXin 92 88 N N 0
ZhangQin 83 87 Y N 1

输出样例

1
2
3
ChenRuiyi
9000
28700

思路

  • 简单维护一下数据,直接做就好。

代码

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

int main()
{
int n;
while (cin >> n)
{
string name, max_name;
int fin, cls, pas, money, max_money = 0, sum = 0;
char m, w;
bool moni, west;
while (n--)
{
cin >> name >> fin >> cls >> m >> w >> pas;
moni = m == 'Y' ? 1 : 0;
west = w == 'Y' ? 1 : 0;
money = 0;
if (fin > 80 && pas >= 1)
money += 8000;
if (fin > 85 && cls > 80)
money += 4000;
if (fin > 90)
money += 2000;
if (fin > 85 && west)
money += 1000;
if (cls > 80 && moni)
money += 850;
sum += money;
if (money > max_money)
{
max_money = money;
max_name = name;
}
}
cout << max_name << endl;
cout << max_money << endl;
cout << sum << endl;
}
return 0;
}

G.货币系统

原题

问题描述

XX做梦来到了一个神奇的世界,这个世界的货币系统与我们常见的不同,XX对货币的数值感到十分好奇。

传统地,一个货币系统是由$1,5,10,20$或$25,50$和$100$的单位面值组成的。

XX想知道有多少种不同的方法来用货币系统中的货币来构造一个确定的数值。
举例来说,使用一个货币系统$\lbrace1,2,5,10,…\rbrace$产生 $18$单位面值的一些可能的方法是:$18\times1,9\times2,8\times2+2\times1,3\times5+2+1$等等。写一个程序来计算用给定的货币系统来构造一定数量的面值有多少种方法。保证总数将会适合long long (C/C++),即在$0$ 到$2^{63}-1$之间。

输入

货币系统中货币的种类数目是 $V$ $(1<=V<=25)$。要构造的数量钱是 $N$ $(1<= N<=10,000)$。

输入数据第一行为整数$T$ $(T ≤ 15)$,表示有$T$组测试数据,每组测试数据第一行为两个整数:$V$和$N$,第二行为$V$个整数,表示可用的货币面值。

输出

对每组测试数据,在一行中输出用这$V$种硬币凑足$N$单位货币的方案数。

输入样例

1
2
3
1
3 10
1 2 5

输出样例

1
10

思路

  • 设$f[i,j]$表示用前$i$种硬币能表示$j$数量货币的方法数,则$$f[i,j]=f[i-1,j]+f[i-1,j-a[i]]$$
  • 即前$i$种硬币能表示$j$货币的方法=不用第$i$种硬币能表示的$j$货币的方法+用上第$i$种货币能表示$j$货币的方法。
  • 当然这个方程在空间上还可以简化为一维的。所以最后部分的核心代码就是:
1
2
3
for (int j=0;j<V;j++)
for (int i=a[j];i<=N;i++)
f[i]+=f[i-a[j]];

代码

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

int main()
{
int t;
cin >> t;
while (t--)
{
int V, N;
long long dp[10002];
memset(dp, 0, sizeof(dp));
dp[0] = 1;
cin >> V >> N;
while (V--)
{
int v;
cin >> v;
for (int i = v; i <= N; i++)
dp[i] += dp[i - v];
}
cout << dp[N] << endl;
}
return 0;
}
捐助作者