上期问哥没参加,但从赛后大家的反馈来看,又出现了数据上的bug,使用 python 的朋友会遇到第二个用例的柱子高度数组长度不够,200根柱子,只有179个数据,这让人怎么玩?但是用C++的选手就没有这个问题。不禁让问哥想起另外几道使用 python 永远无法AC的每日一练(津津的储蓄计划与拯救爱情等),感受到C站对python的森森恶意。
可能C站人手实在不够吧,连必要的数据校验都做不到(摊手)。
第一题:小鱼的航程(改进版)
有一只小鱼,它上午游泳150公里,下午游泳100公里,晚上和周末都休息(实行双休日),假设从周x(1<=x<=7)开始算起,请问这样过了n天以后,小鱼一共累计游泳了多少公里呢?
分析
本题没什么难点,就是朴素的数学模拟计算。只要计算出从周 x 算起,到第 n 天后,共度过了多少个工作日,然后乘以 250 就是答案。
要注意的是,周 x 当天也算。
参考代码
def solution(self, x, n):r = 8-xif n > r:days = max(0, r-2) + 5*((n-r)//7) + min(5, (n-r)%7)else:days = min(x+n-1, 6-x)return max(0, 250*days)
第二题:编码
编码工作常被运用于密文或压缩传输。这里我们用一种最简单的编码方式进行编码:把一些有规律的单词编成数字。字母表中共有26个字母{a,b,…,z},这些特殊的单词长度不超过6且字母按升序排列。把所有这样的长度相同的单词放在 一起,按字典顺序排列,一个单词的编码就对应着它在整个序列中的位置。 你的任务就是对于所给的单词,求出它的编码。
分析
14期考过,可以参考问哥之前写的详细题解。现在看来没什么难度,暴力应该就可以过。
第三题:一维数组的最大子数组和
给定一个整数数组 nums ,找到一个具有最大和的连续子数组,输出该子数组在原数组中的开始下标和结束下标。原数组下标从0开始。
分析
一维数组的最大子数组和我们已经很熟悉了,动态规划或贪心算法的入门操作。本题是在此基础上要输出最大子数组和的起始下标。所以问哥就懒得改了,直接在求最大和的代码基础上增加一个元组,记录起始下标即可。
参考代码
def solution(self, n, arr):if n<=1: return 0,0result = temp = arr[0]start = end = 0ans = (0, 0)for i in range(1, n):if arr[i] > arr[i]+temp:start = itemp = arr[i]else:temp += arr[i]end += 1if temp > result:result = tempans = (start, end)return ans
第四题:喜水青蛙
总是喜欢在水里嬉戏的青蛙,某天要过河拜访一位朋友。已知河道中长满了带刺的不知名生物,能通过的路只有一条直线,长度为L。 直线上随机分布着m块石头。青蛙的最小跳跃距离是s,最大跳跃距离是t。 青蛙想要尽可能的少踩石头,那么它通过河道最少会踩到多少石头?
分析
以前考过的NOIP原题,十几天前刚写过详细的题解,带着粉丝们复习过,也算是押题成功了吧?
别的不多说,本题有两个难点:
- 正确理解题意。青蛙并不是一定要踩着石头才能过河,原题是独木桥,可能还好理解一点,C站换成了直线。。。嗯,问哥只能说,读不懂的不止你一个。
- 路径需要压缩,但是和 (最小公倍数)毫无干系。问哥的题解里已经详细指出了,这里也是提醒不要被网上某些不负责任的题解给带偏了。