【算法课OJ】上机实验考试

Author Avatar
source. 11月 07, 2018
  • 在其它设备中阅读本文章

所谓自由,不是随心所欲,而是自我主宰。


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

密码:123854

因为这次题目比较简单,故不给出代码,思路仅供参考。

战况

个人

img

因为环境良好,第一题拿了一血。然后看第二题,看到公式当场懵逼,考虑时效先跳过这一题。做第三题时不太清醒,先跳过留最后(老师让我上课讲解类似的题,我还讲了三种方法)。然后跑回去看第二题,发现这其实就是输出七进制,直接写了大一时 C++ 实验课上助教教的递归方程方法。第四题我一看到就开始写 0-1 背包,写完发现只要求个最多人数,那时候觉得后面可能会遇到0-1背包,故先保存代码,改用贪心。第五题果然是 0-1 背包,修改代码后仔细检查交了AC(当时判题贼慢,等了超久返回信息才返回 AC)。第三题又改了超久,终于过了,真的好尴尬。考完试我跟老师说了我汽水瓶那题想了超久都搞不出,老师说,你上课讲的三种方法一种都想不起来了吗?😳

总体

按题目

题目编号 标题 正确 提交 正确率
A 星空梦想——鲁班 102 271 0.38
B 午夜歌剧——元歌 94 166 0.57
C 圣诞恋歌——貂蝉 100 209 0.48
D 海之征途——孙策 68 178 0.38
E 海之征途——孙策 52 213 0.24

按AC题数

AC题数 基础分 人数 占比
5(AK) 90 34 0.25
4 80 36 0.27
3 70 16 0.12
2 60 17 0.13
1 50 20 0.15
0 0 11 0.08

问题 A: 星空梦想——鲁班

题目描述

img

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

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

输入

多组测试用例。

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

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

输出

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

样例输入

3
3
4
50

样例输出

3
5
20365011074

提示

注意结果超过int范围,请用long long类型存储ans

思路

Fibonacci数列。

问题 B: 午夜歌剧——元歌

题目描述

img

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

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

等式1:

img

等式2:

img

输入

多组测试用例。

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

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

输出

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

样例输入

3
7
1433223
193224

样例输出

10
15116331
1433223

提示

测试数据均大于等于1,不用特判0

思路

十进制转七进制,可以使用递归函数。

问题 C: 圣诞恋歌——貂蝉

题目描述

img

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

输入

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

输出

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

样例输入

6
1
2
3
4
5
81

样例输出

1
2
4
5
7
121

提示

没思路,喝瓶汽水冷静下?

思路

递归函数。

问题 D: 海之征途——孙策

题目描述

img

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

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

输入

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

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

输出

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

样例输入

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

样例输出

3
6

思路

贪心。

问题 E: 极冰防御——盾山

题目描述

img

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

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

假设盾山最多只能承受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
10 5
2 6
2 3
6 5
5 4
4 6

样例输出

15

提示

结果可能超过int范围,请使用long long类型变量

思路

dp,0-1背包问题。

本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明来自 ComyDream
本文链接:http://comydream.github.io/2018/11/07/algorithm-experiment-exam/