python蓝桥杯 k倍区间

  • Post author:
  • Post category:python


给定一个长度为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 版权协议,转载请附上原文出处链接和本声明。