新手村Ⅳ
一定要先点击左上角的“参与作业”按钮，再开始做练习题哦~
目录
- 前言
- 题目列表
- 注意事项
- 提示
- 0.T323912 予沛赶路
- 1.T380437 精灵分宝石
- 2.T380452 小精灵摘金苹果（升级版）
- 3.T281068 予沛买龙血
- 4.T380451 勇者与宝藏
- 5.T323914 勇者攀登魔法塔
- 6.T281044 予沛驯服独角兽
- 7.T380455 魔法咒文排序挑战
- 8.T380459 远古魔法组合
- 9.T380439 勇者大破迷宫杀机
- Python 3.10 官方文档相关章节
前言
It's harder to read code than to write it.
—— Joel Spolsky
在编程的世界中，读代码比写代码困难。 所以，尽量让自己能读懂你自己写的代码。听起来像一句废话，但做到这一点这并不容易——你真的能读懂你自己写的代码吗？
本次练习的部分题目来自历年 NOIP 普及组（也就是初中组）中的简单题——但不用担心，我们不需要用 C++ 来解决这些问题，在我们手中的工具是易用的 Python。
如果某些题目让你感到没有头绪，可以看看「提示」章节，也许会找到一些灵感。
题目列表
| 序号 | 题目 |
|---|---|
| 0 | T323912 予沛赶路 |
| 1 | T380437 精灵分宝石 |
| 2 | T380452 小精灵摘金苹果（升级版） |
| 3 | T281068 予沛买龙血 |
| 4 | T380451 勇者与宝藏 |
| 5 | T323914 勇者攀登魔法塔 |
| 6 | T380455 魔法咒文排序挑战 |
| 7 | T380459 远古魔法组合 |
| 8 | T281044 予沛驯服独角兽 |
| 9 | T380439 勇者大破迷宫杀机 |
注意事项
- 提交答案时，一定要将语言设置为“Python 3”（默认是 C++）；
- 耐心读题，确保已经理解了题意、数据类型、输入输出要求后再作答；
- 计算机没有玄学，如果
WA (Wrong Answer)了，仔细分析原因，思考为什么出错，带着理由修改代码，而不是盲目修改代码； - 建议不要打印多余的空格和空行。
提示
0. T323912 予沛赶路
细心即可。
1. T380437 精灵分宝石
不要想复杂。
2. T380452 小精灵摘金苹果（升级版）
在对问题求解时，可以总是做出在当前看来是最好的选择——如果选择的方法得当，那么局部最优就是全局最优。
3. T281068 予沛买龙血
每次选单价最小的。
4. T380451 勇者与宝藏
追求性价比即可！
5. T323914 勇者攀登魔法塔
首先，到每一层的步数和到前几层的步数关系如何？
- 和斐波那契数列极其相似！可以使用递归！
其次，题目的数据量较大，如果在实现代码中又出现了 TLE ，可以尝试把计算的结果存下来，避免反复计算。
存储的方式除了字典，这里同样可以使用数组来进行存储运算的结果。这时候，数组中每一个元素的含义是什么？
找到这个关系之后，再思考各个爬塔状态之间的关系，能否总结出一个公式？尝试将这个公式和数组的定义结合起来！
如果你能够想清楚这些问题，那么你已经初步掌握了 动态规划 的思想了！
6. T281044 予沛驯服独角兽
在上一题的基础上，思考以下两个问题：
- 到棋盘上的每一个状态之间的关系是什么？可否用公式来表达出来？
- 如果要使用数组来记录结果，那么数组中元素的含义是什么？
7. T380455 魔法咒文排序挑战
传说中的高中数学知识点：排列。
在编程中，排列同样是经典的递归问题。我们会将这种编程思想称之为「深度优先搜索」。而实现这种思想的方法是 回溯 。
这个算法有一些复杂，但是我们提供了逃课的方式：
- Python 已经提供了快速计算排列的内置方法，可以利用
itertools库中的permutations函数。
8. T380459 远古魔法组合
传说中的高中数学知识点：组合。
在编程中，组合同样是经典的递归问题，它和全排列很相似哦。
相似的，你也可以逃课：
- Python 已经提供了快速计算组合的内置方法，可以利用
itertools库中的combinations函数。
9. T380439 勇者大破迷宫杀机
有深度优先搜索，自然就有广度优先搜索。
如果你用广度优先搜索时发现一直超时，可能是因为用 list 做队列太慢了，可以考虑用 collections 库中的 deque 来加速，它的速度很快。
Python 3.10 官方文档相关章节
官方文档中的一些内容可能对初学者而言过于晦涩，难以理解，所以也不必强迫自己一开始就理解其中的全部内容——等用到时回头再看，自然就会有所感悟。