16级算法分析与设计上机考试

http://192.168.173.163/JudgeOnline/contest.php?cid=1118

密码:123854

由于是去年的考试题已经不能再提交运行,代码运行输出仅满足给出的测试样例,不能保证能够AC,仅供参考。

星空梦想——鲁班

题目描述

鲁班七号是王者峡谷里的射手,站撸英雄。战场上的鲁班七号,机制强大的鲨嘴炮,立刻将挡在前路的任何物体轰飞。正如他所说的,“借你们的肉体试验下新发明的威力”。是的,这就是鲁班大师和他的天才机关造物鲁班七号。然而,鲁班最为致命的缺点是腿短,跑得慢,一个稍不留神,便会被刺客所击杀。

既然腿短,那么就来多多运动吧,跳跳台阶可还行?假设鲁班七号一次可以跳上1级台阶,但极限一次只能跳上2级台阶(腿短没办法,嘤嘤嘤)。鲁班七号现在从0级阶梯开始,最终跳上第n级的台阶,求总共有多少种跳法?

输入

多组测试用例。

第一行输入包含一个整数T(1<=T<=50),代表测试用例个数。

接下来T行,每行输入包含一个整数n(1<=n<=50),代表鲁班最终跳上了第n级台阶。

输出

每组测试用例对应一行输出,每行输出一个整数ans,代表鲁班最终跳上第n级台阶的跳法种数。

样例输入

1
2
3
4
3
3
4
50

样例输出

1
2
3
3
5
20365011074

考查知识点

斐波拉契数列

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
long long dp[51];
cin >> t;
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i < 51; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
while (t--) {
int n;
cin >> n;
cout << dp[n] << endl;
}
return 0;
}

午夜歌剧——元歌

题目描述

元歌是王者峡谷里的刺客。何谓至高机关之美呢?唯有以至高权力的手令太古奇迹重现人世,方能称得上啊。

是的,元歌擅长操控,所做傀儡能起到以假乱真的作用,今天元歌的傀儡变成你的初中数学老师,给你出个数学题:给你一个数字x,让你求出k7、k6、k5、k4、k3、k2、k1、k0(0<=ki<=9),使得以下等式1成立,最后根据等式2求出最终ans值。

等式1:

等式2:

输入

多组测试用例。

第一行输入包含一个整数T(1<=T<=1000),代表测试用例个数。

接下来T行,每一行包含一个整数x(1<=x<=1500000)。

输出

每组测试用例对应一行输出,每行输出一个整数ans,代表最终运算结果。

样例输入

1
2
3
4
3
7
1433223
193224

样例输出

1
2
3
10
15116331
1433223

考查知识点

进制转化

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int x;
cin >> x;
int ans = 0;
int q = x, r;
int k = 0;
while (q > 0) {
r = q % 7;
q = q / 7;
ans = ans + r * pow(10, k);
k++;
}
cout << ans << endl;
}
return 0;
}

圣诞恋歌——貂蝉

题目描述

貂蝉是王者峡谷里的法师/刺客,貂蝉打法一定要注意配合技能与被动。半肉出装加上蛇皮走位,往往可以1打5,轻松拿下5杀。语花印被动描述为:技能命中会为敌人叠加花之印记,叠加满4层后印记触发被动,会给自身回复生命,同时会对周围敌人造成真实伤害并减速。
我们现在对貂蝉的技能及被动进行简化如下:每使用1次技能会攻击1次目标,每攻击3次目标,会自动额外攻击1次目标。
现在,貂蝉在游戏中使用了n次技能,请问总共会给目标带来多少次攻击。

输入

多组测试数据,第一行输入包含一个整数T,代表测试样例个数。
接下来T行,每行输入包含一个整数n(1<=n<=100),代表貂蝉使用了n次技能。

输出

每组测试用例对应一行输出,每行输出一个整数ans,代表貂蝉对目标进行了ans次攻击。

样例输入

1
2
3
4
5
6
7
6
1
2
3
4
5
81

样例输出

1
2
3
4
5
6
1
2
4
5
7
121

考查知识点

汽水瓶问题:递归

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
int n;
int ans = 0;

void count(int x) {
if (x < 3) return;
ans = ans + x / 3;
int t = (x / 3) + x % 3;
count(t);
}

int main() {
int t;
cin >> t;
while (t--) {
cin >> n;
ans = n;
count(n);
cout << ans << endl;
}
return 0;
}

海之征途——孙策

题目描述

孙策是王者峡谷里的坦克/战士。大船靠岸,江郡欢呼着迎来了他们的新领袖,人称江东小霸王的年轻人。游戏中,孙策的技能长帆破浪,可以驾船冲锋,可将船撞向敌方单位或者阻挡物,并造成一定的伤害。

现在,有一群好奇的江郡小朋友想跟着孙策一起出海航行,但孙策的船承载不了所有小朋友,所以孙策决定,尽可能带更多的小朋友出海,现在请你帮孙策谋一个策略,使得更多的小朋友有机会出海航行。已知的条件是孙策船的最大载重m,以及n个小朋友的体重。

输入

多组测试用例。
第一行输入包含一个整数T(1<=T<=1000),代表测试用例个数。

每组测试用例第一行有两个整数m和n。(0<=m<=1000, 0<=n<=1000),分别代表船的载重重量和小朋友的个数,接下来一行为n个小朋友的体重。

输出

每组测试用例对应一行输出,每行输出一个整数ans,代表最多能有ans个小朋友跟着一起出海。

样例输入

1
2
3
4
5
2
10 4
3 5 2 4
20 9
3 5 2 4 6 1 8 5 9

样例输出

1
2
3
6

考查知识点

贪心算法

代码

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;

int main() {
int t;
int a[1001];
cin >> t;
while (t--) {
int m, n;
int ans = 0;
cin >> m >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n);
for (int i = 0; i < n; i++) {
if (m >= a[i]) {
ans++;
m -= a[i];
}
else break;
}
cout << ans << endl;
}
return 0;
}

极冰防御——盾山

题目描述

盾山是王者峡谷里的辅助,一夫当关、万夫莫开,一个好的辅助往往可以给团队带来极大帮助。

盾山的游戏中的一个技能为不动如山:手握一块由石头组成的巨盾,张开巨盾砸向地面,将敌人推开,并持续一段时间。

假设盾山最多只能承受C重量的盾牌,而现在有N个小石头,每个石头i的重量为Wi,防御值为Pi。那么,呆萌的盾山想知道,他从N个小石头中挑选M个(M<=N)组成他可承受盾牌,最大的防御值是多少?

输入

多组测试用例。
第一行输入包含一个整数T(1<=T<=10),代表测试用例个数。

接下来有T组测试用例。每组测试用例第一行为盾山承受盾牌的最大重量C(C<10000)和小石头的个数N(N<1000)。接下来的N行分别为小石头的重量Wi(1<=Wi<=100)和防御值Pi(1<=Pi<=3000000)。

输出

每组测试用例对应一行输出,每行输出一个整数ans,代表可承受盾牌的最大防御值。

样例输入

1
2
3
4
5
6
7
1
10 5
2 6
2 3
6 5
5 4
4 6

样例输出

1
15

考查知识点

01背包问题

代码

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
#include<bits/stdc++.h>
using namespace std;
struct stone {
long long w;
long long v;
};

long long m[1003][10003];
stone a[1001];

int main() {
int t;
int c, n;
cin >> t;
while (t--) {
memset(m, 0, sizeof(m));
memset(a, 0, sizeof(a));
cin >> c >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].w >> a[i].v;
}
for (int i = 1; i < a[n].w; i++) {
m[n][i] = 0;
}
for (int i = a[n].w; i <= c; i++) {
m[n][i] = a[n].v;
}
for (int i = n - 1; i >= 1; i--) {
for (int j = 1; j < a[i].w; j++) {
m[i][j] = m[i + 1][j];
}
for (int j = a[i].w; j <= c; j++) {
m[i][j] = max(m[i + 1][j], m[i + 1][j - a[i].w] + a[i].v);
}
}
cout << m[1][c] << endl;
}
return 0;
}
-------------end ♥-------------