不知不觉又过去两期周赛,相应地,题解也落下了。而当我再回去想下载考试报告时。。。
现在更新的速度有这么快了么?
可惜题目还是考过的旧题,尤其对我们这种老油子来说,最大的好处是省去了阅读理解的烦恼。
平心而论,本期四道题,对初学者来说,还是有一定难度的。尤其第二题并查集,和第四题三维背包问题,虽然问哥写过题解,也记得解法,但若是真让我一字不差地背下来,还是有点吃力的。特别是背包问题中的剪枝优化,稍微有点烧脑。
第二题,天然气订单,30期,并查集问题。用其它的做法应该也能通过,但我没试过。理论上不可能会比并查集的复杂度更优了。
第三题,排查网络故障,23期,之前的题解疏忽了边界问题,现已更正。当然,还有更简单的做法,就是一直除2,且向下取整,因为这样做和向上取整+边界问题是等价的——二分的确很简单,但有时候理解起来还是挺麻烦的。
第四题,运输石油,32期,比较麻烦。三维背包的复杂度是 ,好在本题可以通过剪枝来优化。如果不考虑时间复杂度,还可以通过排序来做,也就是深度优先搜索()
第一题,最后一位,放在最后来说,曾在27期考过,但那期我没参加,所以也没写过题解。
小明选择了一个正整数X,然后把它写在黑板上。然后每一天他会擦掉当前数字的最后一位,直到他擦掉所有数位。 在整个过程中,小明会把所有在黑板上出现过的数字记录下来,然后求出他们的总和sum. 例如X = 509, 在黑板上出现过的数字依次是509, 50, 5, 他们的和就是564. 小明现在给出一个sum,小明想让你求出一个正整数X经过上述过程的结果是sum.
输入描述:
输入包括正整数sum(1 ≤ sum ≤ 10^18)
输出描述:
输出一个正整数,即满足条件的X,如果没有这样的X,输出-1。
输入样例:
564
输出样例:
509
本题不难,由题目描述可以很容易发现,原数字不可能大于 sum,所以给出的正整数 sum 就决定了答案的上限。然后从上限开始向下穷举,一个个去试这个题目中计算条件,当找到满足条件的整数时,退出穷举,输出答案即可。如果当计算的结果小于 sum,说明没有符合条件的整数,输出 -1。
def fun(n):
res = 0
while n > 0:
res += n
n //= 10
return res
当然,由上述过程也可以看出答案具有单调性,所以我们也可以找到答案的下限,然后通过二分来做。
答案的下限也很简单。我们假设这个整数有 m 位,除了最高位,其余位数为0,以示例为例,可得,x00 * 111 = 56400,于是可得答案的下限是 56400//111 = 508,再通过上下限进行二分查找即可。文章来源:https://www.toymoban.com/news/detail-428874.html
实际上,多试验几次,就会发现,答案只比这个下限大 1 或 2 的位置,所以从下限开始穷举,比二分还要快。——感觉这应该是个数学现象,直觉上应该有 的公式解法,但问哥数学不好,就不继续推了,感兴趣的童鞋可以留言,谢谢。文章来源地址https://www.toymoban.com/news/detail-428874.html
到了这里,关于CSDN周赛第48期的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!