【算法课OJ】上机实验考试
所谓自由，不是随心所欲，而是自我主宰。
链接：http://192.168.173.163/JudgeOnline/contest.php?cid=1118
密码：123854
因为这次题目比较简单，故不给出代码，思路仅供参考。
战况
个人
因为环境良好，第一题拿了一血。然后看第二题，看到公式当场懵逼，考虑时效先跳过这一题。做第三题时不太清醒，先跳过留最后（老师让我上课讲解类似的题，我还讲了三种方法）。然后跑回去看第二题，发现这其实就是输出七进制，直接写了大一时 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: 星空梦想——鲁班
题目描述
鲁班七号是王者峡谷里的射手，站撸英雄。战场上的鲁班七号，机制强大的鲨嘴炮，立刻将挡在前路的任何物体轰飞。正如他所说的，“借你们的肉体试验下新发明的威力”。是的，这就是鲁班大师和他的天才机关造物鲁班七号。然而，鲁班最为致命的缺点是腿短，跑得慢，一个稍不留神，便会被刺客所击杀。
既然腿短，那么就来多多运动吧，跳跳台阶可还行？假设鲁班七号一次可以跳上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: 午夜歌剧——元歌
题目描述
元歌是王者峡谷里的刺客。何谓至高机关之美呢？唯有以至高权力的手令太古奇迹重现人世，方能称得上啊。
是的，元歌擅长操控，所做傀儡能起到以假乱真的作用，今天元歌的傀儡变成你的初中数学老师，给你出个数学题：给你一个数字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，代表最终运算结果。
样例输入
3
7
1433223
193224
样例输出
10
15116331
1433223
提示
测试数据均大于等于1，不用特判0
思路
十进制转七进制，可以使用递归函数。
问题 C: 圣诞恋歌——貂蝉
题目描述
貂蝉是王者峡谷里的法师/刺客，貂蝉打法一定要注意配合技能与被动。半肉出装加上蛇皮走位，往往可以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: 海之征途——孙策
题目描述
孙策是王者峡谷里的坦克/战士。大船靠岸，江郡欢呼着迎来了他们的新领袖，人称江东小霸王的年轻人。游戏中，孙策的技能长帆破浪，可以驾船冲锋，可将船撞向敌方单位或者阻挡物，并造成一定的伤害。
现在，有一群好奇的江郡小朋友想跟着孙策一起出海航行，但孙策的船承载不了所有小朋友，所以孙策决定，尽可能带更多的小朋友出海，现在请你帮孙策谋一个策略，使得更多的小朋友有机会出海航行。已知的条件是孙策船的最大载重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: 极冰防御——盾山
题目描述
盾山是王者峡谷里的辅助，一夫当关、万夫莫开，一个好的辅助往往可以给团队带来极大帮助。
盾山的游戏中的一个技能为不动如山：手握一块由石头组成的巨盾，张开巨盾砸向地面，将敌人推开，并持续一段时间。
假设盾山最多只能承受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/