腾讯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

相关推荐

昨天 11:15
中南大学 Java
好可爱的hr姐姐哈哈哈哈
黑皮白袜臭脚体育生:兄弟们貂蝉在一起,吕布开了
点赞 评论 收藏
分享
程序员小白条:你是沟通了900个,不是投了900份简历,你能投900份,意味着对面都要回复你900次,你早就找到实习了,没亮点就是这样的,别局限地区,时间投的也要早,现在都要7月了
点赞 评论 收藏
分享
lllllkin:感觉可以精简到一页简历,有些排版感觉不是必须的。 时间线越早的,你自己越熟悉的放前面。描述可以更精简些,一些问题解决感觉可以不用写具体技术栈,卖个关子,等面试官问。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-09 16:15
我应届生,去年10月份开始在这家公司实习,到今年10月份正好一年想(实习+试用期),在想要不要提前9月份就离职,这样好找工作些,但又差一个月满一年,又怕10月份国庆回来离职,容易错过了下半年的金九银十,到年底容易gap到年后
小破站_程序员YT:说这家公司不好吧,你干了快一年 说这家公司好吧,你刚毕业就想跑路说你不懂行情吧,你怕错过金九银十说 你懂行情吧,校招阶段在实习,毕业社招想换工作 哥们,我该怎么劝你留下来呢
应届生,你找到工作了吗
点赞 评论 收藏
分享
评论
1
2
分享

创作者周榜

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