全部评论
用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 最后不知道过了多少,快要交卷了
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)的复杂度? 求大佬解答
相关推荐
07-07 10:12
黑龙江外国语学院 Java 
点赞 评论 收藏
分享
06-25 20:44
乐山师范学院 Java 
点赞 评论 收藏
分享
05-21 00:25
电子科技大学 后端 lllllkin:感觉可以精简到一页简历,有些排版感觉不是必须的。
时间线越早的,你自己越熟悉的放前面。描述可以更精简些,一些问题解决感觉可以不用写具体技术栈,卖个关子,等面试官问。
点赞 评论 收藏
分享

点赞 评论 收藏
分享