新手村（下）
一定要先点击左上角的“参与作业”按钮，再开始做练习题哦~
目录
前言
题目列表
注意事项
提示
- T323894 「要有光」
- T323913 勇者的魔法统计图
- T533436 魔法鱼比可爱
- T676174 神秘的报数游戏
- T671833 哥德巴赫猜想
- T584092 村长的答疑会
- T281068 宏宇买龙血
- T676167 精力管理大师
- T323914 勇者攀登魔法塔
- T281044 宏宇驯服独角兽
Python 3.10 官方文档相关章节
前言
Make it run. Make it right. Make it faster.
—— Kent Beck
在编写程序的过程中，让代码先跑起来永远是最重要的。
本次新手村的内容部分来自洛谷「普及-」的题库中，开始涉及一些算法思想和优化方法，可能会有一些难度。
如果有些题目让你感到无从下手，可以看看 「提示」章节，或许会给你带来一些思路。
题目列表
| 序号 | 题目编号与标题 | 知识点 |
|---|---|---|
| 0 | T323894 「要有光」 | 模拟 |
| 1 | T323913 勇者的魔法统计图 | 模拟 |
| 2 | T533436 魔法鱼比可爱 | 循环结构 & 分支结构 |
| 3 | T676174 神秘的报数游戏 | 队列 & 模拟 |
| 4 | T671833 哥德巴赫猜想 | 搜索 |
| 5 | T584092 村长的答疑会 | 贪心 |
| 6 | T281068 宏宇买龙血 | 贪心 |
| 7 | T676167 精力管理大师 | 贪心 |
| 8 | T323914 勇者攀登魔法塔 | 递归 & 动态规划 |
| 9 | T281044 宏宇驯服独角兽 | 动态规划 |
注意事项
- 提交答案时，一定要将语言设置为“Python 3”（默认是 C++）；
- 耐心读题，确保已经理解了题意、数据类型、输入输出要求后再作答；
- 计算机没有玄学，如果
WA (Wrong Answer)了，仔细分析原因，思考为什么出错，带着理由修改代码，而不是盲目修改代码；如果出现TLE(Time Limit Exceeded)说明当前的代码处理速度慢，需要优化代码的实现方法，可以参考「提示」章节的内容来进行优化。 - 建议不要打印多余的空格和空行。
提示
0. T323894 「要有光」
如果没有魔法矿石和火把，这个世界将是一片黑暗。
所以，哪里亮了点哪里。
——善良的助教
1. T323913 勇者的魔法统计图
- 这是一道复杂的
模拟题 。 - 统计图看起来有点复杂，但如果把它抽象一个二维的
list呢？ - 统计字母出现次数这件事很简单，但有一些需要注意的：
- 首先，每一个字母都要出现。
- 其次，怎么把频次转换成带
*的序列呢？
2. T533436 魔法鱼比可爱
- 如果输入有两行，如何分别读取输入的数据?——分别使用两个变量存储
input()的内容就好了
n = int(input())
a = list(map(int, input().split()))
- 需要写双重
for 循环，遍历输入的list，将每一个值和列表中的其他值比较、计数，得到结果。 - 还需要创建一个新的
list，存放结果并输出。
进阶：你可以尝试只用一个循环来完成这个任务吗？
3. T676174 神秘的报数游戏
- 不要想复杂。
- 既然是按圈报数，说明序列是
循环的，既然是循环，就可以用求模来处理。 - 进阶的解法需要使用
队列这一数据结构。
4. T671833 哥德巴赫猜想
- 质数：指的是一个自然数仅仅能被1和自己整除的数（换言之，被除了自己和1，被任何数取模都不为0），2是最小的质数，
也是偶数里唯一的质数。- 判断一个数是不是质数，通过暴力循环就可以实现。
- 判断一个数
n是不是可以由两个质数加和得到：同样可以通过暴力循环实现，找出比n小的数里哪一些符合条件即可。 - 如果你实现了以上两个功能，那么大概率已经可以通过部分测试了，但是会出现
TLE。 - 优化解法：
- 筛选质数：如果是大于2的偶数，一定不是质数，这样可以快速筛掉一半的数。在剩下的数中，我们只需要关注目标数
n的平方根小的那一些数就可以了（容易证明）。
- 筛选质数：如果是大于2的偶数，一定不是质数，这样可以快速筛掉一半的数。在剩下的数中，我们只需要关注目标数
5. T584092 村长的答疑会
只要不想复杂，这道题就非常简单；但如果想复杂了，这道题就非常复杂。
大胆一些，大力出奇迹！
——前几任善良助教的谏言
这一任善良助教的谏言：
- 这是一个很简单的
贪心策略问题。局部最优能推出全局最优！ - 小学奥数告诉我们，只要时间短的排前面，那么总体的等待时间一定是最短的。
6. T281068 予沛买龙血
贪心策略：每次选单价最小的。
7. T676167 精力管理大师
这是一个稍微有一点复杂的贪心策略问题，但思路和上一题比较相似，都是需要找到局部最优的条件。
- 提示：产生负收益的一定不是最优解。
8. T323914 勇者攀登魔法塔
首先，到每一层的步数和到前几层的步数关系如何？
- 和斐波那契数列极其相似！可以使用递归！
其次，题目的数据量较大，如果在实现代码中又出现了 TLE ，可以尝试把计算的结果存下来，避免反复计算。
存储的方式除了字典，这里同样可以使用数组来进行存储运算的结果。这时候，数组中每一个元素的含义是什么？
找到这个关系之后，再思考各个爬塔状态之间的关系，能否总结出一个公式？尝试将这个公式和数组的定义结合起来！
如果你能够想清楚这些问题，那么你已经初步掌握了 动态规划 的思想了！
9. T281044 宏宇驯服独角兽
在上一题的基础上，思考以下两个问题：
- 到棋盘上的每一个状态之间的关系是什么？可否用公式来表达出来？
- 如果要使用数组来记录结果，那么数组中元素的含义是什么？
Python 3.10 官方文档相关章节
官方文档中的一些内容可能对初学者而言过于晦涩，难以理解，所以也不必强迫自己一开始就理解其中的全部内容——等用到时回头再看，自然就会有所感悟。