一、实操题
1、陶陶摘苹果
【问题描述】
陶陶家的院子里有一棵苹果树，每到秋天树上就会结出10个苹果。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有个30厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。
现在已知10个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。
【输入文件】
输入文件apple.in包括两行数据。第一行包含10个100到200之间（包括100和200）的整数（以厘米为单位）分别表示10个苹果到地面的高度，两个相邻的整数之间用一个空格隔开。第二行只包括一个100到120之间（包含100和120）的整数（以厘米为单位），表示陶陶把手伸直的时候能够达到的最大高度。
【输出文件】
输出文件apple.out包括一行，这一行只包含一个整数，表示陶陶能够摘到的苹果的数目。
【样例输入】
100 200 150 140 129 134 167 198 200 111
110
【样例输出】
5
参考答案：陶陶能够摘到的苹果的数目为5。
解析：【喵呜刷题小喵解析】：
首先，我们需要读取输入文件apple.in中的两行数据。第一行包含10个苹果到地面的高度，第二行表示陶陶把手伸直的时候能够达到的最大高度。
然后，我们需要遍历这10个苹果的高度，判断陶陶能否摘到每个苹果。具体地，我们需要比较每个苹果的高度和陶陶的最大高度。如果某个苹果的高度小于等于陶陶的最大高度，那么陶陶就能够摘到这个苹果。
最后，我们统计陶陶能够摘到的苹果的数目，并将结果输出到输出文件apple.out中。
对于样例输入，10个苹果的高度分别为100, 200, 150, 140, 129, 134, 167, 198, 200, 111，陶陶的最大高度为110。陶陶能够摘到的苹果的高度分别为100, 150, 140, 129, 111，因此陶陶能够摘到的苹果的数目为5。
2、校门外的树
【问题描述】
某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
【输入文件】
输入文件tree.in的第一行有两个整数：L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
【输出文件】
输出文件tree.out包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
【样例输入】
500 3
150 300
100 200
470 471
【样例输出】
298
【数据规模】
对于20%的数据，区域之间没有重合的部分；
对于其它的数据，区域之间有重合的情况。
参考答案：对于这个问题，我们可以使用差集的思想来解决。首先，统计马路上原本有多少棵树，即L+1棵。然后，对于每个区域，统计该区域覆盖了多少棵树。最后，将马路上原本有的树的数量减去所有区域覆盖的树的数量，即可得到马路上剩余的树的数目。具体实现时，我们可以使用一个变量total_trees来保存马路上原本有的树的数量，初始值为L+1。对于每个区域，我们可以计算该区域的长度，即终止点坐标减去起始点坐标，然后将其加1（因为区域端点处的两棵树也要被覆盖），得到一个变量region_trees。然后，将region_trees从total_trees中减去，即可得到该区域覆盖的树的数量。最后，将所有区域覆盖的树的数量累加起来，即为所有区域覆盖的树的总数量。最后，将马路上原本有的树的数量减去所有区域覆盖的树的总数量，即可得到马路上剩余的树的数目。
解析：【喵呜刷题小喵解析】：
这个问题可以使用差集的思想来解决。差集是指两个集合的差，即在一个集合中但不在另一个集合中的元素。在这个问题中，我们可以将马路上原本有的树看作一个集合，将每个区域覆盖的树看作另一个集合。我们需要找出这两个集合的差集，即马路上剩余的树的数目。
具体实现时，我们可以使用一个变量total_trees来保存马路上原本有的树的数量，初始值为L+1。对于每个区域，我们可以计算该区域的长度，即终止点坐标减去起始点坐标，然后将其加1（因为区域端点处的两棵树也要被覆盖），得到一个变量region_trees。然后，将region_trees从total_trees中减去，即可得到该区域覆盖的树的数量。最后，将所有区域覆盖的树的数量累加起来，即为所有区域覆盖的树的总数量。最后，将马路上原本有的树的数量减去所有区域覆盖的树的总数量，即可得到马路上剩余的树的数目。
需要注意的是，如果区域之间有重合的部分，我们需要将重合部分覆盖的树的数量重复计算。因此，在计算每个区域覆盖的树的数量时，我们需要将region_trees累加到一个变量covered_trees中，而不是直接将其从total_trees中减去。最后，将covered_trees从total_trees中减去，即可得到马路上剩余的树的数目。
在实际实现时，我们可以使用数组或者数据结构来存储区域的信息，以便快速计算每个区域覆盖的树的数量。同时，需要注意处理输入数据的合法性和范围，避免程序出错或者产生错误的输出结果。
3、采药
【问题描述】
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
【输入文件】
输入文件medic.in的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
【输出文件】
输出文件medic.out包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
【样例输入】
70 3
71 100
69 1
1 2
【样例输出】
3
【数据规模】
对于30%的数据，M <= 10；
对于全部的数据，M <= 100。
参考答案：对于这个问题，我们可以使用动态规划来解决。我们可以定义一个数组dp，其中dp[i]表示在i分钟内可以获得的最大价值。然后，我们可以遍历每一株草药，对于每一株草药，我们可以计算采摘这株草药后剩余的时间t，然后更新dp[t+采摘时间] = max(dp[t+采摘时间], dp[t] + 该株草药的价值)。最后，dp[T]就是我们要找的答案。
解析：【喵呜刷题小喵解析】：
这个问题是一个典型的动态规划问题。我们可以使用动态规划来解决。首先，我们需要定义一个数组dp，其中dp[i]表示在i分钟内可以获得的最大价值。然后，我们可以遍历每一株草药，对于每一株草药，我们可以计算采摘这株草药后剩余的时间t，然后更新dp[t+采摘时间] = max(dp[t+采摘时间], dp[t] + 该株草药的价值)。这样，我们就可以保证在采摘这株草药后，剩余的时间内可以获得的最大价值被正确地计算出来。最后，dp[T]就是我们要找的答案，即在规定的时间内，可以采到的草药的最大总价值。
这个问题的时间复杂度是O(TM)，其中T是总时间，M是草药的数目。这个算法的时间复杂度是可以接受的，因为M的最大值是100，而T的最大值是1000，所以总的时间复杂度是O(100000)，在可以接受的范围内。
在编程实现时，我们需要先读入T和M，然后读入每一株草药的时间和价值，然后初始化dp数组，遍历每一株草药，更新dp数组，最后输出dp[T]。
对于样例输入，T=70，M=3，草药的时间和价值分别为(71, 100), (69, 1), (1, 2)。我们可以按照上述算法进行计算，得到dp数组为(0, 0, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
4、循环
【问题描述】
乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天，他突然对数的正整数次幂产生了兴趣。
众所周知，2的正整数次幂最后一位数总是不断的在重复2，4，8，6，2，4，8，6……我们说2的正整数次幂最后一位的循环长度是4（实际上4的倍数都可以说是循环长度，但我们只考虑最小的循环长度）。类似的，其余的数字的正整数次幂最后一位数也有类似的循环现象：
这时乐乐的问题就出来了：是不是只有最后一位才有这样的循环呢？对于一个整数n的正整数次幂来说，它的后k位是否会发生循环？如果循环的话，循环长度是多少呢？
注意：
1． 如果n的某个正整数次幂的位数不足k，那么不足的高位看做是0。
2． 如果循环长度是L，那么说明对于任意的正整数a，n的a次幂和a + L次幂的最后k位都相同。
【输入文件】
输入文件circle.in只有一行，包含两个整数n（1 <= n < 10100）和k（1 <= k <= 100），n和k之间用一个空格隔开，表示要求n的正整数次幂的最后k位的循环长度。
【输出文件】
输出文件circle.out包括一行，这一行只包含一个整数，表示循环长度。如果循环不存在，输出-1。
【样例输入】
32 2
【样例输出】
4
【数据规模】
对于30%的数据，k <= 4；
对于全部的数据，k <= 100。
参考答案：对于输入的n和k，我们需要找到n的正整数次幂的最后k位的循环长度。首先，我们可以观察到，对于任何正整数n，它的正整数次幂的最后几位的循环规律都遵循一个模运算的性质，即$n^a \mod 10^k = n^a+L \mod 10^k$，其中L是循环长度。为了找到循环长度，我们可以从1开始，计算$n^1, n^2, n^3, ...$，直到找到两个相邻的次幂的最后k位相同为止。此时，这两个次幂之间的差值就是循环长度L。具体的算法如下：1. 初始化两个变量prev和curr，分别表示上一次和当前次幂的最后k位。2. 从1开始，计算$n^i$，直到找到两个相邻的次幂的最后k位相同为止。3. 如果找到了循环，返回循环长度i-j，其中j是上一次和当前次幂相同的次幂。4. 如果没有找到循环，返回-1。
解析：【喵呜刷题小喵解析】：
这个题目考察的是模运算的性质和循环规律。对于任何正整数n，它的正整数次幂的最后几位的循环规律都遵循一个模运算的性质，即$n^a \mod 10^k = n^{a+L} \mod 10^k$，其中L是循环长度。这个性质说明，当n的次幂的位数超过k时，它的最后k位会开始循环。
我们可以通过计算n的次幂来找到循环长度。具体的算法是从1开始，计算$n^1, n^2, n^3, ...$，直到找到两个相邻的次幂的最后k位相同为止。此时，这两个次幂之间的差值就是循环长度L。
对于输入的n和k，我们可以使用上述算法来找到循环长度。如果循环存在，我们返回循环长度；如果循环不存在，我们返回-1。
需要注意的是，由于n的次幂可能会非常大，我们需要在计算过程中使用模运算来避免溢出。同时，由于k的最大值是100，我们需要使用高精度算法来计算n的次幂的最后k位。
另外，由于题目中给出的数据规模较小，我们可以使用暴力算法来解决问题。对于30%的数据，k <= 4，我们可以直接计算n的4次幂来找到循环长度。对于全部的数据，k <= 100，我们需要使用上述算法来找到循环长度。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
