给定一个长度为N的数列,A1, A2, … AN,如果其中一段连续的子序列Ai, Ai+1, … Aj(i <= j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。
你能求出数列中总共有多少个K倍区间吗?
输入格式
5 2
1
2
3
4
5程序应该输出:
6
首先第一想法肯定是暴力,显然超时。
n,k=map(int,input().split())
l=[]
for i in range(n):
l.append(int(input()))
count=0
for i in range(len(l)):
for j in range(i,len(l)):
if(sum(l[i:j+1])%k==0):
count+=1
print(count)
接着参考了
蓝桥杯 K倍区间 python_风信子的猫Redamancy的博客-CSDN博客
,里面有讲到一个数学性质 ( sum[j]-sum[i-1] )%K= 0,即是 sum[j]%K-sum[i-1] %K= 0 ,即是sum[j]%K=sum[i-1] %K ,也就是算出数组所有数和K取余,余数相同的两个数就可以组成一个K倍区间,而为余数为0的数除了可以和别的0组成k倍区间以外,本身也是K倍区间。
那么怎么统计里面相同余数的想法就出来了。
n,k=map(int,input().split())
l=[]
for i in range(n):
l.append(int(input()))
ll=[sum(l[:i+1])%k for i in range(len(l))]
ll_only=list(set(ll))
res=ll.count(0)
for i in range(len(ll_only)):
tmp=ll.count(ll_only[i])
res+=tmp*(tmp-1)//2 #C(tmp,2)
print(res)
依然超时!费解了,参考大佬的代码
N,K = map(int,input().split())
ans = 0
cnt = [0]*K #把我的ll,用来存放模=>用来计数每个相同余数的个数
for i in range(N):
num = int(input())
ans += num #sum(i)
cnt[ans%K] += 1
ans = cnt[0] #统计0的个数
for i in range(0,K):
ans += cnt[i] * (cnt[i] - 1)//2
print(ans)
很巧妙的利用 cnt[ans%k],索引当作余数的值,来存放余数的个数。
版权声明:本文为zzzyr_yan原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。