腾讯0901笔试题第二题求思路

大佬们第二题有做出来的吗 求思路。。。

#腾讯#
全部评论
用dp的方法。 [t,k] = list(map(int,input().split())) maxn = int(1e5 + 100) dp = [[0]*2 for _ in range(maxn)] dp[1][1] = 1 dp[k][0] = 1 ans = [0]*maxn for i in range(1,100000):     dp[i+k][0] += (dp[i][0] + dp[i][1])     dp[i+1][1] += (dp[i][0] + dp[i][1])     ans[i] = ans[i-1] + dp[i][0] + dp[i][1] while t:     [a,b] = list(map(int,input().split()))     print(ans[b] - ans[a-1])     t -= 1 最后不知道过了多少,快要交卷了
点赞 回复 分享
发布于 2019-09-01 22:17
O(n*logn)复杂度的 import sys if __name__ == "__main__":     t,k=sys.stdin.readline().strip().split()     t,k=int(t),int(k)     for _ in range(t):         a,b=sys.stdin.readline().strip().split()         a,b=int(a),int(b)         times=0         count=0         for i in range(a,b+1):             white = 0             times=0             while white<=i:                 if white==0:                     count+=1                 else:                     count+=i-white+1                 times+=1                 white = times * k         print(count) 简化为O(n)的代码: import sys if __name__ == "__main__":     t,k=sys.stdin.readline().strip().split()     t,k=int(t),int(k)     for _ in range(t):         a,b=sys.stdin.readline().strip().split()         a,b=int(a),int(b)         count=0         for i in range(a,b+1):             n=i//k             count+=(1+n*i-(1+n)*n*k/2+n)         print(int(count)) 测试用例全过了,但是线上通过率0%。说循环有误或者算法复杂度过大。难道要O(1)的复杂度? 求大佬解答
点赞 回复 分享
发布于 2019-09-01 22:13

相关推荐

06-15 02:05
已编辑
南昌航空大学 数据分析师
Eason三木:你如果想干技术岗,那几个发公众号合唱比赛的经历就去掉,优秀团员去掉,求职没用。然后CET4这种不是奖项,是技能,放到下面的专业技能里或者单独列一个英语能力。 另外好好改改你的排版,首行缩进完全没有必要,行间距好好调调,别让字和标题背景黏在一起,你下面说能做高质量PPT你得展现出来啊,你这简历排版我用PPT做的都能比你做的好。 然后自我评价,你如果要干数据工程师,抗压能力强最起码得有吧。
简历中的项目经历要怎么写
点赞 评论 收藏
分享
05-23 19:02
吉林大学 Java
点赞 评论 收藏
分享
评论
1
2
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务